Method and apparatus for compressed sensing

A 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;
• and
• a processor applying post processing filtering to reduce a noise level.

A method for verifying in a compressed sensing (CS) scheme that a given matrix A offers compressed sensing, comprising the steps of:

• given a proposed matrix A, a processor generating a suite of trial signals x1, x2, . . . xT, representing typical signals;
• for each trial signal x, a processor generating a test dataset y=Ax (noiseless case) or y=Ax+z (noisy case);
• a processor running a sparsity-promoting reconstruction algorithm;
• a processor observing an output x# of said reconstruction algorithm;
• a processor checking either informally or by formal means that said output is of sufficiently high quality;
• wherein if said output is judged to be of sufficient quality, then a successful CS-system is obtained;
• and
• if not, a processor generating a new candidate CS matrix and evaluating using a same empirical testing approach;
• a processor repeating said method of generating and testing candidate CS matrices several times, if needed;
• and
• if, at a given (n,m) combination, a successful CS matrix A is not found, a processor then increasing the value of n and repeating the above steps.