Reconstruction of missing coefficients of overcomplete linear transforms using projections onto convex sets

• US 6,470,469 B1
• Filed: 03/26/1999
• Issued: 10/22/2002
• Est. Priority Date: 03/26/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chou, Philip A., Mehrotra, Sanjeev, Wang, Albert S.
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US09/276,842
• Time in Patent Office: 1,306 Days
• Field of Search: 714/746, 714/776
• US Class Current: 714/746
• CPC Class Codes: G06T 2207/20052 Discrete cosine transform [DCT]
• CPC Class Codes: G06T 2207/20056 Discrete and fast Fourier transform, [DFT, FFT]
• CPC Class Codes: G06T 5/10 using non-spatial domain filtering
• CPC Class Codes: G06T 5/77 Retouching; Inpainting; Scratch removal
• CPC Class Codes: H03M 13/03 Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
• CPC Class Codes: H03M 13/17 Burst error correction, e.g. error trapping, Fire codes
• CPC Class Codes: H03M 13/35 Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics

Abstract

A projection onto convex sets (POCS)-based method for consistent reconstruction of a signal from a subset of quantized coefficients received from an N×K overcomplete transform. By choosing a frame operator F to be the concatenization of two or more K×K invertible transforms, the POCS projections are calculated in R^K space using only the K×K transforms and their inverses, rather than the larger R^N space using pseudo inverse transforms. Practical reconstructions are enabled based on, for example, wavelet, subband, or lapped transforms of an entire image. In one embodiment, unequal error protection for multiple description source coding is provided. In particular, given a bit-plane representation of the coefficients in an overcomplete representation of the source, one embodiment of the present invention provides coding the most significant bits with the highest redundancy and the least significant bits with the lowest redundancy. In one embodiment, this is accomplished by varying the quantization stepsize for the different coefficients. Then, the available received quantized coefficients are decoded using a method based on alternating projections onto convex sets.

Claims

1. A computerized method of reconstructing a set of data x having K dimensions, the method comprising:

receiving a set of data y′

, wherein the set of data y′

corresponds to a set of data y but with some coefficients missing, wherein the set of data y has N dimensions and represents an overcomplete transformation of the set of data x, and wherein N>

K; and

iteratively transforming the received set of data y′

using projections onto K-dimensional convex sets as calculated with a computer to produce a set of data {circumflex over (x)} representing the reconstructed set of data x.

2. The method of claim 1, further comprising

providing an initial set of data x having K dimensions;

overcompletely transforming the set of data x to a set of coefficients y having N dimensions, where N>

K;

quantizing the coefficients of y to obtain indices j such that each coefficient y_1,i lies in the j_i^th quantization region and each one of the indices j correspond to a respective quantization region;

entropy coding the indices j to obtain binary descriptions; and

transmitting the binary descriptions on a channel.

3. The method of claim 2 wherein the transmitting on the channel further comprises:

storing the binary descriptions onto a storage medium; and

reading the binary descriptions from the storage medium.

4. The method of claim 1, wherein the iteratively transforming calculation further comprises:

transforming a set of data y₁ to a set of data y₂ using F₂F₁<sup>−

1</sup>,

setting components of the resulting set of data y₂ corresponding to received components to those received components y₂′

,

transforming the resulting set of data y₂ to a set of data y₁ using F₁F₂<sup>−

1</sup>,

setting components of the resulting set of data y₁ corresponding to received components to those received components y₁′

, and

transforming the resulting set of data y₁ to a set of data x′

using F₁<sup>−

1</sup>, wherein F₁ and F₂ are each K×

K transforms.

5. The method of claim 1, wherein the iteratively transforming calculation farther comprises:

(a) initializing a t=0;

(b) setting an initial point p₁(0) such that for each index i,

p_1,i(0)=ŷ

_1,i if i∈

R₁ and

p_1,i(0)=0 if i∉

R₁;

(c) transforming p₁(t) into the coordinate system of F₂ using

p₂(t)=F₂(F₁<sup>−

1</sup>p₁(t))=F₁₂p₁(t);

(d) projecting p₂(t) onto F₂Q such that for each index i,

q_2,i(t+1)=min{max{p_2,i(t),l_2,i}, u_2,i} if i∈

