RIPless compressed sensing from anisotropic measurements

DOI10.1016/J.LAA.2013.04.018zbMATH Open1332.94045arXiv1205.1423OpenAlexW2003870284MaRDI QIDQ2437334FDOQ2437334

Yanyan Li

Publication date: 3 March 2014

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: Compressed sensing is the art of reconstructing a sparse vector from its inner products with respect to a small set of randomly chosen measurement vectors. It is usually assumed that the ensemble of measurement vectors is in isotropic position in the sense that the associated covariance matrix is proportional to the identity matrix. In this paper, we establish bounds on the number of required measurements in the anisotropic case, where the ensemble of measurement vectors possesses a non-trivial covariance matrix. Essentially, we find that the required sampling rate grows proportionally to the condition number of the covariance matrix. In contrast to other recent contributions to this problem, our arguments do not rely on any restricted isometry properties (RIP's), but rather on ideas from convex geometry which have been systematically studied in the theory of low-rank matrix recovery. This allows for a simple argument and slightly improved bounds, but may lead to a worse dependency on noise (which we do not consider in the present paper).

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

Recommendations

• Compressed sensing: how sharp is the restricted isometry property?
• The restricted isometry property and its implications for compressed sensing
• An introduction to compressed sensing
• Sparse recovery under weak moment assumptions
• Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions

zbMATH Keywords

compressed sensingLASSOsparse regression\(\ell_1\) minimizationnon-commutative large deviation estimatesanisotropic ensemblesoperator Bernstein inequalitiesrestricted isometriesthe Dantzig selectorthe golfing scheme

Mathematics Subject Classification ID

Convex programming (90C25) Large deviations (60F10) Ridge regression; shrinkage estimators (Lasso) (62J07) Applications of mathematical programming (90C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)

Cites Work

• Simultaneous analysis of Lasso and Dantzig selector
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
• Title not available (Why is that?)
• Exact matrix completion via convex optimization
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Reconstruction From Anisotropic Random Measurements
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• A Probabilistic and RIPless Theory of Compressed Sensing
• On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
• Probabilistic methods for algorithmic discrete mathematics
• A remark on compressed sensing
• Title not available (Why is that?)
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators
• Strong converse for identification via quantum channels

Cited In (11)

• A partial derandomization of phaselift using spherical designs
• Convergence radius and sample complexity of ITKM algorithms for dictionary learning
• Sparse Model Uncertainties in Compressed Sensing with Application to Convolutions and Sporadic Communication
• Restricted isometries for partial random circulant matrices
• Low-rank matrix completion in a general non-orthogonal basis
• Robust group lasso: model and recoverability
• Extracting Sparse High-Dimensional Dynamics from Limited Data
• Modern compressive tomography for quantum information science
• Improved recovery guarantees for phase retrieval from coded diffraction patterns
• On the Role of Total Variation in Compressed Sensing
• Infinite dimensional compressed sensing from anisotropic measurements and applications to inverse problems in PDE

This page was built for publication: RIPless compressed sensing from anisotropic measurements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437334)