Simple bounds for recovering low-complexity models
From MaRDI portal
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.
Recommendations
Cites work
- A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers
- Adaptive estimation of a quadratic functional by model selection.
- Compressed sensing
- Counting faces of randomly projected polytopes when the projection radically lowers dimension
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Exact matrix completion via convex optimization
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- scientific article; zbMATH DE number 4061904 (Why is no real title available?)
- scientific article; zbMATH DE number 3673370 (Why is no real title available?)
- Invertibility of symmetric random matrices
- Local operator theory, random matrices and Banach spaces.
- On Sparse Representations in Arbitrary Redundant Bases
- Probability Inequalities for Sums of Bounded Random Variables
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- The convex geometry of linear inverse problems
- Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
Cited in
(42)- Improved bounds for sparse recovery from subsampled random convolutions
- Sparse power factorization: balancing peakiness and sample complexity
- Super-resolution of positive sources on an arbitrarily fine grid
- Necessary and sufficient conditions of solution uniqueness in 1-norm minimization
- On model selection consistency of regularized M-estimators
- Nonuniform sparse recovery with subgaussian matrices
- Convex cardinal shape composition
- Low complexity regularization of linear inverse problems
- A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries
- Sparse signal recovery from quadratic measurements via convex programming
- Sparse recovery with pre-Gaussian random matrices
- Sharp MSE bounds for proximal denoising
- Typical l₁-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices
- On sparse reconstruction from Fourier and Gaussian measurements
- New bounds for RIC in compressed sensing
- Model selection with low complexity priors
- Scaling law for recovering the sparsest element in a subspace
- Error bounds for sparse and low-rank matrix approximation based on restricted isometric properties
- On uniqueness guarantees of solution in convex regularized linear inverse problems
- Computational complexity versus statistical performance on sparse recovery problems
- High-dimensional dynamic systems identification with additional constraints
- scientific article; zbMATH DE number 7583424 (Why is no real title available?)
- On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery
- Decomposable norm minimization with proximal-gradient homotopy algorithm
- Dual extrapolation for sparse GLMs
- Adaptive rates for total variation image denoising
- Living on the edge: phase transitions in convex programs with random data
- Sparse recovery under weak moment assumptions
- Non-convex matrix completion and related problems via strong duality
- Sparse recovery from extreme eigenvalues deviation inequalities
- Lower bounds for sparse recovery
- On two random models in data analysis
- Lower bounds for adaptive sparse recovery
- A Unified Recovery of Structured Signals Using Atomic Norm
- A theory of optimal convex regularization for low-dimensional recovery
- Hierarchical Bayesian inverse problems: a high-dimensional statistics viewpoint
- Solution uniqueness of convex optimization problems via the radial cone
- Stable recovery of regularized linear inverse problems
- Geometric characterizations of Lipschitz stability for convex optimization problems
- A data-dependent regularization method based on the graph Laplacian
- Sparse disjointed recovery from noninflating measurements
- A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery
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)