R₂ and

q_2,i(t+1)=p_2,i(t) if i∉

R₂;

(e) transforming q₂(t+1) into the coordinate system of F₁ using

q₁(t+1)=F₁(F₂<sup>−

1</sup>q₂(t+1))=F₂₁q₂(t+1);

(f) projecting q₁(t+1) onto F₁P such that for each index i,

p_1,i(t+1)=min{max{q_1,i(t+1),l_1,i}, u_1,i} if i∈

R₁; and

p_1,i(t+1)=p_2,i(t) if i∉

R₁; and

(g) reconstructing a set of data {circumflex over (x)}=F₁<sup>−

1</sup>p₁(t);

wherein;

F₁ and F₂ are each K×

K transforms,

F₁<sup>−

1</sup> is the inverse transform of F₁, F₂<sup>−

1</sup> is the inverse transform of F₂,

ŷ

₁ is a quantized version of y₁, ŷ

₂ is a quantized version of y₂, such that ŷ

₁ componentwise lies between respective lower and upper quantization cell boundary vectors l₁≦

ŷ

₁≦

u₁ and ŷ

₂ componentwise lies between respective lower and upper quantization cell boundary vectors l₂≦

ŷ

₂≦

u₂,

R₁⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₁, and

R₂⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₂.

6. The method of claim 5, wherein the iteratively transforming calculation further comprises:

(f1) checking for convergence by testing ∥

p₁(t+1)−

p₁(t)∥

²>

ε

, and if so then setting t←

t+1 and iterating (c) through (f).

7. The method of claim 6, wherein F₁ is a wavelet transform and F₂ is a discrete cosine transform.

8. The method of claim 1, wherein the iteratively transforming calculation further comprises:

(a) initializing a t=0;

(b) setting p_1,i(0)=ŷ

_1,i if i∈

R₁ (i.e., received descriptions) and

p_1,i(0)=0 if i∉

R₁;

(i.e., descriptions not received)

(c) for each m=1, . . . , M−

1 in turn;

(i) transforming p_m(t) into the coordinate system of F_m+1;

{tilde over (p)}m+1(t)=F_m+1F_m<sup>−

1</sup>P_m(t)=F_m,m+1p_m(t); and

(ii) projecting {tilde over (p)}_m+1(t) onto F_m+1P_m+1;

p_m+1,i(t)=min{max{{tilde over (p)}_m+1,i(t), l_{m 1,i}}u_m+1,i} if i∈

R₂

p_m+1,i(t)={tilde over (p)}_m+1,i(t) if i∉

R₂

(d) transforming p_M(t) into the coordinate system of F₁;

{tilde over (p)}₁(t+1)=F₁F_M<sup>−

1</sup>p_M(t)=F_M,1p_M(t)

(e) projecting {tilde over (p)}₁(t+1) onto F₁P₁;

p_1,i(t+1)=min{max{{tilde over (p)}_1,i(t+1), l_1,i}, u_1,i} if i∈

R₁

p_1,i(t+1)={tilde over (p)}_1,i(t+1) if i∉

R₁

(h) checking for convergence, and if ∥

p_n(t+1)−

p_n(t)∥

²>

epsilon for an n between 1 and M inclusive, then setting t←

t+1 and repeating (c) through (f), otherwise performing (g); and

(g) reconstructing x;

{circumflex over (x)}=F_n<sup>−

1</sup>p_n(t+1);

wherein;

F₁ through F_M are each K×

K transforms,

M is an integer larger than 1,

each F_m<sup>−

1</sup> is the inverse transform of F_m,

ŷ

₁ is a quantized version of y₁, such that ŷ

₁ componentwise lies between respective lower and upper quantization cell boundary vectors l₁≦

ŷ

₁≦

u₁ and each ŷ

_m componentwise lies between respective lower and upper quantization cell boundary vectors l_m≦

ŷ

_m≦

u_m,

R₁⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₁, and for each m, R_m⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

_m.

9. A computer readable medium having computer executable instructions stored thereon for performing a method of reconstructing a set of data x having K dimensions, the method comprising:

receiving a set of data y′

, wherein the set of data y′

corresponds to a set of data y but with some coefficients missing, wherein the set of data y has N dimensions and represents an overcomplete transformation of the set of data x, and wherein N>

