Consistent Basis Pursuit for Signal and Matrix Estimates in Quantized Compressed Sensing
Authors:
- 3 November 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Signal Processing Letters
- Vol. 23 (1) , 25-29
Abstract
This letter focuses on the estimation of low-complexity signals when they are observed through $M$ uniformly quantized compressive observations. Among such signals, we consider 1-D sparse vectors, low-rank matrices, or compressible signals that are well approximated by one of these two models. In this context, we prove the estimation efficiency of a variant of Basis Pursuit Denoise, called Consistent Basis Pursuit (CoBP), enforcing consistency between the observations and the re-observed estimate, while promoting its low-complexity nature. We show that the reconstruction error of CoBP decays like ${M^{ - 1/4}}$ when all parameters but $M$ are fixed. Our proof is connected to recent bounds on the proximity of vectors or matrices when (i) those belong to a set of small intrinsic “dimension”, as measured by the Gaussian mean width, and (ii) they share the same quantized (dithered) random projections. By solving CoBP with a proximal algorithm, we provide some extensive numerical observations that confirm the theoretical bound as $M$ is increased, displaying even faster error decay than predicted. The same phenomenon is observed in the special, yet important case of 1-bit CS.
Keywords
All Related Versions
Funding Information
- Walloon Region of Belgium
- Fonds De La Recherche Scientifique - FNRS
This publication has 27 references indexed in Scilit:
- Analysis-by-Synthesis Quantization for Compressed Sensing MeasurementsIEEE Transactions on Signal Processing, 2013
- One‐Bit Compressed Sensing by Linear ProgrammingCommunications on Pure and Applied Mathematics, 2013
- The Convex Geometry of Linear Inverse ProblemsFoundations of Computational Mathematics, 2012
- Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming ApproachIEEE Transactions on Information Theory, 2012
- Proximal Splitting Methods in Signal Processing2011
- Compressed Sensing With Quantized MeasurementsIEEE Signal Processing Letters, 2009
- Distortion-rate functions for quantized compressive sensing2009
- Optimal quantization of random measurements in compressed sensing2009
- Atomic Decomposition by Basis PursuitSIAM Journal on Scientific Computing, 1998
- Weak Convergence and Empirical Processes1996