Limits on Sparse Support Recovery via Linear Sketching with Random Expander Matrices

Jonathan Scarlett, Volkan Cevher

Introduction

In the field of compressed sensing and data sketching, the challenge is often to recover a sparse signal $\beta \in \mathbb{R}^p$ from a limited number of noisy linear measurements $Y = X\beta + Z$. While much of the literature focuses on minimizing the $\ell_2$ reconstruction error, many practical applications—ranging from cognitive radio channel identification to network traffic monitoring—prioritize support recovery. This task involves identifying the specific indices of the non-zero entries in $\beta$, rather than their exact values.

Historically, i.i.d. Gaussian matrices have served as the "gold standard" for measurement matrices ($X$) due to their optimal theoretical guarantees. However, their density makes them computationally expensive for large-scale applications. Random expander matrices—sparse binary matrices—have emerged as a high-performance alternative, offering faster computation and reduced storage. Despite their popularity, a "sharp" information-theoretic characterization of their recovery limits was previously missing. This paper fills that gap, establishing exact thresholds for support recovery and comparing them to the Gaussian baseline.

The Support Recovery Problem

The authors consider the standard linear model $Y = X\beta + Z$, where $X$ is an $n \times p$ measurement matrix and $Z$ represents additive white Gaussian noise. The goal is to identify the support set $S = \{j : \beta_j \neq 0\}$, where $|S| = k$.

The measurement matrix $X$ used in this study is a random expander construction. In this setup, each column of $X$ is a random permutation of a sparse binary vector containing exactly $d$ ones. This sparsity is what provides the computational edge, but it also introduces complex dependencies between the entries of the matrix, making traditional i.i.d. analysis techniques inapplicable.

Methodology: Information-Theoretic Limits

To determine the absolute physical limits of support recovery, the authors analyze the performance of an information-theoretically optimal decoder. This decoder minimizes the probability of error regardless of computational cost, providing a benchmark for what is physically possible.

The Change-of-Measure Technique

A significant mathematical hurdle in analyzing expander matrices is the lack of independence between entries within a column. To overcome this, the authors developed a "change-of-measure" technique. This innovation allows them to bound the error probability of the non-i.i.d. expander distribution by relating it to a simpler, independent Bernoulli distribution.

Mutual Information Thresholds

By deriving exact thresholds for the number of measurements $n$ based on conditional mutual information, the researchers established a framework for a direct "apples-to-apples" comparison with Gaussian matrices. The required number of measurements scales as: $$n \approx \frac{|s_{dif}| \log p}{I(X;Y)}$$ where $I(X;Y)$ represents the mutual information between the matrix and the measurements.

Key Insights: The SNR Divide

The paper reveals a nuanced relationship between the measurement matrix structure and the signal-to-noise ratio (SNR).

1. Noise as an Equalizer

One of the most significant findings is that at moderate-to-high noise levels (low SNR), the sparsity of the expander matrix does not significantly hinder performance. In these regimes, expander matrices perform nearly as well as Gaussian matrices, even matching them down to the constant factors. The gap is a negligible multiplicative factor of $1/(1-\rho)$, where $\rho$ is the matrix density. Since expanders are designed to be extremely sparse ($\rho \approx 0$), they are effectively optimal in noisy environments.

2. High-SNR Saturation

The performance gap widens significantly at low noise levels (high SNR). Because expander matrices are binary and discrete, the amount of information they can convey about the signal eventually "saturates." In contrast, the mutual information provided by Gaussian matrices grows logarithmically with the SNR. Consequently, in very low-noise scenarios, Gaussian matrices can recover the signal support with far fewer measurements than expander matrices.

The authors also demonstrate a formal link between the geometric property of "expansion" in the underlying bipartite graph of the matrix and its recovery robustness. When the expansion property is satisfied, the matrix provides a stable and reliable recovery of the signal support.

Conclusion and Future Work

This research provides the first sharp characterization of the trade-offs involved in using sparse binary matrices for support recovery. While expanders are nearly optimal in noisy settings, their discrete nature imposes a fundamental limit in high-precision, low-noise environments.

Several avenues for future research remain:

  • Algorithmic Gap: The current study focuses on the optimal decoder, which is NP-hard. It remains to be seen if practical algorithms like LASSO or Basis Pursuit can reach these theoretical limits when paired with expander matrices.
  • Linear Sparsity: The analysis assumes the number of non-zero entries $k$ is relatively small. Extending these results to cases where $k$ scales linearly with the signal dimension $p$ will require more advanced concentration inequalities.
  • LASSO Performance: Further investigation is needed to determine if the saturation point for expanders is higher or lower than the performance limits of specific practical decoders using Gaussian measurements.

Summary updated

Abstract

Linear sketching is a powerful tool for the problem of sparse signal recovery, having numerous applications such as compressive sensing, data stream computing, graph sketching, and routing. Motivated by applications where the \emphpositions of the non-zero entries in a sparse vector are of primary interest, we consider the problem of \emphsupport recovery from a linear sketch taking the form \mathbfY = \mathbfXβ+ \mathbfZ. We focus on a widely-used expander-based construction in the columns of the measurement matrix \mathbfX ∈\mathbbR^n \times p are random permutations of a sparse binary vector containing d ≪n ones and n-d zeros. We provide a sharp characterization of the number of measurements required for an information-theoretically optimal decoder, thus permitting a precise comparison to the i.i.d. Gaussian construction. Our findings reveal both positive and negative results, showing that the performance nearly matches the Gaussian construction at moderate-to-high noise levels, while being worse by an arbitrarily large factor at low noise levels.
BibTeX
@inproceedings{scarlett2016limits,
  author = {Jonathan Scarlett and Volkan Cevher},
  title = {{Limits on Sparse Support Recovery via Linear Sketching with Random Expander Matrices}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
}
Figure