2014

Structured random measurements in signal processing

Krahmer, Felix, Rauhut, Holger

Understand

Compressed sensing and its extensions have recently triggered interest in randomized signal acquisition.

A key finding is that random measurements provide sparse signal reconstruction guarantees for efficient and stable algorithms with a minimal number of samples.
While this was first shown for (unstructured) Gaussian random measurement matrices, applications require certain structure of the measurements leading to structured random measurement matrices.
Near optimal recovery guarantees for such structured measurements have been developed over the past years in a variety of contexts.

Built on

Phase retrieval algorithms: A comparison
J. R. Fienup · 1982
Earlier work this paper cites.
Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
B. Carl · 1985
Earlier work this paper cites.
Inégalités de Khintchine dans C p {C}_{p} ( 1 < p < ∞ ) (1<p<\infty)
F. Lust-Piquard · 1986
Earlier work this paper cites.
Probability in Banach Spaces
M. Ledoux and M. Talagrand · 1991
Earlier work this paper cites.
Atomic decomposition by Basis Pursuit
S. S. Chen, D. L. Donoho, and M. A. Saunders · 1999
Earlier work this paper cites.
Operator Khintchine inequality in non-commutative probability
A. Buchholz · 2001
Earlier work this paper cites.
Matrix rank minimization with applications
M. Fazel · 2002
Earlier work this paper cites.
Hybrid projection–reflection method for phase retrieval
H. H. Bauschke, P. L. Combettes, and D. R. Luke · 2003
Earlier work this paper cites.
The Generic Chaining
M. Talagrand · 2005
Earlier work this paper cites.
On signal reconstruction without phase
R. Balan, P. Casazza, and D. Edidin · 2006
Earlier work this paper cites.
Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
E. J. Candès, J. Romberg, and T. Tao · 2006
Earlier work this paper cites.
Stable signal recovery from incomplete and inaccurate measurements
E. J. Candès, J. Romberg, and T. Tao · 2006
Earlier work this paper cites.
Near optimal signal recovery from random projections: universal encoding strategies?
E. J. Candès and T. Tao · 2006
Earlier work this paper cites.
Compressed sensing
D. L. Donoho · 2006
Earlier work this paper cites.
Toeplitz-structured compressed sensing matrices
W. Bajwa, J. Haupt, G. Raz, S. Wright, and R. Nowak · 2007
Earlier work this paper cites.
Compressive sensing
R. G. Baraniuk · 2007
Earlier work this paper cites.
The Dantzig selector: statistical estimation when p p is much larger than n n
E. J. Candès and T. Tao · 2007
Earlier work this paper cites.
Sparse MRI: The application of compressed sensing for rapid MR imaging
M. Lustig, D. L. Donoho, and J. Pauly · 2007
Earlier work this paper cites.
Random sampling of sparse trigonometric polynomials
H. Rauhut · 2007
Earlier work this paper cites.
A simple proof of the restricted isometry property for random matrices
R. G. Baraniuk, M. Davenport, R. A. DeVore, and M. Wakin · 2008
Earlier work this paper cites.
An introduction to compressive sampling
E. J. Candès and M. Wakin · 2008
Earlier work this paper cites.
Single-Pixel Imaging via Compressive Sampling
M. Duarte, M. Davenport, D. Takhar, J. Laska, S. Ting, K. Kelly, and R. G. Baraniuk · 2008
Earlier work this paper cites.
Compressive coded aperture superresolution image reconstruction
R. F. Marcia and R. M. Willett · 2008
Earlier work this paper cites.
On the impossibility of uniform sparse reconstruction using greedy methods
H. Rauhut · 2008
Earlier work this paper cites.
Compressed sensing and redundant dictionaries
H. Rauhut, K. Schnass, and P. Vandergheynst · 2008
Earlier work this paper cites.
Imaging via Compressive Sampling
J. K. Romberg · 2008
Earlier work this paper cites.
On sparse reconstruction from Fourier and Gaussian measurements
M. Rudelson and R. Vershynin · 2008
Earlier work this paper cites.
Simultaneous analysis of lasso and Dantzig selector
P. Bickel, Y. Ritov, and A. Tsybakov · 2009
Earlier work this paper cites.
Exact matrix completion via convex optimization
E. J. Candès and B. Recht · 2009
Earlier work this paper cites.
Restricted isometry constants where ℓ p \ell^{p} sparse recovery can fail for 0 < p ≤ 1 0<p\leq 1
M. Davies and R. Gribonval · 2009
Earlier work this paper cites.
High-resolution radar via compressed sensing
M. Herman and T. Strohmer · 2009
Earlier work this paper cites.
CMOS compressed imaging by random convolution,
L. Jacques, P. Vandergheynst, A. Bibet, V. Majidzadeh, A. Schmid, and Y. Leblebici · 2009
Earlier work this paper cites.
Uniform uncertainty principle for Bernoulli and subgaussian ensembles
S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann · 2009
Earlier work this paper cites.
Circulant and Toeplitz matrices in compressed sensing
H. Rauhut · 2009
Earlier work this paper cites.
Compressive sensing by random convolution
J. K. Romberg · 2009
Earlier work this paper cites.
A singular value thresholding algorithm for matrix completion
J.-F. Cai, E. J. Candès, and Z. Shen · 2010
Earlier work this paper cites.

Similar

