Dual-space Compressed Sensing

Xudong Lv, Ashok AjoyarXiv 2022 · DOI · arXiv

TL;DR

Dual-space Compressed Sensing (CS) breaks the traditional mold of sampling in a single basis by simultaneously measuring an object in two incoherent spaces (e.g., real-space and k-space). By using initial k-space data to guide targeted real-space sampling, this method significantly reduces the number of measurements required, improves noise robustness, and simplifies the complex optimization landscape typical of image reconstruction.

What Problem Does This Paper Address?

Compressed Sensing is a cornerstone of modern imaging (like MRI), allowing us to reconstruct high-resolution images from far fewer samples than the Nyquist criterion suggests—provided the image is "sparse" (mostly zeros). Traditionally, we sample in a basis where the data is not sparse (like Fourier or k-space) to reconstruct the sparse real-space image.

However, conventional CS has limits. As the number of samples decreases, the "optimization landscape"—the mathematical terrain the computer must navigate to find the true image—becomes riddled with local minima (false solutions). This leads to reconstruction errors, especially in noisy environments. Furthermore, standard CS assumes we are locked into sampling in only one space. The authors ask: What if we could sample in both spaces at once?

Methods

The authors propose a "Dual-space CS" algorithm that uses a feed-forward mechanism:

  1. Initial k-space Sampling: Take a small number of random samples in k-space to create a rough, intermediate reconstruction.
  2. Feature Identification: Identify the most likely locations of sparse features (like bright particles or sharp edges) in that intermediate image.
  3. Targeted Real-space Sampling: Perform a few highly specific measurements in real-space at those identified locations.
  4. Problem Truncation: This is the "secret sauce." By "pinning down" these specific pixels, the algorithm removes them from the mathematical search. This creates a "truncated image" with much higher effective sparsity.
  5. Final Reconstruction: Re-solve the optimization problem for the remaining unknown pixels. Because the search space is now much smaller and the effective sparsity is higher, the algorithm converges much faster and more accurately.

Datasets

The paper evaluates the method using:

  • Simulated 1D signals: Collections of $\delta$-functions (representing sparse objects like nanoparticles) to test basic convergence and noise robustness.
  • 2D Shepp-Logan Phantom: A standard benchmark in medical imaging used here to demonstrate superior edge detection.
  • Synthesized 64x64 images: Used for large-scale statistical analysis (1,000+ manifestations) to prove the consistency of the "speedup" across different levels of sparsity.

Key Insights and Ideas

  • Cleaning the Landscape: One of the most striking "aha moments" is shown in the paper's visualization of the optimization landscape. While single-space CS results in a "bumpy" terrain with many traps, dual-space CS creates a smooth, well-conditioned landscape with a clear global minimum.
  • SNR Boost: In noisy settings, random k-space sampling spreads signal and noise across the whole domain. Targeted real-space sampling acts like a spotlight, providing a massive boost to the Signal-to-Noise Ratio (SNR) exactly where the signal lives.
  • The Power of Truncation: The authors prove that the required number of samples $m^*$ scales with the truncated sparsity ($s_T$) rather than the original sparsity ($s$). Since $s_T < s$, the "sampling budget" required for a perfect reconstruction drops significantly.

Key Results

  • Superior Fidelity: In 2D edge detection tests on the Shepp-Logan phantom, dual-space CS achieved >99.9% image fidelity and >99.5% edge fidelity, vastly outperforming conventional CS using the same total number of samples.
  • Noise Resilience: Dual-space CS maintained high reconstruction accuracy even when the SNR approached 1, a regime where conventional CS typically fails due to spurious noise peaks.
  • Theoretical Validation: The authors introduced a "truncated Null Space Property" (t-NSP) to formally prove why this hybrid approach provides a tighter bound on reconstruction error.

Limitations and Future Work

  • Hardware Constraints: The primary limitation is physical. To use this, you need a system capable of dual-mode sampling. The authors suggest this is perfect for Nanodiamond (ND) imaging, where Nitrogen-Vacancy (NV) centers allow for simultaneous optical (real-space) and $^{13}$C MRI (k-space) measurements.
  • Success Probability: The benefit depends on the "success probability" of the initial k-space reconstruction. If the first pass is too poor to identify any true features, the real-space sampling won't provide the necessary "boost."
  • Future Directions: The authors envision applying these principles to Quantum Information Science (QIS), specifically for entanglement characterization and state tomography, where "sampling" is often the most expensive part of the experiment.

Summary updated

Abstract

Compressed sensing (CS) is a powerful method routinely employed to accelerate image acquisition. It is particularly suited to situations when the image under consideration is sparse but can be sampled in a basis where it is non-sparse. Here we propose an alternate CS regime in situations where the image can be sampled in two incoherent spaces simultaneously, with a special focus on image sampling in Fourier reciprocal spaces (e.g. real-space and k-space). Information is fed-forward from one space to the other, allowing new opportunities to efficiently solve the optimization problem at the heart of CS image reconstruction. We show that considerable gains in imaging acceleration are then possible over conventional CS. The technique provides enhanced robustness to noise, and is well suited to edge-detection problems. We envision applications for imaging collections of nanodiamond (ND) particles targeting specific regions in a volume of interest, exploiting the ability of lattice defects (NV centers) to allow ND particles to be imaged in reciprocal spaces simultaneously via optical fluorescence and 13C magnetic resonance imaging (MRI) respectively. Broadly this work suggests the potential to interface CS principles with hybrid sampling strategies to yield speedup in signal acquisition in many practical settings.
BibTeX
@misc{lv2022dual,
  author = {Xudong Lv and Ashok Ajoy},
  title = {{Dual-space Compressed Sensing}},
  year = {2022},
  eprint = {2207.07627},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2207.07627},
}
Figure