Compressed Sensing Using Binary Matrices of Nearly Optimal Dimensions

Lotfi, Mahsa and Vidyasagar, Mathukumalli (2020) Compressed Sensing Using Binary Matrices of Nearly Optimal Dimensions. IEEE Transactions on Signal Processing, 68. pp. 3008-3021. ISSN 1053-587X

Text
Signal_Processing.pdf - Published Version
Available under License Creative Commons Attribution.
Download (1MB)

Abstract

In this paper, we study the problem of compressed sensing using binary measurement matrices and ℓ1-norm minimization (basis pursuit) as the recovery algorithm. We derive new upper and lower bounds on the number of measurements to achieve robust sparse recovery with binary matrices. We establish sufficient conditions for a column-regular binary matrix to satisfy the robust null space property (RNSP) and show that the associated sufficient conditions for robust sparse recovery obtained using the RNSP are better by a factor of (3 √3)/2 ≈ 2.6 compared to the sufficient conditions obtained using the restricted isometry property (RIP). Next we derive universal lower bounds on the number of measurements that any binary matrix needs to have in order to satisfy the weaker sufficient condition based on the RNSP and show that bipartite graphs of girth six are optimal. Then we display two classes of binary matrices, namely parity check matrices of array codes and Euler squares, which have girth six and are nearly optimal in the sense of almost satisfying the lower bound. In principle, randomly generated Gaussian measurement matrices are 'order-optimal.' So we compare the phase transition behavior of the basis pursuit formulation using binary array codes and Gaussian matrices and show that (i) there is essentially no difference between the phase transition boundaries in the two cases and (ii) the CPU time of basis pursuit with binary matrices is hundreds of times faster than with Gaussian matrices and the storage requirements are less. Therefore it is suggested that binary matrices are a viable alternative to Gaussian matrices for compressed sensing using basis pursuit. © 1991-2012 IEEE.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Vidyasagar, Mathukumalli	UNSPECIFIED

Item Type:

Article

Additional Information:

Manuscript received October 29, 2018; revised October 10, 2019 and April 18, 2020; accepted April 21, 2020. Date of publication April 27, 2020; date of current version May 29, 2020. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Jarvis Haupt. This work was supported in part by the National Science Foundation, USA under Award #ECCS-1306630, and in part by the Department of Science and Technology, Government of India. (Corresponding author: Mathukumalli Vidyasagar.) Mahsa Lotfi was with the Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas, Richardson, TX 75080 USA. She is now with the Department of Statistics, Stanford University, Stanford, CA 94305 USA (e-mail: lotfi@stanford.edu).

Uncontrolled Keywords:

array codes; binary matrices; Compressed sensing; phase transition; robust null space property

Subjects:

Electrical Engineering

Divisions:

Department of Electrical Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

27 Oct 2022 11:21

Last Modified:

27 Oct 2022 11:21