A Survey of Compressive Sensing and Applications
Justin Romberg
Georgia Tech, School of ECE
ENS Winter School
January 10, 2012
Lyon, France
Signal processing trends
DSP: sample first, ask questions later
Explosion in sensor technology/ubiquity has caused two trends:
Physical capabilities of hardware are being stressed,
increasing speed/resolution becoming expensive
► gigahertz+ analog-to-digital conversion
► accelerated MRI
► industrial imaging
Deluge of data
► camera arrays and networks, multi-view target databases, streaming
video...
Compressive Sensing: sample smarter, not faster
Classical data acquisition
Shannon-Nyquist sampling theorem (Fundamental Theorem of DSP):
��if you sample at twice the bandwidth, you can perfectly reconstruct
the data��
time
space
Counterpart for ��indirect imaging�� (MRI, radar):
Resolution is determined by bandwidth
Sense, sample, process...
sensor
��fast�� ADC
data compression
Compressive sensing (CS)
Shannon/Nyquist theorem is pessimistic
► 2��bandwidth is the worst-case sampling rate —
holds uniformly for any bandlimited data
► sparsity/compressibility is irrelevant
► Shannon sampling based on a linear model,
compression based on a nonlinear model
Compressive sensing
► new sampling theory that leverages compressibility
► key roles played by new uncertainty principles and
randomness
Shannon
Heisenberg
Compressive sensing
��compressive��
sensor
��slow�� ADC
Essential idea:
��pre-coding�� the signal in analog makes it ��easier�� to acquire
Reduce power consumption, hardware complexity, acquisition time
A simple underdetermined inverse problem
Observe a subset Ω of the 2D discrete Fourier plane
phantom (hidden)
white star = sample locations
N := 512
2
= 262,144 pixel image
observations on 22 radial lines, 10,486 samples, �� 4% coverage
Minimum energy reconstruction
Reconstruct g∗ with
g∗(��1,��2) = (
ˆ
f(��1,��2) (��1,��2) �� Ω
0
(��1,��2) �� Ω
Set unknown Fourier coefis to zero, and inverse transform
original
Fourier samples
g∗
Total-variation reconstruction
Find an image that
Fourier domain: matches observations
Spatial domain: has a minimal amount of oscillation
Reconstruct g∗ by solving:
min
g ��
i,j
|(∇g)i,j| s.t. g(��1,��2) =ˆf(��1,��2), (��1,��2) �� Ω
original
Fourier samples
g∗ = original
perfect reconstruction
Sampling a superposition of sinusoids
We take M samples of a superposition of S sinusoids:
Time domain x0(t)
Frequency domain x0(��)
Measure M samples
S nonzero components
(red circles = samples)
Sampling a superposition of sinusoids
Reconstruct by solving
min
x
x 1
subject to x(tm) = x0(tm), m = 1,...,M
original x0, S = 15
perfect recovery from 30 samples
Numerical recovery curves
Resolutions N = 256,512,1024 (black, blue, red)
Signal composed of S randomly selected sinusoids
Sample at M randomly selected locations
% success
0
0.2
0.4
0.6
0.8
1
0
10
20
30
40
50
60
70
80
90
100
S/M
In practice, perfect recovery occurs when M �� 2S for N �� 1000
A nonlinear sampling theorem
Exact Recovery Theorem (Cand`es, R, Tao, 2004):
Unknown x0 is supported on set of size S
Select M sample locations 1tml ��at random�� with
M �� Const · S log N
Take time-domain samples (measurements) ym = x0(tm)
Solve
min
x x 1
subject to x(tm) = ym, m = 1,...,M
Solution is exactly f with extremely high probability
In total-variation/phantom example, S=number of jumps
Graphical intuition for l1
minx x 2 s.t. ��x = y
minx x 1 s.t. ��x = y
L Doesn��t Work hy
L
1
Works
n if
random orientation
Acquisition as linear algebra
=
resolution/
bandwidth
# samples
data
unknown
signal/image
acquisition
system
Small number of samples = underdetermined system
Impossible to solve in general
If x is sparse and �� is diverse, then these systems can be ��inverted��
Sparsity/Compressibility
pixels
large
wavelet
coefficients
wideband
signal
samples
large
Gabor
coefficients
time
fre
q
u
e
n
c
y
Wavelet approximation
Take 1% of largest coefficients, set the rest to zero (adaptive)
original
approximated
rel. error = 0.031
Linear measurements
Instead of samples, take linear measurements of signal/image x0
y1 = x0,��1 , y2 = x0,��2 , ...,yM = x0,��K
y = ��x0
Equivalent to transform-domain sampling,
1��ml = basis functions
Example: pixels
ym =
,
Linear measurements
Instead of samples, take linear measurements of signal/image x0
y1 = x0,��1 , y2 = x0,��2 , ...,yM = x0,��K
y = ��x0
Equivalent to transform-domain sampling,
1��ml = basis functions
Example: line integrals (tomography)
ym =
,
Linear measurements
Instead of samples, take linear measurements of signal/image x0
y1 = x0,��1 , y2 = x0,��2 , ...,yM = x0,��K
y = ��x0
Equivalent to transform-domain sampling,
1��ml = basis functions
Example: sinusoids (MRI)
ym =
,