Method and apparatus for compressed sensing

• US 7,646,924 B2
• Filed: 08/08/2005
• Issued: 01/12/2010
• Est. Priority Date: 08/09/2004
• Status: Active Grant

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: David Leigh Donoho
• Inventors: Donoho, David Leigh
• Primary Examiner(s): Kim; Charles
• Assistant Examiner(s): Koziol; Stephen R
• Application Number:
  US11/199,675
• Publication Number:
  US 20060029279A1
• Time in Patent Office: 1,618 Days
• Field of Search: 382/298, 382/232, 341/87, 341/50, 706/20, 375/148, 342/357.12
• US Class Current: 382/232
• CPC Class Codes: G06F 18/2136 based on sparsity criteria, e.g. with an overcomplete basis
• CPC Class Codes: G06F 2218/06 by applying a scale-space analysis, e.g. using wavelet analysis
• CPC Class Codes: G06F 2218/22 Source localisation; Inverse modelling
• CPC Class Codes: G06T 11/005 Specific pre-processing for tomographic reconstruction, e.g. calibration, source positioning, rebinning, scatter correction, retrospective gating
• CPC Class Codes: G06T 2207/20056 Discrete and fast Fourier transform, [DFT, FFT]
• CPC Class Codes: G06T 2207/20064 Wavelet transform [DWT]
• CPC Class Codes: H04N 19/86 involving reduction of coding artifacts, e.g. of blockiness

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, x^# of x is possible. This embodiment is driven by the goal of promoting the approximate sparsity of x^#.

Claims

1. A computer implemented method for designing special measurement matrices (CS-matrices) for use in compressed sensing, comprising the steps of:

a processor generating a CS matrix A as a matrix product A=U B where B is p by m and U is n by p;

a processor generating said matrix B with the property that, for objects of interest, Bx is sparse or is approximately a sparse vector, wherein B is an orthogonal matrix; and

a processor generating said matrix U as an n by p matrix with the properties that;

(1) the columns of U are of unit length in the Euclidean norm;

(2) the square matrix G=U′

U, where U′

denotes the transpose (real-valued matrix entries) or the conjugate transpose (complex-valued matrix entries), has its off-diagonal entries bounded in absolute value by the coherence parameter M; and

a processor using said matrices to produce an approximate reconstruction of a digital signal or image.

2. The computer implemented method of claim 1:

wherein p is equal to m, so that B is a square matrix.

3. The computer implemented method of claim 1:

wherein said B factor is a matrix representation of a known digital transform, comprising any of a wavelet, Fourier, and subband transforms.

4. The computer implemented method of claim 1:

wherein said U factor is part of a known transform, comprising any of a selection of a subset of n rows of a known p times p matrix.

5. 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 R^p to Rⁿ;

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.

6. 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 I₁ minimization, I₁ 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.

7. 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.