Vanishingly Sparse Matrices and Expander Graphs, with application to compressed sensing

Bubacarr Bah, Jared Tanner

Abstract

This paper establishes the first tight, quantitative guarantees for using "vanishingly sparse" random matrices in compressed sensing. By introducing a novel dyadic splitting technique to analyze expander graphs, the authors derive precise bounds that demonstrate these sparse matrices can perform as well as—and in some regimes, better than—traditional dense Gaussian matrices for signal recovery. These findings provide the necessary "order constants" for practical engineering applications where computational efficiency and scalability are paramount.

Introduction

In compressed sensing, the goal is to recover a high-dimensional sparse signal from a minimal number of measurements. Traditionally, dense random matrices (e.g., Gaussian) have been favored due to their well-understood theoretical properties. However, their density poses significant challenges for storage and computational speed in large-scale systems. Sparse matrices, which represent bipartite expander graphs, offer a promising alternative by enabling faster matrix-vector multiplications and reduced memory footprints.

While the potential of expander-based matrices was known, the precise number of measurements required for a given signal sparsity remained unclear. This research addresses this gap by providing a rigorous probabilistic analysis of sparse structures, specifically focusing on Sparse Expanders (SE) and Sparse Signed Expanders (SSE).

Methods

The authors model the measurement process using bipartite graphs $G(U,V,E)$, where $U$ represents input nodes and $V$ represents output nodes. A graph is considered a $(k, d, \epsilon)$-expander if every subset of $k$ nodes in $U$ connects to at least $(1-\epsilon)dk$ unique neighbors in $V$.

Bipartite graph representation of a sparse expander, showing the mapping from a subset of inputs X to its neighbors Γ(X).

To overcome the combinatorial complexity of proving expansion properties, the authors introduce a dyadic splitting technique. This method recursively partitions the set of columns into halves (dyadic levels) and analyzes the overlapping non-zero entries ("collisions") at each level. By combining this with large deviation analysis—utilizing Stirling’s approximation and Shannon entropy functions—they establish an upper bound on the probability that a random sparse matrix fails to meet the "lossless" expansion criteria.

Key Results

The study quantifies the "lossless" threshold, showing that even with a small number of non-zeros per column (e.g., $d=7$ or $8$), these matrices are highly efficient. A significant contribution is the derivation of concrete tail bounds (Theorem 1.6) for the probability of expansion failure.

Phase transition curves illustrating the relationship between the measurement rate (n/N) and the signal sparsity (k/n) for different expansion parameters.

The authors plotted sampling theorems for various recovery algorithms, including $\ell_1$-minimization and Expander Recovery (ER). A key insight is that for certain parameter regimes, the recovery guarantees for sparse expander-based matrices are actually superior to those of dense Gaussian matrices. Furthermore, the Expander Recovery (ER) algorithm was found to succeed over a larger portion of the parameter space than standard $\ell_1$-minimization when paired with these sparse structures.

Conclusion

This work provides a theoretical foundation for the use of vanishingly sparse matrices in practical compressed sensing. By delivering tight quantitative bounds, it bridges the gap between abstract graph theory and engineering requirements. Future research directions include extending these results to deterministic matrix constructions and exploring the benefits of variable-degree sparse matrices to further optimize phase transitions.

Summary updated

Abstract

We revisit the probabilistic construction of sparse random matrices where each column has a fixed number of nonzeros whose row indices are drawn uniformly at random with replacement. These matrices have a one-to-one correspondence with the adjacency matrices of fixed left degree expander graphs. We present formulae for the expected cardinality of the set of neighbors for these graphs, and present tail bounds on the probability that this cardinality will be less than the expected value. Deducible from these bounds are similar bounds for the expansion of the graph which is of interest in many applications. These bounds are derived through a more detailed analysis of collisions in unions of sets. Key to this analysis is a novel {\em dyadic splitting} technique. The analysis led to the derivation of better order constants that allow for quantitative theorems on existence of lossless expander graphs and hence the sparse random matrices we consider and also quantitative compressed sensing sampling theorems when using sparse non mean-zero measurement matrices.
BibTeX
@article{bah2013vanishingly,
  author = {Bubacarr Bah and Jared Tanner},
  title = {{Vanishingly Sparse Matrices and Expander Graphs, with application to compressed sensing}},
  journal = {IEEE Trans. Information Theory},
  year = {2013},
  url = {https://openreview.net/forum?id=zJfFV24DyiD},
}
Figure