K; and

iteratively transforming the received set of data y′

using projections onto convex sets as calculated with a computer to produce a set of data x′

representing the reconstructed set of data x.

10. The medium of claim 9, further including instructions such that the iteratively transforming further comprises:

(a) initializing a t=0;

(b) setting an initial point p₁(0) such that for each index i,

p_1,i(0)=ŷ

_1,i if i∈

R₁ and

p_1,i(0)=0 if i∉

R₁;

(c) transforming p₁(t) into the coordinate system of F₂ using

p₂(t)=F₂(F₁<sup>−

1</sup>p₁(t))=F₁₂p₁(t);

(d) projecting p₂(t) onto F₂Q such that for each index i,

q_2,i(t+1)=min{max{p_2,i(t),l_2,i}, u_2,i} if i∈

R₂ and

q_2,i(t+1)=p_2,i(t) if i∉

R₂;

(e) transforming q₂(t+1) into the coordinate system of F₁ using

q₁(t+1)=F₁(F₂<sup>−

1</sup>q₂(t+1))=F₂₁q₂(t+1);

(f) projecting q₁(t+1) onto F₁P such that for each index i,

p_1,i(t+1)=min{max{q_1,i(t+1),l_1,i},u_1,i} if i∈

R₁ and

p_1,i(t+1)=p_2,i(t) if i∉

R₁; and

(g) reconstructing a set of data {circumflex over (x)}=F₁<sup>−

1</sup>p₁(t);

wherein;

F₁ and F₂ are each K×

K transforms,

F₁<sup>−

1</sup> is the inverse transform of F₁, F₂<sup>−

1</sup> is the inverse transform of F₂,

ŷ

₁ is a quantized version of y₁, ŷ

₂ is a quantized version of y₂, such that ŷ

₁ componentwise lies between respective lower and upper quantization cell boundary vectors l₁≦

ŷ

₁≦

u₁ and ŷ

₂ componentwise lies between respective lower and upper quantization cell boundary vectors l₂≦

ŷ

₂≦

u₂,

R₁⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₁, and

R₂⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₂.

11. The medium of claim 10, further including instructions such that the iteratively transforming calculation further comprises:

(f1) checking for convergence by testing ∥

p₁(t+1)−

p₁(t)∥

²>

ε

, and if so then setting t←

t+1 and iterating (c) through (f).

12. The medium of claim 9, further including instructions such that the iteratively transforming further comprises:

(a) initializing a t=0;

(b) setting p_1,i(0)=ŷ

_1,i if i∈

R₁ (i.e., received descriptions) and

p_1,i(0)=0 if i∉

R₁;

(i.e., descriptions not received)

(c) for each m=1, . . . , M−

1 in turn;

(i) transforming p_m(t) into the coordinate system of F_m+1;

{tilde over (p)}_m+1(t)=F_m+1F_m<sup>−

1</sup>P_m(t)=F_m,m+1p_m(t); and

(ii) projecting {tilde over (p)}_m+1(t) onto F_m+1P_m+1;

p_m+1,i(t)=min{max{{tilde over (p)}m+1,i(t), l_m+1,i}u_m+1,i} if i∈

R₂

p_m+1,i(t)={tilde over (p)}_m+1,i(t) if i∉

R₂

(d) transforming p_M(t) into the coordinate system of F₁;

{tilde over (p)}₁(t+1)=F₁F_M<sup>−

1</sup>p_M(t)=F_M,1p_M(t)

(e) projecting {tilde over (p)}₁(t+1) onto F₁P₁;

p_1,i(t+1)=min{max{{tilde over (p)}_1,i(t+1), l_1,i}, u_1,i} if i∈

R₁

p_1,i(t+1)={tilde over (p)}_1,i(t+1) if i∉

R₁

(i) checking for convergence, and if ∥

p_n(t+1)−

p_n(t)∥

² >

epsilon for an n between 1 and M inclusive,

then setting t←

t+1 and repeating (c) through (f), otherwise performing (g); and

(g) reconstructing x;

{circumflex over (x)}=F_n<sup>−

1</sup>p_n(t+1);

wherein;

F₁ through F_M are each K×

K transforms,

M is an integer larger than 1,

