Abstract
In previous work two of the authors have shown that a vector $x \in \mathbb{R}^n$ with at most $k < n$ nonzeros can be recovered from an expander sketch $Ax$ in $\mathcal{O}(\mathrm{nnz}(A)\log k)$ operations via the Parallel-$\ell_0$ decoding algorithm, where $\mathrm{nnz}(A)$ denotes the number of nonzero entries in $A \in \mathbb{R}^{m \times n}$. In this paper we present the Robust-$\ell_0$ decoding algorithm, which robustifies Parallel-$\ell_0$ when the sketch $Ax$ is corrupted by additive noise. This robustness is achieved by approximating the asymptotic posterior distribution of values in the sketch given its corrupted measurements. We provide analytic expressions that approximate these posteriors under the assumptions that the nonzero entries in the signal and the noise are drawn from continuous distributions. Numerical experiments presented show that Robust-$\ell_0$ is superior to existing greedy and combinatorial compressed sensing algorithms in the presence of small to moderate signal-to-noise ratios in the setting of Gaussian signals and Gaussian additive noise.
Introduction
Compressed sensing (CS) is a powerful paradigm for reconstructing sparse signals from a limited number of measurements. While traditional CS often relies on dense matrices and computationally intensive optimization, combinatorial compressed sensing utilizes sparse, binary expander matrices to achieve near-linear recovery times. A prominent example is the Parallel-$\ell_0$ algorithm, which offers massive parallelism and speed.
However, Parallel-$\ell_0$ is notoriously sensitive to noise. Its logic depends on identifying exact zeros or exact matches between measurements—conditions that are almost never met in real-world scenarios with additive noise. This paper introduces Robust-$\ell_0$, a Bayesian-inspired evolution of the algorithm designed to maintain high-speed recovery even when measurements are corrupted.
Methods and Model
The core innovation of Robust-$\ell_0$ is the transition from rigid "if-then" logic to a probabilistic framework. Instead of checking for exact equality, the algorithm calculates the posterior probability that a measurement represents a zero signal component ($p_z$) or that two measurements correspond to the same signal value ($p_e$).
To make this computationally feasible for continuous distributions like Gaussian noise, the authors derived analytic series approximations (Theorems I.4 and III.3). These allow the algorithm to efficiently estimate posterior scores without exhaustive integration. Furthermore, an iterative thresholding scheme using a "sweeping parameter" $t$ is employed. By starting with a high threshold and gradually decreasing it, the algorithm prioritizes the most certain signal updates, effectively "cooling" into a solution.
The algorithm relies on the signal being "dissociated"—meaning sums of different subsets of signal components are unique. While this may seem restrictive, signals drawn from any continuous distribution satisfy this property almost surely. The framework was tested using a Generating Model (GM) where $k$-sparse signals $x$ and additive noise $\eta$ are drawn from continuous distributions, and $A$ is a random expander matrix. Experiments scaled up to $n = 2^{24}$ (approximately 16.7 million variables) to test the limits of its parallel architecture.
Key Results
Robust-$\ell_0$ demonstrates significant resilience to noise compared to previous combinatorial methods like SSMP and SMP. In environments with small-to-moderate noise (e.g., $\sigma = 0.001$), it maintains high recovery rates at sparsity levels where other algorithms fail.
As shown in the algorithm selection map, Robust-$\ell_0$ variants (such as the "adaptive point" and "asterisk" versions) are the preferred choice across a wide range of sampling rates ($\delta = m/n$) and sparsity levels ($\rho = k/m$), particularly when $\rho$ is low. While greedy algorithms like CGIHT may perform better in extremely high-noise regimes ($\sigma \approx 0.1$), Robust-$\ell_0$ remains highly competitive in speed and offers better theoretical alignment with the sparse matrices used in large-scale applications.
Conclusion and Future Work
By bridging the gap between combinatorial speed and numerical robustness, Robust-$\ell_0$ provides a scalable solution for noisy compressed sensing. Future research may focus on automating the selection of the sweeping parameter $t$ and developing "blind" versions of the algorithm that do not require prior knowledge of signal and noise distributions.
Summary updated