A Fast Noniterative Algorithm for Compressive Sensing Using Binary Measurement Matrices

作者：Lotfi Mahsa; Vidyasagar Mathukumalli^*

来源：IEEE Transactions on Signal Processing, 2018, 66(15): 4079-4089.

DOI：10.1109/TSP.2018.2841881

• Compressive sensing
• ultra sparse vector recovery
• deterministic methods
• expander graphs
• restricted isometry property
• basis pursuit

In this paper, we present a new algorithm for compressive sensing that makes use of binary measurement matrices and achieves exact recovery of ultrasparse vectors in a single pass and without any iterations. Due to its noniterative nature, our algorithm is hundreds of times faster than l(1)-norm minimization and methods based on expander graphs, both of which require multiple iterations. Our algorithm can accommodate nearly sparse vectors, in which case, it recovers an index set of the largest components, and can also accommodate burst noise measurements. Compared to compressive sensing methods that are guaranteed to achieve exact recovery of all sparse vectors, our method requires fewer measurements. However, methods that achieve statistical recovery, that is, recovery of almost all but not all sparse vectors, can require fewer measurements than our method.

• 出版日期2018-8-1