Compressed Sensing with Binary Matrices: New Bounds on the Number of Measurements




Journal Title

Journal ISSN

Volume Title


Institute of Electrical and Electronics Engineers Inc.


In this paper we study the problem of compressed sensing using binary measurement matrices. New bounds are derived for the number of measurements that suffice to achieve robust sparse recovery, and the number of measurements needed to achieve sparse recovery. In particular, by interpreting any binary measurement matrix as the biadjacency matrix of an unbalanced bipartite graph, we derive new lower bounds on the number of measurements required by any graph of girth six or larger, in order to satisfy a sufficient condition for sparse recovery. It is shown that the optimal choices for the girth of the graph associated with the measurement matrix are six and eight. Some interesting open problems that arise from our results are pointed out. The proofs of the results presented here are omitted. The reader is directed to (M. Lotfi and M. Vidyasagar, “Compressed sensing using binary matrices of nearly optimal dimensions,” arXiv:1808.03001, 2018) for stronger results than are presented here, as well as their proofs. © 2019 IEEE.


Due to copyright restrictions and/or publisher's policy full text access from Treasures at UT Dallas is limited to current UTD affiliates (use the provided Link to Article).


Compressed sensing (Telecommunication), Graph theory, Binary matrices, Measurements (Binary), Bipartite graphs, Matrices


©2019 IEEE