Simple bounds for recovering low-complexity models
From MaRDI portal
Publication:378116
DOI10.1007/S10107-012-0540-0zbMATH Open1278.15038arXiv1106.1474OpenAlexW2008997396MaRDI QIDQ378116FDOQ378116
Authors: Benjamin Recht, Emmanuel J. Candès 
Publication date: 11 November 2013
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: This note presents a unified analysis of the recovery of simple objects from random linear measurements. When the linear functionals are Gaussian, we show that an s-sparse vector in R^n can be efficiently recovered from 2s log n measurements with high probability and a rank r, n by n matrix can be efficiently recovered from r(6n-5r) with high probability. For sparse vectors, this is within an additive factor of the best known nonasymptotic bounds. For low-rank matrices, this matches the best known bounds. We present a parallel analysis for block sparse vectors obtaining similarly tight bounds. In the case of sparse and block sparse signals, we additionally demonstrate that our bounds are only slightly weakened when the measurement map is a random sign matrix. Our results are based on analyzing a particular dual point which certifies optimality conditions of the respective convex programming problem. Our calculations rely only on standard large deviation inequalities and our analysis is self-contained.
Full work available at URL: https://arxiv.org/abs/1106.1474
Recommendations
convex programmingdualityrandom matrices\(\ell _{1}\)-norm minimizationblock-sparsitylow-complexity modelsnuclear-norm minimization
Convex programming (90C25) Optimality conditions and duality in mathematical programming (90C46) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)
Cites Work
- Title not available (Why is that?)
- A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
- Probability Inequalities for Sums of Bounded Random Variables
- Exact matrix completion via convex optimization
- Local operator theory, random matrices and Banach spaces.
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
- Adaptive estimation of a quadratic functional by model selection.
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Compressed sensing
- On Sparse Representations in Arbitrary Redundant Bases
- Invertibility of symmetric random matrices
- The convex geometry of linear inverse problems
- Title not available (Why is that?)
- Counting faces of randomly projected polytopes when the projection radically lowers dimension
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
Cited In (36)
- High-dimensional dynamic systems identification with additional constraints
- Title not available (Why is that?)
- Sparse power factorization: balancing peakiness and sample complexity
- Living on the edge: phase transitions in convex programs with random data
- Necessary and sufficient conditions of solution uniqueness in 1-norm minimization
- Sparse recovery under weak moment assumptions
- Nonuniform sparse recovery with subgaussian matrices
- Lower bounds for sparse recovery
- Sparse signal recovery from quadratic measurements via convex programming
- Low complexity regularization of linear inverse problems
- Computational complexity versus statistical performance on sparse recovery problems
- Lower bounds for adaptive sparse recovery
- A Unified Recovery of Structured Signals Using Atomic Norm
- Non-convex matrix completion and related problems via strong duality
- On model selection consistency of regularized M-estimators
- Sparse recovery from extreme eigenvalues deviation inequalities
- Model selection with low complexity priors
- Convex cardinal shape composition
- New bounds for RIC in compressed sensing
- Sparse recovery with pre-Gaussian random matrices
- Super-resolution of positive sources on an arbitrarily fine grid
- Sparse disjointed recovery from noninflating measurements
- Sharp MSE bounds for proximal denoising
- Title not available (Why is that?)
- A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery
- Typical \(l_1\)-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices
- Error bounds for sparse and low-rank matrix approximation based on restricted isometric properties
- A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries
- On two random models in data analysis
- On uniqueness guarantees of solution in convex regularized linear inverse problems
- A theory of optimal convex regularization for low-dimensional recovery
- On sparse reconstruction from Fourier and Gaussian measurements
- Improved bounds for sparse recovery from subsampled random convolutions
- On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery
- Title not available (Why is that?)
- Decomposable norm minimization with proximal-gradient homotopy algorithm
This page was built for publication: Simple bounds for recovering low-complexity models
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q378116)