The power of matrix completion: near-optimal convex relaxation
E. J. Candès and T. Tao · 2010
Cited alongside, same era.
On compressive sensing applied to radar
J. Ender · 2010
Cited alongside, same era.
Compressed remote sensing of sparse objects
A. Fannjiang, P. Yan, and T. Strohmer · 2010
Cited alongside, same era.
Quantum state tomography via compressed sensing
D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert · 2010
Cited alongside, same era.
Toeplitz compressed sensing matrices with applications to sparse channel estimation
J. Haupt, W. Bajwa, G. Raz, and R. Nowak · 2010
Cited alongside, same era.
ADMiRA: Atomic decomposition for minimum rank approximation
Kiryung Lee and Y. Bresler · 2010
Cited alongside, same era.
Sparsity in time-frequency representations
G. E. Pfander, H. Rauhut · 2010
Cited alongside, same era.
Compressive Sensing and Structured Random Matrices
H. Rauhut · 2010
Cited alongside, same era.
Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
B. Recht, M. Fazel, and P. Parrilo · 2010
Cited alongside, same era.
Compressive sensing on a CMOS separable-transform image sensor
R. Robucci, J. Gray, L. K. Chiu, J. Romberg, and P. Hasler · 2010
Cited alongside, same era.
Improved pediatric MR imaging with compressed sensing
S. Vasanawala, M. Alley, B. Hargreaves, R. Barth, J. Pauly, and M. Lustig · 2010
Cited alongside, same era.
Generalized sampling and infinite dimensional compressed sensing
B. Adcock and A. C. Hansen · 2011
Cited alongside, same era.

Then

Restricted isometries for partial random circulant matrices
H. Rauhut, J. K. Romberg, and J. A. Tropp · 2012
Later among the works it cites.
A simpler approach to matrix completion
B. Recht · 2012
Later among the works it cites.
User-friendly tail bounds for sums of random matrices
J. A. Tropp · 2012
Later among the works it cites.
Introduction to the non-asymptotic analysis of random matrices
R. Vershynin · 2012
Later among the works it cites.
Breaking the coherence barrier: A new theory for compressed sensing
Original
B. Adcock, A. C. Hansen, C. Poon, and B. Roman · 2013
Later among the works it cites.
Compressive multiplexing of correlated signals
Original
A. Ahmed and J. Romberg · 2013
Later among the works it cites.
Phase retrieval from power spectra of masked signals
Original
A. S. Bandeira, Y. Chen, and D. G. Mixon · 2013
Later among the works it cites.
Phase retrieval via matrix completion
E. Candès, Y. Eldar, T. Strohmer, and V. Voroninski · 2013
Later among the works it cites.
Phase retrieval from coded diffraction patterns
Original
E. J. Candes, X. Li, and M. Soltanolkotabi · 2013
Later among the works it cites.
Variable density sampling with continuous sampling trajectories
Original
N. Chauffert, P. Ciuciu, J. Kahn, P. Weiss · 2013
Later among the works it cites.
Restricted isometry of Fourier matrices and list decodability of random linear codes
Original
M. Cheraghchi, V. Guruswami, and A. Velingker · 2013
Later among the works it cites.
Quasi-linear compressed sensing
Original
M. Fornasier, M. Ehler, and J. Sigl · 2013
Later among the works it cites.
A mathematical introduction to compressive sensing
S. Foucart and H. Rauhut · 2013
Later among the works it cites.
Analysis of sparse MIMO radar
T. Strohmer and B. Friedlander · 2013
Later among the works it cites.
Quantum tomography under prior information
T. Heinosaari, L. Mazzarella, and M. M. Wolf · 2013
Later among the works it cites.
Feasibility study for compressive multi-dimensional integral imaging
R. Horisaki, X. Xiao, J. Tanida and B. Javidi · 2013
Later among the works it cites.
Sparse recovery with random convolutions, 2013
D. James · 2013
Later among the works it cites.
Convolutional compressed sensing using deterministic sequences
K. Li, L. Gan, and C. Ling · 2013
Later among the works it cites.
Short, fat matrices
D. Mixon · 2013
Later among the works it cites.
Determination of all pure quantum states from a minimal number of observables
Original
D. Mondragon, V. Voroninski · 2013
Later among the works it cites.
Phase retrieval using alternating minimization
P. Netrapalli, P. Jain, and S. Sanghavi · 2013
Later among the works it cites.
The restricted isometry property for time-frequency structured random matrices
G. Pfander, H. Rauhut, and J. Tropp · 2013
Later among the works it cites.
Interpolation via weighted l1 minimization
Original
H. Rauhut and R. Ward · 2013
Later among the works it cites.
Normalized iterative hard thresholding for matrix completion
J. Tanner and K. Wei · 2013
Later among the works it cites.
Quantum tomography from few full-rank observables
Original
V. Voroninski · 2013
Later among the works it cites.
Phase retrieval with polarization
B. Alexeev, A. S. Bandeira, M. Fickus, and D. G. Mixon · 2014
Closest in time.
Sparse representation of a polytope and recovery of sparse signals and low-rank matrices
T. Cai and A. Zhang · 2014
Closest in time.
An algebraic characterization of injectivity in phase retrieval
A. Conca, D. Edidin, M. Hering, and C. Vinzant · 2014
Closest in time.
Stable optimizationless recovery from phaseless linear measurements
L. Demanet and P. Hand · 2014
Closest in time.
Phase retrieval: Stability and recovery guarantees
Y. Eldar and S. Mendelson · 2014
Closest in time.
Improved Recovery Guarantees for Phase Retrieval from Coded Diffraction Patterns
Original
D. Gross, F. Krahmer, and R. Kueng · 2014
Closest in time.
Remote sensing via ℓ 1 \ell_{1} -minimization
M. Hügel, H. Rauhut, and T. Strohmer · 2014
Closest in time.
Stable and robust sampling strategies for compressive imaging
F. Krahmer and R. Ward · 2014
Closest in time.
Matrix recipes for hard thresholding methods
A. Kyrillidis and V. Cevher · 2014
Closest in time.
GESPAR: Efficient Phase Retrieval of Sparse Signals
Y. Shechtman, A. Beck, Y.C. Eldar, · 2014
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…