Method and Apparatus for Signal Detection, Classification and Estimation from Compressive Measurements

• US 20080228446A1
• Filed: 10/25/2006
• Published: 09/18/2008
• Est. Priority Date: 10/25/2005
• Status: Active Grant

• Current Assignee: Rice University
• Original Assignee: Rice University
• Inventors: Wakin, Michael B., Duarte, Marco F., Davenport, Mark A., Baraniuk, Richard G
• Granted Patent: US 8,483,492 B2
• Time in Patent Office: Days
• US Class Current: 702/189
• CPC Class Codes: G06F 18/21375 involving differential geometry, e.g. embedding of pattern manifold
• CPC Class Codes: G06F 2218/08 Feature extraction
• CPC Class Codes: G06F 2218/12 Classification; Matching
• CPC Class Codes: G06V 10/52 Scale-space analysis, e.g. wavelet analysis multi-scale boundary representations G06V10/42
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Abstract

The recently introduced theory of Compressive Sensing (CS) enables a new method for signal recovery from incomplete information (a reduced set of “compressive” linear measurements), based on the assumption that the signal is sparse in some dictionary. Such compressive measurement schemes are desirable in practice for reducing the costs of signal acquisition, storage, and processing. However, the current CS framework considers only a certain task (signal recovery) and only in a certain model setting (sparsity).

We show that compressive measurements are in fact information scalable, allowing one to answer a broad spectrum of questions about a signal when provided only with a reduced set of compressive measurements. These questions range from complete signal recovery at one extreme down to a simple binary detection decision at the other. (Questions in between include, for example, estimation and classification.) We provide techniques such as a “compressive matched filter” for answering several of these questions given the available measurements, often without needing to first reconstruct the signal. In many cases, these techniques can succeed with far fewer measurements than would be required for full signal recovery, and such techniques can also be computationally more efficient. Based on additional mathematical insight, we discuss information scalable algorithms in several model settings, including sparsity (as in CS), but also in parametric or manifold-based settings and in model-free settings for generic statements of detection, classification, and estimation problems.

Claims

1. A method for estimating the value of a function ƒ

of an unknown signal x from compressive measurements of said unknown signal x, the method comprising the steps of;

(a) obtaining compressive measurements of an unknown signal x, and

(b) determining a value of a function ƒ

most consistent with said obtained compressive measurements.

2. A method for estimating the value of a function ƒ

of an unknown signal x according to claim 1, wherein said determining step comprises generating an estimate of x.

12. A method as in claim 1 in which the resulting decision is used to select an appropriate basis for a full reconstruction of the signal.

3. A method for determining which among a plurality of candidate signal models is most consistent with a signal x using a set of compressive measurements of said signal x, the method comprising the steps of:

(a) obtaining a set of compressive measurements of a signal x; and

(b) comparing said set of compressive measurements to measurements one would expect under various candidate signal models.

4. A method for determining which among a plurality of candidate signal models is most consistent with a signal x according to claim 3, wherein said comparing step comprises comparing said set of compressive measurements with every candidate signal model.

5. A method for determining which among a plurality of candidate signal models is most consistent with a signal x according to claim 3, wherein said comparing step comprises generating an estimate of x.

13. A method as in claim 3 in which the resulting decision is used to classify the signal into classes corresponding to the respective dictionaries.

15. A method for determining which among a plurality of candidate signal models is most consistent with a signal x according to claim 3, wherein an estimate of x is generated according to be most consistent with said compressive measurements under said most consistent signal model.

6. A method for estimating, from compressive measurements of a signal x, one or more unknown parameters θ

on which the signal x depends, the method comprising the steps of;

(a) obtaining compressive measurements of a signal x; and

(b) determining an appropriate value of θ

most consistent with said obtained compressive measurements.

7. A method according to claim 6, wherein said determining step comprises generating an estimate of x that is then used to estimate θ

.

8. A method for determining whether an unknown signal x is sparse or compressible in a known dictionary Ψ

from compressive measurements of said signal x, the method comprising the steps of;

(a) obtaining compressive measurements of a signal x; and

(b) determining whether said compressive measurements of said signal x are consistent with the signal x being sparse or compressible in the dictionary Ψ

; and

(c) applying some measure of the sparsity or compressibility to the estimate.

9. A method according to claim 8, wherein said determining step comprises attempting to obtain a rough reconstruction of the Signal x using the dictionary Ψ

.

11. A method according to claim 9, wherein said determining step comprises attempting to obtain a rough reconstruction of the signal x using each dictionary Ψ

_i.

10. A method for determining which dictionary from among a plurality of dictionaries Ψ

_i an unknown signal x yields the most sparse or compressible representation of the signal x, the method comprising the steps of;

(a) obtaining compressive measurements of a signal x,

(b) determining how consistent said compressive measurements of said signal x are with the signal x being sparse or compressible in each dictionary Ψ

_i by estimating a set of expansion coefficients in each dictionary consistent with generating said compressive measurements; and

applying some measure of sparsity or compressibility to said estimated expansion coefficients in each dictionary; and

(c) selecting a dictionary Ψ

_j that is most consistent with the compressive measurements of the signal x and the simultaneous assumption that the signal x is sparse in that dictionary.

14. A method for estimating a the value of a function ƒ

of an unknown signal x, determining which among a which among a plurality of candidate signal models is most consistent with the signal x, or determining whether the signal x is sparse or compressible in a known dictionary Ψ

from compressive measurements of said signal x in the case where said signal x is contaminated with interference, the method comprising the steps of;

(a) obtaining compressive measurements of a signal x;

(b) using a model for a structure of interference contaminating said signal x to obtain an estimate of the interference, and

(c) estimating the value of the function ƒ

(x) of said signal x, determining a signal model most consistent with the compressive measurements of said signal x, or determining whether the signal x is sparse or compressible in a known dictionary Ψ

.

16. A method for estimating the value of an unknown signal X from compressive measurements of one or more signals x_i that depend on the value of X, the method comprising the steps of:

(a) obtaining compressive measurements each signal x_i, and

(b) determining a value of X most consistent with said obtained compressive measurements.

17. A method for estimating the value of an unknown signal X from compressive measurements of one or more signals x_i according to claim 16, wherein the dependence of the signals x_i on the value X is known explicitly.

18. A method for estimating the value of an unknown signal X from compressive measurements of one or more signals x_i according to claim 17, wherein said determining step comprises generating an estimate of each x_i, from which the value X is then determined as to be most consistent with said estimates of each x_i.

19. A method for estimating the value of an unknown signal X from compressive measurements of one or more signals x_i according to claim 16, wherein the dependence of each signal x_i on the value X is known save for an unknown parameter collection θ

_i.

20. A method for estimating the value of an unknown signal X from compressive measurements of one or more signals x_i according to claim 19, wherein said determining step comprises generating an estimate of each x_i, from which the value X is then determined as to be most consistent with said estimates of each x_i.

21. A method for estimating the value of an unknown signal X from compressive measurements of one or more signals x_i according to claim 19, wherein said determining step comprises generating an estimate of each θ

_i and x_i, from which the value X is then determined as to be most consistent with said estimates of each x_i under said estimates of parameters θ

_i.