METHOD AND APPARATUS FOR COMPRESSED SENSING
First Claim
1. 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 known 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.
1 Assignment
0 Petitions
Accused Products
Abstract
Method and apparatus for compressed sensing yields acceptable quality reconstructions of an object from reduced numbers of measurements. A component x of a signal or image is represented as a vector having m entries.
Measurements y, comprising a vector with n entries, where n is less than m, are made. An approximate reconstruction of the m-vector x is made from y. Special measurement matrices allow measurements y=Ax+z, where y is the measured m-vector, x the desired n-vector and z an m-vector representing noise. “A” is an n by m matrix, i.e. an array with fewer rows than columns. “A” enables delivery of an approximate reconstruction, x#′ of x. An embodiment discloses approximate reconstruction of x from the reduced-dimensionality measurement y. Given y, and the matrix A, approximate reconstruction x# of x is possible. This embodiment is driven by the goal of promoting the approximate sparsity of x#.
-
Citations
3 Claims
-
1. 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 known 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.
- m measurements produced by a compressed sensing scheme, comprising the steps of;
-
2. 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.
-
-
3. A method for sub-band sensing, where an object of interest x comprises a concatenation of several objects x1, x2, x3, comprising the steps of:
-
a processor applying a different compressed sensing measurement scheme for each one of said objects; for each object, in a scheme where a component xj of said digital signal or image is represented as a vector with mj entries, a processor making measurements y comprising a vector with only nj entries, where nj is less than mj; and
from ni measurements, given a CS matrix Aj, said CS matrix Aj represented as a matrix product Aj=B where B is a known transform such that Bixj is a vector which can be well-approximated by a relatively small number of large-amplitude entries, with remaining entries relatively small in amplitude, andwhere Ui is a matrix that stably recovers at least one sparse vector from low-dimensional data; a processor producing an approximate reconstruction of said mi-vector xj.
-
Specification