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

[img] Text
Signal_Processing.pdf - Published Version
Available under License Creative Commons Attribution.

Download (1MB)


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 CreatorsORCiD
Vidyasagar, MathukumalliUNSPECIFIED
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:
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
Publisher URL:
OA policy:
Related URLs:

    Actions (login required)

    View Item View Item
    Statistics for RAIITH ePrint 11077 Statistics for this ePrint Item