Simple bounds for recovering low-complexity models

DOI10.1007/S10107-012-0540-0zbMath1278.15038arXiv1106.1474OpenAlexW2008997396MaRDI QIDQ378116

Benjamin Recht, Emmanuel J. Candès

Publication date: 11 November 2013

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1106.1474

zbMATH Keywords

dualityrandom matricesconvex programming\(\ell _{1}\)-norm minimizationblock-sparsitylow-complexity modelsnuclear-norm minimization

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Convex programming (90C25) Optimality conditions and duality in mathematical programming (90C46) Random matrices (algebraic aspects) (15B52)

Related Items (17)

Sharp MSE bounds for proximal denoising ⋮ Unnamed Item ⋮ High-dimensional dynamic systems identification with additional constraints ⋮ Model selection with low complexity priors ⋮ A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery ⋮ New bounds for RIC in compressed sensing ⋮ On uniqueness guarantees of solution in convex regularized linear inverse problems ⋮ On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery ⋮ Decomposable norm minimization with proximal-gradient homotopy algorithm ⋮ Necessary and sufficient conditions of solution uniqueness in 1-norm minimization ⋮ Convex Cardinal Shape Composition ⋮ Low Complexity Regularization of Linear Inverse Problems ⋮ Unnamed Item ⋮ Super-resolution of positive sources on an arbitrarily fine grid ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On model selection consistency of regularized M-estimators

Cites Work

• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Adaptive estimation of a quadratic functional by model selection.
• The convex geometry of linear inverse problems
• Exact matrix completion via convex optimization
• Counting faces of randomly projected polytopes when the projection radically lowers dimension
• On Sparse Representations in Arbitrary Redundant Bases
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• 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
• Probability Inequalities for Sums of Bounded Random Variables
• Invertibility of symmetric random matrices
• Compressed sensing
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Simple bounds for recovering low-complexity models