Transcript Document

Distilled Sensing: Selective Sampling for
Sparse Signal Recovery
by
Jarvis Haupt, Rui Castro, and Robert Nowak
(International Conference on Artificial Intelligence and Statistics, 2009)
Presented by Lihan He
ECE, Duke University
April 16, 2009
Outline
Introduction
Sparse recovery by non-adaptive sensing
Distilled sensing
Main theorems
Experimental results
Conclusion
2/14
Introduction
Sparse signal recovery problem
 n is very large
 Signal
 Most of the components
are zero – sparse signal
 Objective: Identifying the locations of the non-zero components
based on the data X={X1, …, Xn}
4
2
0
-2
-4
0
100
200
300
400
500
600
700
800
900
1000
3/14
Introduction
Existing method:
 False-discovery rate (FDR) analysis [Benjamini and Hochberg, 1995]
 Cannot recover weak signals
In this paper:
Given a collection of noisy observations of the components of a sparse vector, it
is far easier to identify a large set of null components (where the signal is absent)
than it is to identify a small set of signal components.
 A sequential adaptive sensing procedure
 Taking multiple “looks”
 At each look, finding out the locations where the signal is probably not
present, and focusing sensing resources into the remaining locations for
the next look
 Can recover very weak signals than non-adaptive methods
4/14
Non-Adaptive Sensing
FDP and NDP
Define
is the estimated S from a given signal recovery procedure
False discovery proportion
number of false
discovered components
Non-discovery proportion
total number of
discovered components
NDP =
number of
undiscovered
components
total number of
signal components
5/14
Non-Adaptive Sensing
Recovery procedure
Considering sparse signals have
signal components, each of amplitude
, for some
, and r > 0.
Consider a coordinate-wise thresholding procedure
to estimate the locations of the signal components.
Previous research [Abramovich et al., 2006] shows that
if r>β, with a threshold τ that may depend on r, β and n, the procedure drives
both the FDP and NDP to zero simultaneously with probability tending to one
as n→∞. Conversely, if r<β, no such coordinate-wise thresholding procedure
can drive the FDP and NDP to zero simultaneously with probability tending to
one as n→∞.
Requiring that the nonzero components obey
6/14
Distilled Sensing
Allowing multiple observations, indexed by j
with the restriction
, limiting the sensing energy.
 Adaptive, sequential designs of

depends explicitly on the past
 Iteratively allocate more sensing resources to locations that are most
promising while ignoring locations that are unlikely to contain signal
components
7/14
Distilled Sensing
assuming signal is positive
Each distillation step retains almost all of the locations corresponding to
signal components, but only about half of the locations corresponding to
null components.
8/14
Distilled Sensing
Truth
First observation
Distillation
Second observation
Source: http://homepages.cae.wisc.edu/~jhaupt/ds.html
9/14
Main Theorems
Define energy allocation strategy
Requiring that the nonzero components obey i  2 log n /(2  ) k 1
10/14
Main Theorems
Given k above, only requiring that the nonzero components obey
11/14
Experiments
Astronomical survey
256 x 256 pixels; 533 pixels have nonzero amplitude of 2.98 (β=0.43, r=0.4)
Truth
Recovered by nonadaptive sensing
Noisy observation
Recovered by
distilled sensing
(Δ=0.9, k=5)
12/14
Experiments
10 independent trials
Solid: non-adaptive sensing
Dashed: distilled sensing
13/14
Conclusion
 Proposed a sequential adaptive sensing procedure – distilled sensing
 Recover sparse signal in noise
 Iteratively focus sensing resources towards the signal subspace
containing nonzero components
 Can recover dramatically weaker sparse signals compared with
traditional non-adaptive sensing procedure
14/14