Home > A Survey of Compressive Sensing and Applications

Page 1 |

Justin Romberg

Georgia Tech, School of ECE

ENS Winter School January 10, 2012 Lyon, France

Page 2 |

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 |

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 |

sensor ��fast�� ADC data compression

Page 5 |

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

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 |

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 |

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 |

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 |

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 |

Resolutions N = 256,512,1024 (black, blue, red) Signal composed of S randomly selected sinusoids Sample at M randomly selected locations % success

S/M In practice, perfect recovery occurs when M �� 2S for N �� 1000

Page 13 |

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 |

minx x 2 s.t. ��x = y minx x 1 s.t. ��x = y

Works

n if

Page 15 |

=

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 |

pixels large wavelet coefficients wideband signal samples large Gabor coefficients

time fre q u e n c y

Page 17 |

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

Page 18 |

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 |

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 |

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

- Classification of Minerals by Anionic Species How would you organize some 5000 species of minerals? Chemical Classification of M
- Advanced Placement Chemistry: 1987 Free Response Answers
- BCA Protein Assay Reagent Kit
- บทที่ 6
- CityRail: A system on the brink
- LESSON PLAN ASSIGNMENT
- Identification of Some Active Proteins in the Process of Hen Eggshell Formation†
- MINUTA DE RESOLUÇÃO
- THE ROLE OF OBSTACLES IN LEADERSHIP FORMATION
- wyklady z ortopedii
- LES VIOLENCES AU SEIN DU COUPLE
- Writing a Critical Essay about Literature
- For teachers and other school employees who suffer injuries related to indoor air quality problems in school facilities, worke
- Importing Personal Property Into Ghana
- STARBUCKS 9331337 姚嘉寧 9331376 吳幸儒 9331373 曾琬琇 Background Began in 1971 First Store – in Seattle The Branches
- TERZA DOMENICA DEL TEMPO ORDINARIO
- Cota Mestrado 2009
- Criminology & Criminal Justice Studies is the sociology-based study of crime and the criminal justice system.
- Impact of the New Title I Requirements on Charter Schools (PDF)
- Life Science Journal 2014;11(3) http://www.lifesciencesite.com 339 Patients' satisfaction about nurses' competency in prac
- AnnuAl report 2012/2013

- Different specific Position
- Special quality
- The dominant factor
- Culture
- Culture Industry
- the Legislation of the Culture Industry
- Earthquake resisting
- Welded connection
- Experimental research
- Damage analysis
- Calculation model
- Earth's gravity field
- Satellite gravity measurements
- CHAMP
- GPS
- Satellite perturbation motion
- Track Credits
- Geocentric motion
- Precise Orbit
- Bayes least squares estimation block
- Time changes in Earth's gravitational potential coefficients

All Rights Reserved Powered by Free Document Search and Download

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