Method and apparatus for compressed sensing

A computer implemented method for constructing special measurement matrices (CS-matrices) for use with a compressed sensing scheme, comprising the steps of:

• a processor generating a matrix B which sparsifies a content type of interest, wherein B comprises any of a discrete wavelet transform, a discrete Fourier transform, a discrete curvelet transform, discrete ridgelet transform, or other known mathematical transform, wherein for typical vectors x, a product θ=Bx is a vector which is nearly sparse;
• and
• a processor creating matrices A by the prescription A=UB, where U comprises one of the following types of matrices:
• random n by p matrices with independent entries, wherein such matrices have entries generated by a standard random number generator, wherein said random number generator comprises any of the following distributions:
• Gaussian/Normal distribution, wherein numbers are generated with a standard normal distribution having a probability density with a familiar bell-shaped curve;
• random signs, wherein numbers are +1 or −1 with equal probability;
• random sparse matrices, wherein numbers are +1 or −1 with probability π each, or 0 with probability 1-2π, wherein π is a parameter of the construction, and lies between 0 and ½;
• and
• random uniform numbers, wherein numbers are in the range −1 to 1 with equal density to every interval throughout this range;
• random orthoprojectors, wherein a matrix V is generated with standard normal entries, but in addition the rows of the matrix are orthogonalized by a standard procedure, producing a matrix U., said matrix U comprising an n-by-p matrix which offers an orthogonal projection from Rp to Rn;
• partial Fourier matrices, wherein an n by p matrix F is generated with n rows which are randomly sampled without replacement from among the p rows of the orthogonal p by p Fourier matrix;
• and
• partial Hadamard matrices, wherein an n by p matrix H is generated with n rows which are randomly sampled without replacement from among the p rows of the orthogonal p by p Hadamard matrix;
• and
• a processor using said matrices to produce an approximate reconstruction of a digital signal or image.

A computer implemented method for verifying special measurement matrices (CS-matrices) for use with a compressed sensing scheme, comprising the steps of:

• a processor applying a sparsity-promoting reconstruction algorithm to obtain an approximate reconstruction of x from a reduced-dimensionality measurement y;
• a processor producing a sparse or nearly-sparse approximate solution when there exists a solution x such that θ=Bx is nearly sparse;
• wherein said sparsity-promoting reconstruction algorithm comprises any of I1 minimization, I1 penalization, stepwise fitting, stagewise fitting, alternating projection methods, and Bayesian Modeling;
• and
• a processor using said matrices to produce an approximate reconstruction of a digital signal or image.

A computer implemented method for reconstructing a vector x representing compressible signals of interest, based on a vector y comprising n>m measurements produced by a compressed sensing scheme, comprising the steps of:

• a processor taking n traditional measurements to obtain x;
• a processor applying a standard orthogonal transform B;
• a processor compressing a measured vector x to a nearly sparse vector by said matrix B, where Bx is a vector which can be well-approximated by a relatively small number of large-amplitude entries, with remaining entries relatively small in amplitude;
• a processor delivering among approximate solutions y =Ax+e, an approximate solution x# for which B x# is sparse or nearly sparse;
• a processor applying post processing filtering to reduce a noise level;
• and
• a processor producing an approximate reconstruction of a digital signal or image.