Partially deterministic sampling for compressed sensing with denoising guarantees

1. Problem Statement

The paper addresses Compressed Sensing (CS), a paradigm for recovering high-dimensional signals ($x_0 \in \mathbb{K}^n$) from a small number of linear measurements ($y = Ax_0 + \epsilon$), where $m \ll n$.

• Context: The measurements are subsampled from a unitary matrix $F$ (e.g., Fourier transform in MRI), such that $A = SF$, where $S$ is a sampling matrix.
• The Challenge: In practice, certain measurement vectors (rows of $F$) are known to be critical (e.g., low-frequency components in images). Standard randomized sampling schemes (like with-replacement or without-replacement) treat all vectors probabilistically.
  • With-replacement sampling risks missing critical vectors entirely or sampling them redundantly (wasting measurements).
  • Without-replacement sampling avoids redundancy but still carries a non-negligible probability of missing high-coherence (critical) vectors, especially in edge cases.
• Goal: The authors aim to derive an optimized sampling scheme that rigorously decides which rows to sample deterministically (probability = 1) and which to sample randomly, thereby combining the robustness of deterministic selection with the flexibility of randomization.

2. Methodology

The authors propose a framework based on Bernoulli sampling with optimized probability weights.

A. Bernoulli Selector Sampling

Instead of selecting a fixed number of rows, the method uses a diagonal random matrix $A$ where each diagonal entry $A_{ii}$ is non-zero with probability $w_i$.

• Bernoulli Weights ($w$): A probability vector $w \in [0, 1]^n$.
• Saturated Vectors: If $w_i = 1$, the $i$-th measurement vector is included deterministically.
• Unsaturated Vectors: If $w_i < 1$, the vector is included randomly.
• Preconditioning: A diagonal matrix $D$ is applied to balance the effect of non-uniform sampling probabilities, ensuring the Restricted Isometry Property (RIP) holds.

B. Theoretical Framework

The recovery analysis relies on the Restricted Isometry Property (RIP) and the concept of Local Coherence.

1. Local Coherence ($\alpha$): Measures the alignment between measurement vectors (rows of $F$) and the signal prior set (e.g., a union of subspaces or a generative model).
2. Complexity Measures:
   • The authors define a Tight Bernoulli Complexity $\gamma(\alpha, w)$ and a Simplified Complexity $\eta(\alpha, w)$.
   • These measures quantify the difficulty of recovery based on the interaction between the sampling weights $w$ and the local coherences $\alpha$.
3. Optimization: The core contribution is finding the weight vector $w^\circ$ that minimizes the complexity bound. This leads to a closed-form solution where the largest coherence vectors are assigned probability 1 (deterministic), and the rest are assigned probabilities proportional to their coherence squared, normalized to ensure the expected number of samples is $m$.

C. Key Theoretical Tools

• Matrix Bernstein Inequality: Used to prove that the preconditioned sampling matrix satisfies the RIP with high probability.
• Truncation Operator: A novel operator introduced to bound the noise term in the recovery error, specifically handling the variance introduced by the random number of samples in Bernoulli schemes.
• Union Bounds: Used to combine RIP guarantees with noise bounds to derive final recovery error rates.

3. Key Contributions

1. Optimized Partially Deterministic Scheme:

   • Derivation of a closed-form expression for optimal Bernoulli weights ($w^\circ$).
   • The scheme automatically identifies "saturated" (deterministic) rows. If a row's coherence is too high relative to the sampling budget, it is forced to be sampled with probability 1.
   • This eliminates the risk of missing critical measurements, a flaw in purely random schemes.

2. Improved Sample Complexity Bounds:

   • The paper establishes a new sample complexity bound involving a term $L(\alpha, m)$, which is strictly smaller than the $\|\alpha\|_2$ term found in previous with-replacement sampling theories.
   • Mechanism of Improvement: As the number of measurements $m$ increases, more high-coherence vectors become "saturated" (deterministic). The complexity term $L(\alpha, m)$ only sums the coherences of the unsaturated (random) vectors. Since the largest coherences are removed from the sum, the required sample size decreases significantly compared to previous bounds.

3. Denoising Guarantees:

   • The authors provide the first denoising bounds for Bernoulli sampling under Gaussian noise and variable probability weights.
   • These bounds extend existing theory to handle the specific noise characteristics of partially deterministic sampling.

4. General Recovery Theory:

   • The framework applies to arbitrary signal priors (union of subspaces, sparse signals, and generative models) and arbitrary Bernoulli weight vectors, with the optimized scheme being the specific minimizer of the derived complexity bounds.

4. Results

Theoretical Results

• Theorem 2.8: Provides a rigorous error bound for signal reconstruction. The error depends on the noise level $\sigma$, the optimization error $\epsilon$, and the new complexity term $L(\alpha, m)$.
• Monotonicity: The function $L(\alpha, m)$ is proven to be decreasing in $m$. This implies that as more measurements are taken, the "cost" of the remaining random sampling drops because the most difficult (high coherence) vectors are handled deterministically.
• Toy Example (Section 6): A theoretical counter-example demonstrates that optimized without-replacement sampling can fail to capture a critical vector with constant probability even as $n \to \infty$, whereas the proposed Bernoulli scheme guarantees capture (probability 1) for that vector.

Numerical Experiments (Section 7)

Experiments were conducted on the CELEBA dataset (faces) using two priors:

1. Sparse Prior: Signals sparse in the Haar wavelet basis.
2. Generative Prior: Signals generated by a Convolutional VAE.

Findings:

• Performance: The optimized Bernoulli scheme consistently outperforms both with-replacement and without-replacement sampling schemes in terms of relative reconstruction error.
• Comparison:
  • With-replacement suffers from redundant sampling of high-coherence vectors.
  • Without-replacement (optimized) struggles computationally when using empirical preconditioners for large $m$ and decaying coherences, and theoretically risks missing critical vectors.
  • Bernoulli: Achieves the best balance, ensuring critical vectors are always present while maintaining theoretical guarantees.
• Sparse vs. Generative: The improvement is particularly pronounced in the sparse setting where local coherences have a "heavy tail," making the deterministic inclusion of top vectors crucial.

5. Significance

This work bridges a critical gap between theoretical CS (which often assumes purely random sampling) and practical applications (like MRI, where specific frequencies are known to be vital).

• Practical Impact: It provides a rigorous mathematical justification for the common practice of "hybrid" sampling (deterministically sampling low frequencies, randomly sampling high frequencies). It moves this practice from heuristic to a provably optimal strategy.
• Theoretical Advancement: By introducing the concept of "saturated" vectors in the complexity analysis, the authors derive tighter sample complexity bounds than previously possible, showing that the cost of sampling decreases as the number of measurements grows.
• Robustness: The inclusion of denoising guarantees makes the theory applicable to real-world noisy data, which is ubiquitous in medical imaging and remote sensing.

In summary, the paper proves that partially deterministic sampling is not just a practical workaround but a theoretically superior strategy for compressed sensing, offering better sample efficiency and reconstruction accuracy than purely random approaches.