Reconstruction of missing coefficients of overcomplete linear transforms using projections onto convex sets
First Claim
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 Assignments
0 Petitions
Accused Products
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 RK space using only the K×K transforms and their inverses, rather than the larger RN 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.
-
Citations
33 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.- View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
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 y1,i lies in the jith 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 y1 to a set of data y2 using F2F1−
1,setting components of the resulting set of data y2 corresponding to received components to those received components y2′
,transforming the resulting set of data y2 to a set of data y1 using F1F2−
1,setting components of the resulting set of data y1 corresponding to received components to those received components y1′
, andtransforming the resulting set of data y1 to a set of data x′
using F1−
1, wherein F1 and F2 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 p1(0) such that for each index i, p1,i(0)=ŷ
1,i if i∈
R1 andp1,i(0)=0 if i∉
R1;
(c) transforming p1(t) into the coordinate system of F2 using p2(t)=F2(F1−
1p1(t))=F12p1(t);
(d) projecting p2(t) onto F2Q such that for each index i, q2,i(t+1)=min{max{p2,i(t),l2,i}, u2,i} if i∈
R2 andq2,i(t+1)=p2,i(t) if i∉
R2;
(e) transforming q2(t+1) into the coordinate system of F1 using q1(t+1)=F1(F2−
1q2(t+1))=F21q2(t+1);
(f) projecting q1(t+1) onto F1P such that for each index i, p1,i(t+1)=min{max{q1,i(t+1),l1,i}, u1,i} if i∈
R1; and
p1,i(t+1)=p2,i(t) if i∉
R1; and
(g) reconstructing a set of data {circumflex over (x)}=F1−
1p1(t);
wherein;
F1 and F2 are each K×
K transforms,F1−
1 is the inverse transform of F1, F2−
1 is the inverse transform of F2,ŷ
1 is a quantized version of y1, ŷ
2 is a quantized version of y2, such that ŷ
1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦
ŷ
1≦
u1 and ŷ
2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦
ŷ
2≦
u2,R1⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
1, andR2⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
2.
-
-
6. The method of claim 5, wherein the iteratively transforming calculation further comprises:
(f1) checking for convergence by testing ∥
p1(t+1)−
p1(t)∥
2>
ε
, and if so then setting t←
t+1 and iterating (c) through (f).
-
7. The method of claim 6, wherein F1 is a wavelet transform and F2 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 p1,i(0)=ŷ
1,i if i∈
R1 (i.e., received descriptions) andp1,i(0)=0 if i∉
R1;
(i.e., descriptions not received)(c) for each m=1, . . . , M−
1 in turn;
(i) transforming pm(t) into the coordinate system of Fm+1;
{tilde over (p)}m+1(t)=Fm+1Fm−
1Pm(t)=Fm,m+1pm(t); and
(ii) projecting {tilde over (p)}m+1(t) onto Fm+1Pm+1;
pm+1,i(t)=min{max{{tilde over (p)}m+1,i(t), lm 1,i}um+1,i} if i∈
R2pm+1,i(t)={tilde over (p)}m+1,i(t) if i∉
R2(d) transforming pM(t) into the coordinate system of F1;
{tilde over (p)}1(t+1)=F1FM−
1pM(t)=FM,1pM(t)(e) projecting {tilde over (p)}1(t+1) onto F1P1;
p1,i(t+1)=min{max{{tilde over (p)}1,i(t+1), l1,i}, u1,i} if i∈
R1p1,i(t+1)={tilde over (p)}1,i(t+1) if i∉
R1(h) checking for convergence, and if ∥
pn(t+1)−
pn(t)∥
2>
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)}=Fn−
1pn(t+1);
wherein;
F1 through FM are each K×
K transforms,M is an integer larger than 1, each Fm−
1 is the inverse transform of Fm,ŷ
1 is a quantized version of y1, such that ŷ
1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦
ŷ
1≦
u1 and each ŷ
m componentwise lies between respective lower and upper quantization cell boundary vectors lm≦
ŷ
m≦
um,R1⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
1, and for each m, Rm⊂
{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.- View Dependent Claims (10, 11, 12)
(a) initializing a t=0;
(b) setting an initial point p1(0) such that for each index i, p1,i(0)=ŷ
1,i if i∈
R1 andp1,i(0)=0 if i∉
R1;
(c) transforming p1(t) into the coordinate system of F2 using p2(t)=F2(F1−
1p1(t))=F12p1(t);
(d) projecting p2(t) onto F2Q such that for each index i, q2,i(t+1)=min{max{p2,i(t),l2,i}, u2,i} if i∈
R2 andq2,i(t+1)=p2,i(t) if i∉
R2;
(e) transforming q2(t+1) into the coordinate system of F1 using q1(t+1)=F1(F2−
1q2(t+1))=F21q2(t+1);
(f) projecting q1(t+1) onto F1P such that for each index i, p1,i(t+1)=min{max{q1,i(t+1),l1,i},u1,i} if i∈
R1 andp1,i(t+1)=p2,i(t) if i∉
R1; and
(g) reconstructing a set of data {circumflex over (x)}=F1−
1p1(t);
wherein;
F1 and F2 are each K×
K transforms,F1−
1 is the inverse transform of F1, F2−
1 is the inverse transform of F2,ŷ
1 is a quantized version of y1, ŷ
2 is a quantized version of y2, such that ŷ
1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦
ŷ
1≦
u1 and ŷ
2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦
ŷ
2≦
u2,R1⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
1, andR2⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
2.
-
-
11. The medium of claim 10, further including instructions such that the iteratively transforming calculation further comprises:
(f1) checking for convergence by testing ∥
p1(t+1)−
p1(t)∥
2>
ε
, 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 p1,i(0)=ŷ
1,i if i∈
R1 (i.e., received descriptions) andp1,i(0)=0 if i∉
R1;
(i.e., descriptions not received)(c) for each m=1, . . . , M−
1 in turn;
(i) transforming pm(t) into the coordinate system of Fm+1;
{tilde over (p)}m+1(t)=Fm+1Fm−
1Pm(t)=Fm,m+1pm(t); and
(ii) projecting {tilde over (p)}m+1(t) onto Fm+1Pm+1;
pm+1,i(t)=min{max{{tilde over (p)}m+1,i(t), lm+1,i}um+1,i} if i∈
R2pm+1,i(t)={tilde over (p)}m+1,i(t) if i∉
R2(d) transforming pM(t) into the coordinate system of F1;
{tilde over (p)}1(t+1)=F1FM−
1pM(t)=FM,1pM(t)(e) projecting {tilde over (p)}1(t+1) onto F1P1;
p1,i(t+1)=min{max{{tilde over (p)}1,i(t+1), l1,i}, u1,i} if i∈
R1p1,i(t+1)={tilde over (p)}1,i(t+1) if i∉
R1(i) checking for convergence, and if ∥
pn(t+1)−
pn(t)∥
2 >
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)}=Fn−
1pn(t+1);
wherein;
F1 through FM are each K×
K transforms,M is an integer larger than 1, each Fm−
1 is the inverse transform of Fm,ŷ
1 is a quantized version of y1, such that ŷ
1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦
ŷ
1≦
u1 and each ŷ
m componentwise lies between respective lower and upper quantization cell boundary vectors lm≦
ŷ
m≦
um,R1⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
1, and for each m, Rm⊂
{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.- View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
(a) means for initializing a t=0;
(b) means for setting an initial point p1(0) such that for each index i, p1,i(0)=ŷ
1,i if i∈
R1 andp1,i(0)=0 if i∉
R1;
(c) means for transforming p1(t) into the coordinate system of F2 using p2(t)=F2(F1−
1p1(t))=F12p1(t);
(d) means for projecting p2(t) onto F2Q such that for each index i, q2,i(t+1)=min{max{p2,i(t),l2,i}, u2,i} if i∈
R2 andq2,i(t+1)=p2,i(t) if i∉
R2;
(e) means for transforming q2(t+1) into the coordinate system of F1 using q1(t+1)=F1(F2−
1q2(t+1))=F21q2(t+1);
(f) means for projecting q1(t+1) onto F1P such that for each index i, p1,i(t+1)=min{max{q1,i(t+1), l1,i},u1,i} if i∈
R1 andp1,i(t+1)=p2,i(t) if i∉
R1; and
(g) means for reconstructing a set of data {circumflex over (x)}=F1−
1p1(t);
wherein;
F1 and F2 are each K×
K transforms,F1−
1 is the inverse transform of F1, F2−
1 is the inverse transform of F2,ŷ
1 is a quantized version of y1, ŷ
2 is a quantized version of y2, such that ŷ
1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦
ŷ
1≦
u1 and ŷ
2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦
ŷ
2≦
u2,R1⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
1, andR2⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
2.
-
-
15. The system of claim 14, wherein the means for iteratively transforming further comprises:
-
(f1) means for checking for convergence including means for testing ∥
p1(t+1)−
p1(t)∥
2>
ε
, 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 p1,i(0)=ŷ
1,i if i∈
R1 (i.e., received descriptions) andp1,i(0)=0 if i∉
R1;
(i.e., descriptions not received)(c) for each m=1, . . . , M−
1 in turn;
(i) means for transforming pm(t) into the coordinate system of Fm+1;
{tilde over (p)}m+1(t)=Fm+1Fm−
1Pm(t)=Fm,m+1pm(t); and
(ii) means for projecting {tilde over (p)}m+1(t) onto Fm+1,Pm+1;
pm+1,i(t)=min{max{{tilde over (p)}m+1,i(t), lm+1,i}um+1,i} if i∈
R2pm+1,i(t)={tilde over (p)}m+1,i(t) if i∉
R2(d) means for transforming pM(t) into the coordinate system of F1;
{tilde over (p)}1(t+1)=F1FM−
1pM(t)=FM,1pM(t)(e) means for projecting {tilde over (p)}1(t+1) onto F1P1;
p1,i(t+1)=min{max{{tilde over (p)}1,i(t+1), l1,i}, u1,i} if i∈
R1p1,i(t+1)={tilde over (p)}1,i(t+1) if i∉
R1(j) means for checking for convergence, and if ∥
pn(t+1)−
pn(t)∥
2>
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)}=Fn−
1pn(t+1);
wherein;
F1 through FM are each K×
K transforms,M is an integer larger than 1, Fm−
1 is the inverse transform of Fm,ŷ
1 is a quantized version of y1, such that ŷ
1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦
ŷ
1≦
u1 and each ŷ
m componentwise lies between respective lower and upper quantization cell boundary vectors lm≦
ŷ
m≦
um,R1⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
1 and for each m, Rm⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
m.
-
-
17. The system of claim 14, wherein F1 is a wavelet transform and F2 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 y1 to a set of data y2 using F2 F1−
1,means for setting components of the resulting set of data y2 corresponding to received components to those received components y2′
,means for transforming the resulting set of data y2 to a set of data y1 using F1 F2−
1,means for setting components of the resulting set of data y1 corresponding to received components to those received components y1′
, andmeans for transforming the resulting set of data y1 to a set of data x′
using F1−
1,wherein F1 and F2 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 yi lies in the jith 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.- View Dependent Claims (22, 23, 24, 25)
(a) initializing a t=0;
(b) setting an initial point p1(0) such that for each index i, p1,i(0)=ŷ
1,i if i∈
R1 andp1,i(0)=0 if i∉
R1;
(c) transforming p1(t) into the coordinate system of F2 using p2(t)=F2(F1−
1p1(t))=F12p1(t);
(d) projecting p2(t) onto F2Q such that for each index i, q2,i(t+1)=min{max{p2,i(t),l2,i},u2,i} if i∈
R2 andq2,i(t+1=p2,i(t) if i∉
R2;
(e) transforming q2(t+1) into the coordinate system of F1 using q1(t+1)=F1(F2−
1q2(t+1))=F21q2(t+1);
(f) projecting q1(t+1) onto F1P such that for each index i, p1,i(t+1)=min{max{q1,i(t+1),l1,i},u1,i} if i∈
R1 andp1,i(t+1)=p2,i(t) if i∉
R1;
(g) checking for convergence by testing ∥
p1(t+1)−
p1(t)∥
2>
ε
, and if so then settingt←
t+1 and iterating (c) through (g); and
(h) reconstructing a set of data {circumflex over (x)}=F1−
1p1(t);
wherein;
F1 and F2 are each K×
K transforms,F1−
1 is the inverse transform of F1, F2−
1 is the inverse transform of F2,ŷ
1 is a quantized version of y1, ŷ
2 is a quantized version of y2, such that ŷ
1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦
ŷ
1≦
u1 and ŷ
2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦
ŷ
2≦
u2,R1⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
1, andR2⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
2.
-
-
23. The method of claim 21, wherein the iteratively transforming further comprises:
-
(a) initializing a t=0;
(b) setting p1,i(0)=ŷ
1,i if i∈
R1 (i.e., received descriptions) andp1,i(0)=0 if i∉
R1;
(i.e., descriptions not received)(c) for each m=1, . . . , M−
1 in turn;
(i) transforming pm(t) into the coordinate system of Fm+1;
{tilde over (p)}m+1(t)=Fm+1Fm−
1Pm(t)=Fm,m+1pm(t); and
(ii) projecting {tilde over (p)}m+1(t) onto Fm+1Pm+1;
pm+1,i(t)=min{max{{tilde over (p)}m+1,i(t), lm+1,i}um+1,i} if i∈
R2pm+1,i(t)={tilde over (p)}m+1,i(t) if i∉
R2(d) transforming pM(t) into the coordinate system of F1;
{tilde over (p)}1(t+1)=F1FM−
1pM(t)=FM,1pM(t)(e) projecting {tilde over (p)}1(t+1) onto F1P1;
p1,i(t+1)=min{max{{tilde over (p)}1,i(t+1), l1,i}, u1,i} if i∈
R1p1,i(t+1)={tilde over (p)}1,i(t+1) if i∉
R1(k) checking for convergence, and if ∥
pn(t+1)−
pn(t)∥
2 >
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)}=Fn−
1pn(t+1);
wherein;
F1 through FM are each K×
K transforms,M is an integer larger than 1, each Fm−
1 is the inverse transform of Fm,ŷ
1 is a quantized version of y1, such that ŷ
1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦
ŷ
1≦
u1 and each ŷ
m componentwise lies between respective lower and upper quantization cell boundary vectors lm≦
ŷ
m≦
um,R1⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
1, and for each m, Rm⊂
{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.- View Dependent Claims (27, 28, 29)
a module that transforms a set of data y1 to a set of data y2 using F2F1−
1,a module that sets components of the resulting set of data y2 corresponding to received components to those received components y2′
,a module that transforms the resulting set of data y2 to a set of data y1 using F1F2−
1,a module that sets components of the resulting set of data y1 corresponding to received components to those received components y1′
, anda module that transforms the resulting set of data y1 to a set of data x′
using F1−
1,wherein F1 and F2 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 p1(0) such that for each index i, p1,i(0)=ŷ
1,i if i∈
R1 andp1,i(0)=0 if i∉
R1;
(c) a module that transforms p1(t) into the coordinate system of F2 using p2(t)=F2(F1−
1p1(t))=F12p1(t);
(d) a module that projects p2(t) onto F2Q such that for each index i, q2,i(t+1)=min{max{p2,i(t),l2,i},u2,i} if i∈
R2 andq2,i(t+1)=p2,i(t) if i∉
R2;
(e) a module that transforms q2(t+1) into the coordinate system of F1 using q1(t+1)=F1(F2−
1q2(t+1))=F21q2(t+1);
(f) a module that projects q1(t+1) onto F1P such that for each index i, p1,i(t+1)=min{max{q1,i(t+1),l1,i},u1,i} if i∈
R1 andp1,i(t+1)=p2,i(t) if i∉
R1;
(g) a module that checks for convergence by testing if ∥
p1(t+1)−
p1(t)∥
2>
ε
, and ifso then sets t←
t+1 and iterates modules (c) through (g); and
(h) a module that reconstructs a set of data {circumflex over (x)}=F1−
1p1(t);
wherein;
F1 and F2 are each K×
K transforms,F1−
1 is the inverse transform of F1, F2−
1 is the inverse transform of F2,ŷ
1 is a quantized version of y1, ŷ
2 is a quantized version of y2, such that ŷ
1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦
ŷ
1≦
u1 and ŷ
2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦
ŷ
2≦
u2,R1⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
1, andR2⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
2.
-
-
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 p1(0) such that for each index i, p1,i(0)=ŷ
1,i if i∈
R1 (i.e., received descriptions) andp1,i(0)=0 if i∉
R1;
(i.e., descriptions not received)(c) for each m=1, . . . , M−
1 in turn;
(i) a module that transforms pm(t) into the coordinate system of Fm+1;
{tilde over (p)}m+1(t)=Fm+1Fm+1Pm(t)=Fm,m+1pm(t); and
(ii) a module that projects {tilde over (p)}m+1(t) onto Fm+1Pm+1;
pm+1,i(t)=min{max{{tilde over (p)}m+1,i(t), lm+1,i}um+1,i} if i∈
R2pm+1,i(t)={tilde over (p)}m+1,i(t) if i∉
R2(d) a module that transforms pM(t) into the coordinate system of F1;
{tilde over (p)}1(t+1)=F1FM−
1pM(t)=FM,1pM(t)(e) a module that projects {tilde over (p)}1(t+1) onto F1P1;
p1,i(t+1)=min{max{{tilde over (p)}1,i(t+1), l1,i}, u1,i} if i∈
R1p1,i(t+1)={tilde over (p)}1,i(t+1) if i∉
R1(l) a module that checks for convergence, and if ∥
pn(t+1)−
pn(t)∥
2 >
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)}=Fn−
1pn(t+1);
wherein;
F1 through FM are each K×
K transforms,M is an integer larger than 1, each Fm−
1 is the inverse transform of Fm,ŷ
1 is a quantized version of y1, such that ŷ
1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦
ŷ
1≦
u1 and each ŷ
m componentwise lies between respective lower and upper quantization cell boundary vectors lm≦
ŷ
m≦
um,R1⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
1, and for each m, Rm⊂
{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 F1P;
(c) transforming p1(t) into the coordinate system of F2;
(d) projecting p2(t) onto F2Q;
(e) transforming q2(t+1) into the coordinate system of F1;
(f) projecting q1(t+1) onto F1P;
(g) checking for convergence and if not sufficiently converged then iterating (c) through (g); and
(h) reconstructing {circumflex over (x)}=F1−
1p1(t+1) wherein;
F1 and F2 are each K×
K transforms.- View Dependent Claims (31, 32, 33)
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 p1(0) such that for each index i, p1,i(0)=ŷ
1,i if i∈
R1 andp1,i(0)=0 if i∉
R1;
(c) transforming p1(t) further includes transforming p1(t) into the coordinate system of F2 using p2(t)=F2(F1−
1p1(t))=F12p1(t);
(d) projecting p2(t) further includes projecting p2(t) onto F2Q such that for each index i;
q2,i(t+1)=min{max{p2,i(t),l2,i},u2,i} if i∈
R2 andq2,i(t+)=p2,i(t) if i∉
R2;
(e) transforming q2(t+1) further includes transforming q2(t+1) into the coordinate system of F1 using q1(t+1)=F1(F2−
1q2(t+1))=F21q2(t+1);
(f) projecting q1(t+1) further includes projecting q1(t+1) onto F1P such that for each index i;
p1,i(t+1)=min{max{q1,i(t+1),l1,i},u1,i} if i∈
R1 andp1,i(t+1)=p2,i(t) if i∉
R1; and
(g) checking further includes checking for convergence by testing ∥
p1(t+1)−
p1(t)∥
2>
ε
, and if so then setting t←
t+1 and iterating (c) through (g).and wherein;
F1 and F2 are each K×
K transforms,F1−
1is the inverse transform of F1, F2−
1 is the inverse transform of F2,ŷ
1 is a quantized version of y1, ŷ
2 is a quantized version of y2, such that ŷ
1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦
ŷ
1≦
u1 and ŷ
2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦
ŷ
2≦
u2,R1⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
1, andR2⊂
{1, . . . , K} is the set of indices of the descriptions received of ŷ
2.
-
-
33. The method of claim 30, wherein the (a) initializing t, (b) setting an initial point in F1P, (c) transforming p1(t) into the coordinate system of F2, (d) projecting p2(t) onto F2Q, (e) transforming q2(t+1) into the coordinate system of F1, (f) projecting q1(t+1) onto F1P, (g) checking for convergence and if not sufficiently converged then iterating (c) through (g);
- and (h) reconstructing {circumflex over (x)}=F1−
1p1(t+1) are performed in the order listed.
- and (h) reconstructing {circumflex over (x)}=F1−
Specification