Home > A Survey of Compressive Sensing and Applications

A Survey of Compressive Sensing and Applications

 Page 1
A Survey of Compressive Sensing and Applications
Justin Romberg
Georgia Tech, School of ECE
ENS Winter School January 10, 2012 Lyon, France

 Page 2
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

 Page 3
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

 Page 4
Sense, sample, process...
sensor ��fast�� ADC data compression

 Page 5
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

 Page 6
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

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

 Page 8
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∗

 Page 9
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

 Page 10
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)

 Page 11
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

 Page 12
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

 Page 13
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

 Page 14
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

 Page 15
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��

 Page 16
Sparsity/Compressibility
pixels large wavelet coefficients wideband signal samples large Gabor coefficients
time fre q u e n c y

 Page 17
Wavelet approximation
Take 1% of largest coefficients, set the rest to zero (adaptive) original approximated rel. error = 0.031

 Page 18
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 = ,

 Page 19
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 = ,

 Page 20
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 = ,

All Rights Reserved Powered by Free Document Search and Download

Copyright © 2011
This site does not host pdf,doc,ppt,xls,rtf,txt files all document are the property of their respective owners. complaint#nuokui.com