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$.
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.
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