# Deterministic Compressed Sensing Using Binary Measurement Matrices

## Date

## Authors

## ORCID

## Journal Title

## Journal ISSN

## Volume Title

## Publisher

## item.page.doi

## Abstract

The fundamental objective of compressed sensing is to recover a high dimensional but low
complexity vector or matrix from only a few linear measurements. In most of the initial
publications in the field of compressed sensing, the emphasis is on using random matrices
such as Gaussian, Bernoulli, etc. The limitations of this framework include high memory
requirements, and CPU time. This dissertation mainly focuses on binary measurement
matrices and highlights the superiority of binary matrices in terms of CPU time, complexity,
and the required memory compared to the random measurement matrices.
In the first part of the dissertation (Chapter 2), we present a new recovery algorithm for compressed sensing that makes use of binary measurement matrices and achieves exact recovery
of ultra sparse vectors, in a single pass and without any iterations. Due to its non-iterative
nature, our algorithm is hundreds of times faster than iterative algorithms such as `1-norm minimization, and methods based on expander graphs. Our algorithm can accommodate nearly sparse vectors, in which case it recovers the index set of the largest components, and can also accommodate shot noise measurements. In the second part of the dissertation (Chapter 3), we focus on using binary measurement matrices to solve the problem of compressed sensing while `

1-norm minimization (basis pursuit) is considered 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 prove
sufficient conditions for a column-regular binary matrix to satisfy the robust null space property (RNSP) and 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. Then we show that binary matrices that are bi-adjacency matrices of bipartite graphs
of girth six are optimal. Two classes of binary matrices, namely parity check matrices of
array codes, and the matrices based on Euler Squares, 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”; however in practice, Gaussian matrices require
more measurements than binary matrices when n < 106
.
We then compare the phase transition behavior of the `1-norm minimization formulation
using binary parity check matrix of the array code and the Gaussian matrices, and show
that the phase transitions of both matrices are almost the same and the recovery using basis
pursuit with binary matrices is hundreds of times faster than with Gaussian matrices. In
addition, the required memory is less than when using Gaussian matrices. This suggests
that binary matrices are a viable alternative to Gaussian matrices for compressed sensing
using basis pursuit. This study can be extended to other recovery algorithms using binary
matrices.