METHOD AND APPARATUS FOR COMPRESSED SENSING

• US 20120082344A1
• Filed: 12/12/2011
• Published: 04/05/2012
• 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: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Inventors: DONOHO, David Leigh
• Granted Patent: US 8,855,431 B2
• Time in Patent Office: Days
• US Class Current: 382/103
• 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, approximate reconstruction x^# of x is possible. This embodiment is driven by the goal of promoting the approximate sparsity of x^#.

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.

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 x₁, x₂, . . . x_T, 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 x₁, x₂, x₃, 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 x_j of said digital signal or image is represented as a vector with m_j entries, a processor making measurements y comprising a vector with only n_j entries, where n_j is less than m_j; and

from n_i measurements, given a CS matrix A_j, said CS matrix A_j represented as a matrix product A_j=B where B is a known transform such that B_ix_j is a vector which can be well-approximated by a relatively small number of large-amplitude entries, with remaining entries relatively small in amplitude, and

where U_i is a matrix that stably recovers at least one sparse vector from low-dimensional data;

a processor producing an approximate reconstruction of said m_i-vector x_j.