each F_m<sup>−

1</sup> is the inverse transform of F_m,

ŷ

₁ is a quantized version of y₁, such that ŷ

₁ componentwise lies between respective lower and upper quantization cell boundary vectors l₁≦

ŷ

₁≦

u₁ and each ŷ

_m componentwise lies between respective lower and upper quantization cell boundary vectors l_m≦

ŷ

_m≦

u_m,

R₁⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₁, and for each m, R_m⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

_m.

13. A data-reconstruction system comprising:

means for receiving a set of data y′

, wherein the set of data y′

corresponds to a set of data y but with some coefficients missing, wherein the set of data y has N dimensions and represents an overcomplete transformation of the set of data x, and wherein N>

K; and

means, operatively coupled to the means for receiving, for iteratively transforming the received set of data y′

using projections onto convex sets to produce a set of data x′

representing the reconstructed set of data x.

14. The system of claim 13, wherein the means for iteratively transforming calculation further comprises:

(a) means for initializing a t=0;

(b) means for setting an initial point p₁(0) such that for each index i,

p_1,i(0)=ŷ

_1,i if i∈

R₁ and

p_1,i(0)=0 if i∉

R₁;

(c) means for transforming p₁(t) into the coordinate system of F₂ using

p₂(t)=F₂(F₁<sup>−

1</sup>p₁(t))=F₁₂p₁(t);

(d) means for projecting p₂(t) onto F₂Q such that for each index i,

q_2,i(t+1)=min{max{p_2,i(t),l_2,i}, u_2,i} if i∈

R₂ and

q_2,i(t+1)=p_2,i(t) if i∉

R₂;

(e) means for transforming q₂(t+1) into the coordinate system of F₁ using

q₁(t+1)=F₁(F₂<sup>−

1</sup>q₂(t+1))=F₂₁q₂(t+1);

(f) means for projecting q₁(t+1) onto F₁P such that for each index i,

p_1,i(t+1)=min{max{q_1,i(t+1), l_1,i},u_1,i} if i∈

R₁ and

p_1,i(t+1)=p_2,i(t) if i∉

R₁; and

(g) means for reconstructing a set of data {circumflex over (x)}=F₁<sup>−

1</sup>p₁(t);

wherein;

F₁ and F₂ are each K×

K transforms,

F₁<sup>−

1</sup> is the inverse transform of F₁, F₂<sup>−

1</sup> is the inverse transform of F₂,

ŷ

₁ is a quantized version of y₁, ŷ

₂ is a quantized version of y₂, such that ŷ

₁ componentwise lies between respective lower and upper quantization cell boundary vectors l₁≦

ŷ

₁≦

u₁ and ŷ

₂ componentwise lies between respective lower and upper quantization cell boundary vectors l₂≦

ŷ

₂≦

u₂,

R₁⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₁, and

R₂⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₂.

15. The system of claim 14, wherein the means for iteratively transforming further comprises:

(f1) means for checking for convergence including means for testing

∥

p₁(t+1)−

p₁(t)∥

²>

ε

, and means for setting t←

t+1 and iterating means (c) through (f) if so.

16. The system of claim 13, wherein the means for iteratively transforming calculation further comprises:

(a) means for initializing a t=0;

(c) means for setting

p_1,i(0)=ŷ

_1,i if i∈

R₁ (i.e., received descriptions) and

p_1,i(0)=0 if i∉

R₁;

(i.e., descriptions not received)

(c) for each m=1, . . . , M−

1 in turn;

(i) means for transforming p_m(t) into the coordinate system of F_m+1;

{tilde over (p)}_m+1(t)=F_m+1F_m<sup>−

1</sup>P_m(t)=F_m,m+1p_m(t); and

(ii) means for projecting {tilde over (p)}_m+1(t) onto F_m+1,P_m+1;

p_m+1,i(t)=min{max{{tilde over (p)}_m+1,i(t), l_m+1,i}u_m+1,i} if i∈

R₂

p_m+1,i(t)={tilde over (p)}_m+1,i(t) if i∉

R₂

(d) means for transforming p_M(t) into the coordinate system of F₁;

{tilde over (p)}₁(t+1)=F₁F_M<sup>−

1</sup>p_M(t)=F_M,1p_M(t)

