User menu

Accès à distance ? S'identifier sur le proxy UCLouvain | Saint-Louis

Quantized Compressive Sensing with RIP Matrices: The Benefit of Dithering

Primary tabs

download
  • Open access
  • PDF
  • 973.44 K
Xu, Chunlei [UCL] Jacques, Laurent [UCL]

Quantized compressive sensing (QCS) deals with the problem of coding compressive measurements of low-complexity signals with quantized, finite precision representations, i.e., a mandatory process involved in any practical sensing model. While the resolution of this quantization clearly impacts the quality of signal reconstruction, there actually exist incompatible combinations of quantization functions and sensing matrices that proscribe arbitrarily low reconstruction error when the number of measurements increases. This work shows that a large class of random matrix constructions known to respect the restricted isometry property (RIP) is "compatible" with a simple scalar and uniform quantization if a uniform random vector, or a random dither, is added to the compressive signal measurements before quantization. In the context of estimating low-complexity signals (e.g., sparse or compressible signals, low-rank matrices) from their quantized observations, this compatibility is demonstrated by the existence of (at least) one signal reconstruction method, the projected back projection (PBP), whose reconstruction error decays when the number of measurements increases. Interestingly, given one RIP matrix and a single realization of the dither, a small reconstruction error can be proved to hold uniformly for all signals in the considered low-complexity set. We confirm these observations numerically in several scenarios involving sparse signals, low-rank matrices, and compressible signals, with various RIP matrix constructions such as sub-Gaussian random matrices and random partial discrete cosine transform (DCT) matrices.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès libre
Publication date 2019
Language Anglais
Journal information "Information and Inference" - (2019)
Peer reviewed yes
Publisher Oxford University Press (Oxford) (Oxford)
issn 2049-8764
Publication status Accepté/Sous presse
Affiliations UCL - SST/ICTM/ELEN - Pôle en ingénierie électrique
UCL - SST/ICTM/INMA - Pôle en ingénierie mathématique
Keywords compressive sensing ; quantization ; dithering ; sparse representation ; measure concentration ; random embedding
Links
  1. ADCOCK BEN, HANSEN ANDERS C., POON CLARICE, ROMAN BOGDAN, BREAKING THE COHERENCE BARRIER: A NEW THEORY FOR COMPRESSED SENSING, 10.1017/fms.2016.32
  2. Ai Albert, Lapanowski Alex, Plan Yaniv, Vershynin Roman, One-bit compressed sensing with non-Gaussian measurements, 10.1016/j.laa.2013.04.002
  3. Anitori Laura, Maleki Arian, Otten Matern, Baraniuk Richard G., Hoogeboom Peter, Design and Analysis of Compressed Sensing Radar Detectors, 10.1109/tsp.2012.2225057
  4. Ayaz Ulaş, Dirksen Sjoerd, Rauhut Holger, Uniform recovery of fusion frame structured sparse signals, 10.1016/j.acha.2016.03.006
  5. Baraniuk Richard, Davenport Mark, DeVore Ronald, Wakin Michael, A Simple Proof of the Restricted Isometry Property for Random Matrices, 10.1007/s00365-007-9003-x
  6. Baraniuk Richard G., Cevher Volkan, Duarte Marco F., Hegde Chinmay, Model-Based Compressive Sensing, 10.1109/tit.2010.2040894
  7. Baraniuk Richard G., Foucart Simon, Needell Deanna, Plan Yaniv, Wootters Mary, Exponential Decay of Reconstruction Error From Binary Measurements of Sparse Signals, 10.1109/tit.2017.2688381
  8. Blumensath Thomas, Davies Mike E., Iterative hard thresholding for compressed sensing, 10.1016/j.acha.2009.04.002
  9. Boufounos Petros T., Universal Rate-Efficient Scalar Quantization, 10.1109/tit.2011.2173899
  10. Boufounos Petros T., Baraniuk Richard G., 1-Bit compressive sensing, 10.1109/ciss.2008.4558487
  11. Boufounos Petros T., Jacques Laurent, Krahmer Felix, Saab Rayan, Quantization and Compressive Sensing, Compressed Sensing and its Applications (2015) ISBN:9783319160412 p.193-237, 10.1007/978-3-319-16042-9_7
  12. Boufounos Petros T, Rane Shantanu, Mansour Hassan, Representation and coding of signal geometry, 10.1093/imaiai/iax002
  13. Bussgang, Crosscorrelation functions of amplitude-distorted Gaussian signals (1952)
  14. Candès Emmanuel J, Plan Y, Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements, 10.1109/tit.2011.2111771
  15. Candès Emmanuel J., Romberg Justin K., Tao Terence, Stable signal recovery from incomplete and inaccurate measurements, 10.1002/cpa.20124
  16. Candes E.J., Tao T., Decoding by Linear Programming, 10.1109/tit.2005.858979
  17. Candes Emmanuel J., Tao Terence, Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?, 10.1109/tit.2006.885507
  18. Carrillo R. E., McEwen J. D., Wiaux Y., Sparsity Averaging Reweighted Analysis (SARA): a novel algorithm for radio-interferometric imaging : SARA for radio-interferometric imaging, 10.1111/j.1365-2966.2012.21605.x
  19. Chandrasekaran Venkat, Recht Benjamin, Parrilo Pablo A., Willsky Alan S., The Convex Geometry of Linear Inverse Problems, 10.1007/s10208-012-9135-7
  20. Cohen Albert, Dahmen Wolfgang, DeVore Ronald, Compressed sensing and best $k$-term approximation, 10.1090/s0894-0347-08-00610-3
  21. Dai Wei, Pham Hoa Vinh, Milenkovic Olgica, Distortion-rate functions for quantized compressive sensing, 10.1109/itwnit.2009.5158565
  22. Dattorro, Convex Optimization & Euclidean Distance Geometry (2005)
  23. Dirksen Sjoerd, Tail bounds via generic chaining, 10.1214/ejp.v20-3760
  24. Dirksen (2017)
  25. Donoho D.L., Compressed sensing, 10.1109/tit.2006.871582
  26. Ender Joachim H.G., On compressive sensing applied to radar, 10.1016/j.sigpro.2009.11.009
  27. Fazel (2002)
  28. Feng Joe-Mei, Krahmer Felix, Saab Rayan, Quantized compressed sensing for partial random circulant matrices, 10.1109/sampta.2017.8024436
  29. Feuillen Thomas, Xu Chunlei, Louveaux Jerome, Vandendorpe Luc, Jacques Laurent, Quantity over Quality: Dithered Quantization for Compressive Radar Systems, 10.1109/radar.2019.8835568
  30. Foucart Simon, Hard Thresholding Pursuit: An Algorithm for Compressive Sensing, 10.1137/100806278
  31. Foucart Simon, Rauhut Holger, A Mathematical Introduction to Compressive Sensing, ISBN:9780817649470, 10.1007/978-0-8176-4948-7
  32. Golbabaee Mohammad, Vandergheynst Pierre, Hyperspectral image compressed sensing via low-rank and joint-sparse matrix recovery, 10.1109/icassp.2012.6288484
  33. Gray R.M., Neuhoff D.L., Quantization, 10.1109/18.720541
  34. Gu Xiaoyi, Tu Shenyinying, Shi Hao-Jun Michael, Case Mindy, Needell Deanna, Plan Yaniv, Optimizing Quantization for Lasso Recovery, 10.1109/lsp.2017.2770018
  35. Güntürk C. S., Lammers M., Powell A. M., Saab R., Yılmaz Ö., Sobolev Duals for Random Frames and ΣΔ Quantization of Compressed Sensing Measurements, 10.1007/s10208-012-9140-x
  36. Huynh, Commun. Pure Appl. Math. (2018)
  37. Jacques, IEEE Trans. Inf. Theory, 62, 4696 (2016)
  38. Jacques, IEEE Trans. Inf. Theory, 63, 5477 (2017)
  39. Jacques Laurent, Cambareri Valerio, Time for dithering: fast and quantized random embeddings via the restricted isometry property, 10.1093/imaiai/iax004
  40. Jacques, 10th International Conference on Sampling Theory and Applications (SampTA 2013), 105 (2013)
  41. Jacques Laurent, Laska Jason N., Boufounos Petros T., Baraniuk Richard G., Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors, 10.1109/tit.2012.2234823
  42. Kamilov U. S., Goyal V. K., Rangan S., Message-Passing De-Quantization With Applications to Compressed Sensing, 10.1109/tsp.2012.2217334
  43. Keriven Nicolas, Bourrier Anthony, Gribonval Rémi, Pérez Patrick, Sketching for large-scale learning of mixture models, 10.1093/imaiai/iax015
  44. Klartag B., Mendelson S., Empirical processes and random projections, 10.1016/j.jfa.2004.10.009
  45. Knudson Karin, Saab Rayan, Ward Rachel, One-Bit Compressive Sensing With Norm Estimation, 10.1109/tit.2016.2527637
  46. Kolmogorov, Uspekhi Mat. Nauk, 14, 3 (1959)
  47. Ledoux, Probability in Banach Spaces: Isoperimetry and Processes (2013)
  48. Liaw Christopher, Mehrabian Abbas, Plan Yaniv, Vershynin Roman, A Simple Tool for Bounding the Deviation of Random Matrices on Geometric Sets, Lecture Notes in Mathematics (2017) ISBN:9783319452814 p.277-299, 10.1007/978-3-319-45282-1_18
  49. Mendelson Shahar, Pajor Alain, Tomczak-Jaegermann Nicole, Uniform Uncertainty Principle for Bernoulli and Subgaussian Ensembles, 10.1007/s00365-007-9005-8
  50. Moshtaghpour A., Jacques L., Cambareri V., Degraux K., De Vleeschouwer C., Consistent Basis Pursuit for Signal and Matrix Estimates in Quantized Compressed Sensing, 10.1109/lsp.2015.2497543
  51. Nam S., Davies M.E., Elad M., Gribonval R., The cosparse analysis model and algorithms, 10.1016/j.acha.2012.03.006
  52. Natarajan B. K., Sparse Approximate Solutions to Linear Systems, 10.1137/s0097539792240406
  53. Nguyen Ha Q., Goyal Vivek K., Varshney Lav R., Frame permutation quantization, 10.1016/j.acha.2010.10.003
  54. Oymak, Technical Report (2015)
  55. Oymak, Inf. Inference, 7, 707 (2018)
  56. Pai, Nonadaptive lossy encoding of sparse signals (2006)
  57. Pisier, The Volume of Convex Bodies and Banach Space Geometry (1999)
  58. Plan Yaniv, Vershynin Roman, Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach, 10.1109/tit.2012.2207945
  59. Plan Yaniv, Vershynin Roman, Dimension Reduction by Random Hyperplane Tessellations, 10.1007/s00454-013-9561-6
  60. Plan Yaniv, Vershynin Roman, The Generalized Lasso With Non-Linear Observations, 10.1109/tit.2016.2517008
  61. Plan, Inf. Inference, 6, 1 (2016)
  62. Rauhut, Compressive Sensing and Structured Random Matrices, 1 (2010)
  63. Rauhut Holger, Schnass Karin, Vandergheynst Pierre, Compressed Sensing and Redundant Dictionaries, 10.1109/tit.2008.920190
  64. Recht Benjamin, Fazel Maryam, Parrilo Pablo A., Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization, 10.1137/070697835
  65. Shi Hao-Jun Michael, Case Mindy, Gu Xiaoyi, Tu Shenyinying, Needell Deanna, Methods for quantized compressed sensing, 10.1109/ita.2016.7888203
  66. Tillmann Andreas M., Gribonval Remi, Pfetsch Marc E., Projection onto the cosparse set is NP-hard, 10.1109/icassp.2014.6854987
  67. Tropp Joel A., Gilbert Anna C., Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit, 10.1109/tit.2007.909108
  68. Vershynin Roman, Introduction to the non-asymptotic analysis of random matrices, Compressed Sensing ISBN:9780511794308 p.210-268, 10.1017/cbo9780511794308.006
  69. Zebadua Augusto Gabriel, Amblard Pierre-Olivier, Moisan Eric, Michel Olivier J. J., Compressed and Quantized Correlation Estimators, 10.1109/tsp.2016.2597128
  70. Zebadua, Traitement du signal dans le domaine compressé et quantification sur un bit: deux outils pour les contextes sous contraintes de communication (2017)
  71. Zymnis A., Boyd S., Candes E., Compressed Sensing With Quantized Measurements, 10.1109/lsp.2009.2035667
Bibliographic reference Xu, Chunlei ; Jacques, Laurent. Quantized Compressive Sensing with RIP Matrices: The Benefit of Dithering. In: Information and Inference, (2019)
Permanent URL http://hdl.handle.net/2078.1/216652