RIPless compressed sensing from anisotropic measurements

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).

19 pages. To appear in Linear Algebra and its Applications, Special Issue on Sparse Approximate Solution of Linear Systems

References in corpus (4)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Discussion: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$
• Discussion: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$

Cited by in corpus (13)

• A Partial Derandomization of PhaseLift using Spherical Designs
• Improved Recovery Guarantees for Phase Retrieval from Coded Diffraction Patterns
• Bi-level Protected Compressive Sampling
• Infinite dimensional compressed sensing from anisotropic measurements and applications to inverse problems in PDE
• Modern compressive tomography for quantum information science
• Recoverability of Group Sparse Signals from Corrupted Measurements via Robust Group Lasso
• Anisotropic compressed sensing for non-Cartesian MRI acquisitions
• Privacy-Assured Outsourcing of Compressed Sensing Reconstruction Service in Cloud
• Discriminative reconstruction via simultaneous dense and sparse coding
• On the role of total variation in compressed sensing - structure dependence
• On the role of total variation in compressed sensing
• Unified Theory for Recovery of Sparse Signals in a General Transform Domain
• Predicting sparse circle maps from their dynamics