This paper, "Recovery guarantees for compressed sensing with unknown errors," by Brugiapaglia, Adcock, and Archibald, tackles a practical "elephant in the room" for compressed sensing (CS): what happens when we don't know how much noise is in our data?
TL;DR
The authors provide new theoretical recovery guarantees for $\ell_1$-minimization (specifically Quadratically Constrained Basis Pursuit) that do not require an exact a priori estimate of noise levels. They prove that for sensing matrices based on Bounded Orthonormal Systems (like Fourier or Chebyshev transforms), the reconstruction error degrades gracefully even if the noise is significantly underestimated, offering a robust theoretical foundation for real-world applications like MRI and high-dimensional function approximation.
What Problem Does This Paper Address?
In the standard Compressed Sensing framework, we try to recover a sparse signal $x$ from few measurements $y = Ax + n$, where $n$ is noise. The go-to tool is Quadratically Constrained Basis Pursuit (QCBP): $$\min \|z\|_1 \quad \text{subject to} \quad \|Az - y\|_2 \le \eta$$ Standard theory assumes we know a bound $\eta$ such that $\|n\|_2 \le \eta$. However, in practice, "noise" isn't just sensor static; it includes model discrepancies, discretization errors, and quadrature errors that are nearly impossible to estimate beforehand.
If you choose $\eta$ too small, standard theory breaks down. If you choose it too large, you lose accuracy. This paper asks: Can we still guarantee good recovery if our estimate $\eta$ is wrong?
Methods
The authors move away from the "ideal" scenario where noise is perfectly bounded. Their approach involves:
- Bounded Orthonormal Systems (BOS): Instead of generic Gaussian matrices, they focus on BOS-based matrices (e.g., subsampled Fourier transforms), which are ubiquitous in imaging and physics.
- Robust Null Space Property (NSP) & RIP: They utilize these standard CS tools but extend them to handle the regime where $\|n\|_2 > \eta$.
- Random Matrix Theory: They employ principles from the theory of random matrices with "heavy-tailed" columns to analyze the singular values of the sensing matrices, specifically looking at how "tall" random matrices behave when their columns are independent isotropic vectors.
Datasets
The paper validates its theoretical findings using:
- Simulated Multivariate Functions: A 10-dimensional logarithmic function evaluated using tensorized Chebyshev polynomials.
- Non-Cartesian MRI Data: Using the BrainWeb simulated brain database (a standard phantom in medical imaging) sampled along a rosette trajectory.
- Synthetic Sparse Vectors: Randomly generated 10-sparse vectors in $\mathbb{C}^{1000}$ to compare Fourier vs. Gaussian measurement stability.
Key Insights and Ideas
- The "Penalty" for Ignorance: The authors derive a new error bound (Theorem 6) showing that the recovery error is proportional to the best $s$-term approximation error, the chosen $\eta$, and a third term: $L^{1/2} \max\{\|n\|_2 - \eta, 0\}$. This means if you underestimate the noise, the error only grows by a factor related to the excess noise, scaled by a polylogarithmic factor $L$.
- Fourier vs. Gaussian Stability: A striking insight is that Fourier-based measurements are significantly more stable than Gaussian ones when the noise estimate is zero ($\eta = 0$). As shown in Figure 1, Fourier measurements maintain low error as the number of measurements $m$ approaches the signal dimension $N$, whereas Gaussian measurements become highly unstable.
- Optimal $\eta$ Behavior: The error curve as a function of $\eta$ typically has a global minimum. The authors find that for low noise, underestimating $\eta$ is actually safer than overestimating it.
Key Results
- Theoretical Bound: They established a robust recovery guarantee for QCBP with BOS matrices that accounts for unknown errors.
- MRI Improvements: In non-Cartesian MRI, model errors arise from "gridding" data to a uniform grid. The paper shows that higher-fidelity gridding (which reduces model error) directly translates to better Signal-to-Error Ratios (SER), as predicted by their theory. Figure 4 demonstrates this, showing an SER jump from 8.38dB to 17.84dB by improving the gridding strategy.
- Function Approximation: For high-dimensional functions, they showed that cross-validation can approximate the optimal $\eta$ reasonably well, but their theory explains why the reconstruction remains stable even if cross-validation isn't perfect.
Limitations and Future Work
The authors identify three main hurdles for future research:
- Sparsity Regime: The current proof only holds for a "low" sparsity regime where $s \lesssim \sqrt{N}$ (ignoring log factors). Extending this to the linear regime ($s \propto N$) is an open problem.
- Dimension Dependence: The error estimate still has a polylogarithmic dependence on the total dimension $N$. Ideally, a robust estimate would be independent of $N$.
- Failure Probability: The relationship between the sparsity level and the failure probability $\epsilon$ is currently linear, meaning the failure probability isn't as "overwhelmingly low" as in standard CS results.
Despite these, the work provides a vital bridge between the clean world of CS theory and the messy reality of experimental data.
Summary updated