(e) means for projecting {tilde over (p)}₁(t+1) onto F₁P₁;

p_1,i(t+1)=min{max{{tilde over (p)}_1,i(t+1), l_1,i}, u_1,i} if i∈

R₁

p_1,i(t+1)={tilde over (p)}_1,i(t+1) if i∉

R₁

(j) means for checking for convergence, and if ∥

p_n(t+1)−

p_n(t)∥

²>

epsilon for an n between 1 and M inclusive,

then means for setting t←

t+1 and repeating (c) through (f), otherwise means for going to (g); and

(g) means for reconstructing x.

{circumflex over (x)}=F_n<sup>−

1</sup>p_n(t+1);

wherein;

F₁ through F_M are each K×

K transforms,

M is an integer larger than 1,

F_m<sup>−

1</sup> is the inverse transform of F_m,

ŷ

₁ is a quantized version of y₁, such that ŷ

₁ componentwise lies between respective lower and upper quantization cell boundary vectors l₁≦

ŷ

₁≦

u₁ and each ŷ

_m componentwise lies between respective lower and upper quantization cell boundary vectors l_m≦

ŷ

_m≦

u_m,

R₁⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₁ and for each m, R_m⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

_m.

17. The system of claim 14, wherein F₁ is a wavelet transform and F₂ is a discrete cosine transform.

18. The system of claim 14, wherein the means for iteratively transforming calculation further comprises:

means for transforming a set of data y₁ to a set of data y₂ using F₂ F₁<sup>−

1</sup>,

means for setting components of the resulting set of data y₂ corresponding to received components to those received components y₂′

,

means for transforming the resulting set of data y₂ to a set of data y₁ using F₁ F₂<sup>−

1</sup>,

means for setting components of the resulting set of data y₁ corresponding to received components to those received components y₁′

, and

means for transforming the resulting set of data y₁ to a set of data x′

using F₁<sup>−

1</sup>,

wherein F₁ and F₂ are each K×

K transforms.

19. The system of claim 16, further comprising

means for providing an initial set of data x having K dimensions;

means for overcompletely transforming the set of data x to a set of coefficients y having N dimensions, where N>

K;

means for quantizing the coefficients of y to obtain indices j such that each coefficient y_i lies in the j_i^th quantization region and each one of the indices j correspond to a respective quantization region;

means for entropy coding the indices j to obtain binary descriptions; and

means for transmitting the binary descriptions on a channel.

20. The system of claim 19 wherein the transmitting on the channel further comprises:

means for storing the binary descriptions onto a storage medium; and

means for reading the binary descriptions from the storage medium.

21. A computerized method of reconstructing data after a transmission on an erasure channel, the method comprising:

providing an initial set of data x having K dimensions;

overcompletely transforming the set of data x to a set of data y having N dimensions, where N>

K;

transmitting the set of data y on the channel;

receiving a set of data y′

from the channel; and

iteratively transforming the received set of data y′

using projections onto convex sets that use at least two different K×

K transforms.

22. The method of claim 21, wherein the iteratively transforming further comprises:

(a) initializing a t=0;

(b) setting an initial point p₁(0) such that for each index i,

p_1,i(0)=ŷ

_1,i if i∈

R₁ and

p_1,i(0)=0 if i∉

R₁;

(c) transforming p₁(t) into the coordinate system of F₂ using

p₂(t)=F₂(F₁<sup>−

1</sup>p₁(t))=F₁₂p₁(t);

(d) projecting p₂(t) onto F₂Q such that for each index i,

q_2,i(t+1)=min{max{p_2,i(t),l_2,i},u_2,i} if i∈

R₂ and

