2014

Convex recovery of a structured signal from independent random linear measurements

Tropp, Joel A.

Understand

This chapter develops a theoretical analysis of the convex programming method for recovering a structured signal from independent random linear measurements.

This technique delivers bounds for the sampling complexity that are similar with recent results for standard Gaussian measurements, but the argument applies to a much wider class of measurement ensembles.
To demonstrate the power of this approach, the paper presents a short analysis of phase retrieval by trace-norm minimization.
The key technical tool is a framework, due to Mendelson and coauthors, for bounding a nonnegative empirical process.

Built on

On general minimax theorems
M. Sion · 1958
Earlier work this paper cites.
Convex Analysis
R. T. Rockafellar · 1970
Earlier work this paper cites.
Some inequalities for Gaussian processes and applications
Y. Gordon · 1985
Earlier work this paper cites.
Asymptotic theory of finite-dimensional normed linear spaces
V. Milman and G. Schechtman · 1986
Earlier work this paper cites.
On Milman’s inequality and random subspaces which escape through a mesh in 𝐑 n {\bf R}^{n}
Y. Gordon · 1988
Earlier work this paper cites.
The Volume of Convex Bodies and Banach Space Geometry
G. Pisier · 1989
Earlier work this paper cites.
Probability in Banach Spaces: Isoperimetry and Processes
M. Ledoux and M. Talagrand · 1991
Earlier work this paper cites.
Characterization of the subdifferential of some matrix norms
Original
G. A. Watson · 1992
Earlier work this paper cites.
On the best constant in the Khinchin-Kahane inequality
R. Latała and K. Oleszkiewicz · 1994
Earlier work this paper cites.
Weak convergence and empirical processes
A. W. van der Vaart and J. A. Wellner · 1996
Earlier work this paper cites.
Local operator theory, random matrices and Banach spaces
K. R. Davidson and S. J. Szarek · 2001
Earlier work this paper cites.
Matrix rank minimization with applications
M. Fazel · 2002
Earlier work this paper cites.
The generic chaining
M. Talagrand · 2005
Earlier work this paper cites.

Similar

Random filters for compressive sampling and reconstruction
J. Tropp, M. Wakin, M. Duarte, D. Baron, and R. Baraniuk · 2006
Cited alongside, same era.
Reconstruction and subgaussian operators in asymptotic geometric analysis
S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann · 2007
Cited alongside, same era.
On sparse reconstruction from Fourier and Gaussian measurements
M. Rudelson and R. Vershynin · 2008
Cited alongside, same era.
Painless reconstruction from magnitudes of frame coefficients
R. Balan, B. G. Bodmann, P. G. Casazza, and D. Edidin · 2009
Cited alongside, same era.
Various thresholds for ℓ 1 \ell_{1} -optimization in compressed sensing
Original
M. Stojnic · 2009
Cited alongside, same era.
Empirical processes with a bounded ψ 1 \psi_{1} diameter
S. Mendelson · 2010
Cited alongside, same era.
New null space results and recovery thresholds for matrix rank minimization
Original
S. Oymak and B. Hassibi · 2010
Cited alongside, same era.
Recovering low-rank matrices from few coefficients in any basis
D. Gross · 2011
Cited alongside, same era.
The masked sample covariance estimator: An analysis via the matrix Laplace transform method
R. Y. Chen, A. Gittens, and J. A. Tropp · 2012
Cited alongside, same era.
The convex geometry of linear inverse problems
V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky · 2012
Cited alongside, same era.
Introduction to the non-asymptotic analysis of random matrices
R. Vershynin · 2012
Cited alongside, same era.
Concentration inequalities: A nonasymptotic theory of independence
S. Boucheron, G. Lugosi, and P. Massart · 2013
Cited alongside, same era.

Then

PhaseLift: exact and stable signal recovery from magnitude measurements via convex programming
E. J. Candès, T. Strohmer, and V. Voroninski · 2013
Later among the works it cites.
Bounding the smallest singular value of a random matrix without concentration
Original
V. Koltchinskii and S. Mendelson · 2013
Later among the works it cites.
A remark on the diameter of random sections of convex bodies
Original
S. Mendelson · 2013
Later among the works it cites.
Sharp MSE bounds for proximal denoising
Original
S. Oymak and B. Hassibi · 2013
Later among the works it cites.
Simple bounds for noisy linear inverse problems with exact side information
Original
S. Oymak, C. Thrampoulides, and B. Hassibi · 2013
Later among the works it cites.
Living on the edge: Phase transitions in convex programs with random data
Original
D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp · 2014
Closest in time.
Geometrizing local rates of convergence for linear inverse problems
Original
T. T. Cai, T. Liang, and A. Rakhlin · 2014
Closest in time.
Corrupted sensing: Novel guarantees for separating structured signals
R. Foygel and L. Mackey · 2014
Closest in time.
Compressed sensing under weak moment assumptions
Original
G. Lecué and S. Mendelson · 2014
Closest in time.
Learning without concentration
Original
S. Mendelson · 2014
Closest in time.
Learning without concentration for general loss functions
Original
S. Mendelson · 2014
Closest in time.
Simple error bounds for regularized noisy linear inverse problems
Original
C. Thrampoulides, S. Oymak, and B. Hassibi · 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…