Sparse Randomized Kaczmarz for Support Recovery of Jointly Sparse Corrupted Multiple Measurement Vectors

Natalie Durgin, Rachel Grotheer, Chenxi Huang, Shuang Li, Anna Ma, Deanna Needell, Jing QinarXiv 2017 · arXiv

Introduction

In signal processing, recovering sparse signals from linear measurements is a critical task, especially in the Multiple Measurement Vector (MMV) setting. Here, multiple signals share a common "support"—the indices of non-zero entries. While powerful, MMV models struggle with large-scale data and heavy corruption. Traditional methods often rely on row norms, which are easily fooled by large outliers or sensor spikes, leading to incorrect support identification.

Methodology: The cMMV-SRK Algorithm

To overcome these challenges, this paper introduces cMMV-SRK (Corrupted MMV-SRK). Building on the Sparse Randomized Kaczmarz (SRK) framework, cMMV-SRK processes data iteratively, making it ideal for real-time streaming.

The key innovation is a consensus-based tallying mechanism. Instead of averaging potentially corrupted signal magnitudes, the algorithm maintains a "tally vector." For each processed measurement, it "votes" for candidate support indices, weighting these votes by the iterations performed. Since corruptions are typically random and non-persistent, they fail to accumulate significant votes, whereas the true joint support consistently gains consensus, allowing for robust recovery.

Experimental Evaluation

The researchers evaluated cMMV-SRK against the standard MMV-SRK using synthetic benchmarks and a simulated medical imaging scenario (Hyperspectral Diffuse Optical Tomography, or hyDOT).

Synthetic Benchmarks

Tests were conducted using Gaussian and Uniform measurement matrices ($\Phi$), with corruptions injected as high-magnitude "spikes" to simulate hardware failure.

As illustrated in Figure 1, the standard MMV-SRK algorithm's accuracy plateaus at roughly 20% under these conditions. In contrast, cMMV-SRK achieves near 100% recovery of the true support, demonstrating its superior resilience to outliers.

Parameter Configuration

The experimental parameters for the various test cases, including the distribution of entries and corruptions, are summarized in the table below.

Key Insights

  • Robustness via Consensus: Switching from averaging to a voting mechanism effectively utilizes the "mode" of support estimates, which is naturally resistant to heavy-tailed noise.
  • Streaming-First Design: cMMV-SRK updates its tally as each signal arrives, making it uniquely suited for "online" environments where data is processed sequentially.
  • Real-World Application: In the hyDOT simulation, the algorithm successfully identified tumor locations (the support) despite the system being underdetermined and signals being corrupted.

Conclusion

cMMV-SRK offers a robust, scalable solution for support recovery in corrupted MMV systems. Its ability to maintain high accuracy in the presence of massive outliers and its suitability for streaming data mark a significant advancement over traditional methods. Future work will focus on formal convergence proofs and automated support size estimation.

Summary updated

Abstract

While single measurement vector (SMV) models have been widely studied in signal processing, there is a surging interest in addressing the multiple measurement vectors (MMV) problem. In the MMV setting, more than one measurement vector is available and the multiple signals to be recovered share some commonalities such as a common support. Applications in which MMV is a naturally occurring phenomenon include online streaming, medical imaging, and video recovery. This work presents a stochastic iterative algorithm for the support recovery of jointly sparse corrupted MMV. We present a variant of the Sparse Randomized Kaczmarz algorithm for corrupted MMV and compare our proposed method with an existing Kaczmarz type algorithm for MMV problems. We also showcase the usefulness of our approach in the online (streaming) setting and provide empirical evidence that suggests the robustness of the proposed method to the distribution of the corruption and the number of corruptions occurring.
BibTeX
@misc{durgin2017sparse,
  author = {Natalie Durgin and Rachel Grotheer and Chenxi Huang and Shuang Li and Anna Ma and Deanna Needell and Jing Qin},
  title = {{Sparse Randomized Kaczmarz for Support Recovery of Jointly Sparse Corrupted Multiple Measurement Vectors}},
  year = {2017},
  eprint = {1711.02743},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1711.02743},
}
Figure