q_2,i(t+1=p_2,i(t) if i∉

R₂;

(e) transforming q₂(t+1) into the coordinate system of F₁ using

q₁(t+1)=F₁(F₂<sup>−

1</sup>q₂(t+1))=F₂₁q₂(t+1);

(f) projecting q₁(t+1) onto F₁P such that for each index i,

p_1,i(t+1)=min{max{q_1,i(t+1),l_1,i},u_1,i} if i∈

R₁ and

p_1,i(t+1)=p_2,i(t) if i∉

R₁;

(g) checking for convergence by testing ∥

p₁(t+1)−

p₁(t)∥

²>

ε

, and if so then setting

t←

t+1 and iterating (c) through (g); and

(h) reconstructing a set of data {circumflex over (x)}=F₁<sup>−

1</sup>p₁(t);

wherein;

F₁ and F₂ are each K×

K transforms,

F₁<sup>−

1</sup> is the inverse transform of F₁, F₂<sup>−

1</sup> is the inverse transform of F₂,

ŷ

₁ is a quantized version of y₁, ŷ

₂ is a quantized version of y₂, such that ŷ

₁ componentwise lies between respective lower and upper quantization cell boundary vectors l₁≦

ŷ

₁≦

u₁ and ŷ

₂ componentwise lies between respective lower and upper quantization cell boundary vectors l₂≦

ŷ

₂≦

u₂,

R₁⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₁, and

R₂⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₂.

23. The method of claim 21, wherein the iteratively transforming further comprises:

(a) initializing a t=0;

(b) setting p_1,i(0)=ŷ

_1,i if i∈

R₁ (i.e., received descriptions) and

p_1,i(0)=0 if i∉

R₁;

(i.e., descriptions not received)

(c) for each m=1, . . . , M−

1 in turn;

(i) transforming p_m(t) into the coordinate system of F_m+1;

{tilde over (p)}_m+1(t)=F_m+1F_m<sup>−

1</sup>P_m(t)=F_m,m+1p_m(t); and

(ii) projecting {tilde over (p)}_m+1(t) onto F_m+1P_m+1;

p_m+1,i(t)=min{max{{tilde over (p)}_m+1,i(t), l_m+1,i}u_m+1,i} if i∈

R₂

p_m+1,i(t)={tilde over (p)}_m+1,i(t) if i∉

R₂

(d) transforming p_M(t) into the coordinate system of F₁;

{tilde over (p)}₁(t+1)=F₁F_M<sup>−

1</sup>p_M(t)=F_M,1p_M(t)

(e) projecting {tilde over (p)}₁(t+1) onto F₁P₁;

p_1,i(t+1)=min{max{{tilde over (p)}_1,i(t+1), l_1,i}, u_1,i} if i∈

R₁

p_1,i(t+1)={tilde over (p)}_1,i(t+1) if i∉

R₁

(k) checking for convergence, and if ∥

p_n(t+1)−

p_n(t)∥

² >

epsilon for an n between 1 and M inclusive,

then setting t←

t+l and repeating (c) through (f), otherwise performing (g); and

(g) reconstructing x;

{circumflex over (x)}=F_n<sup>−

1</sup>p_n(t+1);

wherein;

F₁ through F_M are each K×

K transforms,

M is an integer larger than 1,

each F_m<sup>−

1</sup> is the inverse transform of F_m,

ŷ

₁ is a quantized version of y₁, such that ŷ

₁ componentwise lies between respective lower and upper quantization cell boundary vectors l₁≦

ŷ

₁≦

u₁ and each ŷ

_m componentwise lies between respective lower and upper quantization cell boundary vectors l_m≦

ŷ

_m≦

u_m,

R₁⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₁, and for each m, R_m⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

_m.

24. A computer-readable medium having instructions stored thereon for causing a computer to perform the method of claim 22.

25. A computer-readable medium having instructions stored thereon for causing a computer to perform the method of claim 23.

26. A data-reconstruction mechanism for an image system, the mechanism comprising:

a module that receives a set of data y′

, wherein the set of data y′

corresponds to a set of data y but with some coefficients missing, wherein the set of data y has N dimensions and represents an overcomplete transformation of the set of image data x, and wherein N>

K; and

a module that iteratively transforms the received set of data y′

using projections onto convex sets as calculated with a computer to produce a set of image data x′

representing the reconstructed set of image data x.

27. The mechanism of claim 26, wherein the module that iteratively transforms includes:

a module that transforms a set of data y₁ to a set of data y₂ using F₂F₁<sup>−

1</sup>,

a module that sets components of the resulting set of data y₂ corresponding to received components to those received components y₂′

,

a module that transforms the resulting set of data y₂ to a set of data y₁ using F₁F₂<sup>−

1</sup>,

a module that sets components of the resulting set of data y₁ corresponding to received components to those received components y₁′

, and

a module that transforms the resulting set of data y₁ to a set of data x′

using F₁<sup>−

1</sup>,

wherein F₁ and F₂ are structured transforms that project onto convex sets.

28. The mechanism of claim 26, wherein the module that iteratively transforms includes:

(a) a module that initializes a t=0;

(b) a module that sets an initial point p₁(0) such that for each index i,

p_1,i(0)=ŷ

_1,i if i∈

R₁ and

p_1,i(0)=0 if i∉

R₁;

(c) a module that transforms p₁(t) into the coordinate system of F₂ using

p₂(t)=F₂(F₁<sup>−

1</sup>p₁(t))=F₁₂p₁(t);

(d) a module that projects p₂(t) onto F₂Q such that for each index i,

q_2,i(t+1)=min{max{p_2,i(t),l_2,i},u_2,i} if i∈

R₂ and

q_2,i(t+1)=p_2,i(t) if i∉

R₂;

(e) a module that transforms q₂(t+1) into the coordinate system of F₁ using

q₁(t+1)=F₁(F₂<sup>−

1</sup>q₂(t+1))=F₂₁q₂(t+1);

(f) a module that projects q₁(t+1) onto F₁P such that for each index i,

p_1,i(t+1)=min{max{q_1,i(t+1),l_1,i},u_1,i} if i∈

R₁ and

p_1,i(t+1)=p_2,i(t) if i∉

R₁;

(g) a module that checks for convergence by testing if ∥

p₁(t+1)−

p₁(t)∥

²>

ε

, and if

so then sets t←

t+1 and iterates modules (c) through (g); and

(h) a module that reconstructs a set of data {circumflex over (x)}=F₁<sup>−

1</sup>p₁(t);

wherein;

F₁ and F₂ are each K×

K transforms,

F₁<sup>−

1</sup> is the inverse transform of F₁, F₂<sup>−

1</sup> is the inverse transform of F₂,

ŷ

₁ is a quantized version of y₁, ŷ

₂ is a quantized version of y₂, such that ŷ

₁ componentwise lies between respective lower and upper quantization cell boundary vectors l₁≦

ŷ

₁≦

u₁ and ŷ

₂ componentwise lies between respective lower and upper quantization cell boundary vectors l₂≦

ŷ

₂≦

u₂,

R₁⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₁, and

R₂⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₂.

29. The mechanism of claim 26, wherein the module that iteratively transforms includes:

(a) a module that initializes a t=0;

(b) a module that sets an initial point p₁(0) such that for each index i,

p_1,i(0)=ŷ

_1,i if i∈

R₁ (i.e., received descriptions) and

p_1,i(0)=0 if i∉

R₁;

(i.e., descriptions not received)

(c) for each m=1, . . . , M−

1 in turn;

(i) a module that transforms p_m(t) into the coordinate system of F_m+1;

{tilde over (p)}_m+1(t)=F_m+1F_m+1P_m(t)=F_m,m+1p_m(t); and

(ii) a module that projects {tilde over (p)}_m+1(t) onto F_m+1P_m+1;

p_m+1,i(t)=min{max{{tilde over (p)}_m+1,i(t), l_m+1,i}u_m+1,i} if i∈

R₂

p_m+1,i(t)={tilde over (p)}_m+1,i(t) if i∉

R₂

(d) a module that transforms p_M(t) into the coordinate system of F₁;

{tilde over (p)}₁(t+1)=F₁F_M<sup>−

1</sup>p_M(t)=F_M,1p_M(t)

(e) a module that projects {tilde over (p)}₁(t+1) onto F₁P₁;

p_1,i(t+1)=min{max{{tilde over (p)}_1,i(t+1), l_1,i}, u_1,i} if i∈

R₁

p_1,i(t+1)={tilde over (p)}_1,i(t+1) if i∉

R₁

(l) a module that checks for convergence, and if ∥

p_n(t+1)−

p_n(t)∥

² >

epsilon for an n between 1 and M inclusive,

then sets t←

t+1 and repeating (c) through (f), otherwise performs (g); and

(g) a module that reconstructs x;

{circumflex over (x)}=F_n<sup>−

1</sup>p_n(t+1);

wherein;

F₁ through F_M are each K×

K transforms,

M is an integer larger than 1,

each F_m<sup>−

1</sup> is the inverse transform of F_m,

ŷ

₁ is a quantized version of y₁, such that ŷ

₁ componentwise lies between respective lower and upper quantization cell boundary vectors l₁≦

ŷ

₁≦

u₁ and each ŷ

_m componentwise lies between respective lower and upper quantization cell boundary vectors l_m≦

ŷ

_m≦

u_m,

R₁⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₁, and for each m, R_m⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

_m.

30. A computerized method of reconstructing data after a transmission on an erasure channel, the method comprising:

iteratively transforming the received set of data y′

using projections onto convex sets that use at least two different K×

K transforms including;

(a) initializing t;

(b) setting an initial point in F₁P;

(c) transforming p₁(t) into the coordinate system of F₂;

(d) projecting p₂(t) onto F₂Q;

(e) transforming q₂(t+1) into the coordinate system of F₁;

(f) projecting q₁(t+1) onto F₁P;

(g) checking for convergence and if not sufficiently converged then iterating (c) through (g); and

(h) reconstructing {circumflex over (x)}=F₁<sup>−

1</sup>p₁(t+1) wherein;

F₁ and F₂ are each K×

K transforms.

31. The method of claim 30, further comprising:

providing an initial set of data x having K dimensions;

overcompletely transforming the set of data x to a set of data y having N dimensions, where N>

K;

transmitting the set of data y on the channel; and

receiving a set of data y′

from the channel.

32. The method of claim 30, wherein

(a) initializing further includes initializing t=0;

(b) starting further includes setting an initial point p₁(0) such that for each index i,

p_1,i(0)=ŷ

_1,i if i∈

R₁ and

p_1,i(0)=0 if i∉

R₁;

(c) transforming p₁(t) further includes transforming p₁(t) into the coordinate system of F₂ using p₂(t)=F₂(F₁<sup>−

1</sup>p₁(t))=F₁₂p₁(t);

(d) projecting p₂(t) further includes projecting p₂(t) onto F₂Q such that for each index i;

q_2,i(t+1)=min{max{p_2,i(t),l_2,i},u_2,i} if i∈

R₂ and

q_2,i(t+)=p_2,i(t) if i∉

R₂;

(e) transforming q₂(t+1) further includes transforming q₂(t+1) into the coordinate system of F₁ using q₁(t+1)=F₁(F₂<sup>−

1</sup>q₂(t+1))=F₂₁q₂(t+1);

(f) projecting q₁(t+1) further includes projecting q₁(t+1) onto F₁P such that for each index i;

p_1,i(t+1)=min{max{q_1,i(t+1),l_1,i},u_1,i} if i∈

R₁ and

p_1,i(t+1)=p_2,i(t) if i∉

R₁; and

(g) checking further includes checking for convergence by testing ∥

p₁(t+1)−

p₁(t)∥

²>

ε

, and if so then setting t←

t+1 and iterating (c) through (g).

and wherein;

F₁ and F₂ are each K×

K transforms,

F₁<sup>−

1</sup>is the inverse transform of F₁, F₂<sup>−

1</sup> is the inverse transform of F₂,

ŷ

₁ is a quantized version of y₁, ŷ

₂ is a quantized version of y₂, such that ŷ

₁ componentwise lies between respective lower and upper quantization cell boundary vectors l₁≦

ŷ

₁≦

u₁ and ŷ

₂ componentwise lies between respective lower and upper quantization cell boundary vectors l₂≦

ŷ

₂≦

u₂,

R₁⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₁, and

R₂⊂

{1, . . . , K} is the set of indices of the descriptions received of ŷ

₂.

33. The method of claim 30, wherein the (a) initializing t, (b) setting an initial point in F₁P, (c) transforming p₁(t) into the coordinate system of F₂, (d) projecting p₂(t) onto F₂Q, (e) transforming q₂(t+1) into the coordinate system of F₁, (f) projecting q₁(t+1) onto F₁P, (g) checking for convergence and if not sufficiently converged then iterating (c) through (g);

and (h) reconstructing {circumflex over (x)}=F₁<sup>−

1</sup>p₁(t+1) are performed in the order listed.