Compressed sensing for fusion frames

Petros T. Boufounos, Gitta Kutyniok, Holger RauhutProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 2009 · DOI

TL;DR

This paper introduces a novel sparsity model for "fusion frames," a more flexible way to represent signals using collections of subspaces. By combining this with Compressed Sensing (CS) principles, they show that signals with energy concentrated in only a few subspaces can be efficiently sampled and accurately reconstructed, extending CS to more complex signal structures.

What Problem Does This Paper Address?

Traditional Compressed Sensing (CS) relies on signals being "sparse," meaning they have only a few non-zero coefficients in a particular basis. This works well for many signals but struggles with more complex data where structure is better captured by entire subspaces rather than individual coefficients. Fusion frames offer a richer representation by using subspaces as building blocks, allowing signals to be represented as combinations of components residing in these subspaces. The challenge is to adapt CS techniques to leverage this subspace-based sparsity, enabling efficient sampling and recovery of signals that are sparse across subspaces, even if they are not sparse within each subspace.

Methods

The core contribution is the introduction of a new sparsity model for fusion frames. Instead of requiring sparsity within each subspace, the model focuses on signals that have energy concentrated in only a few of the fusion frame's constituent subspaces. To achieve this, the authors define a "mixed $\ell_1/\ell_2$ norm" for fusion frames. This norm penalizes signals that utilize many subspaces, effectively promoting sparsity at the subspace level.

They then adapt the standard CS recovery techniques, specifically $\ell_1$ minimization, to this new model. The recovery guarantees are derived using two key concepts:

  • Fusion Coherence: An adaptation of the classical mutual coherence concept, this measures the "overlap" or correlation between different subspaces in the fusion frame and the sampling matrix. A low fusion coherence is crucial for unique signal recovery.
  • Restricted Isometry Property (RIP): Similar to classical CS, this property ensures that the sampling matrix approximately preserves the norm of signals, particularly those with the target sparsity.

The paper formulates optimization problems (like $\ell_1$ minimization) that, under these conditions, guarantee the unique recovery of the sparse fusion frame signal.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Subspace Sparsity is Powerful: The paper demonstrates that sparsity can be effectively defined at the subspace level, not just at the individual coefficient level. This opens up CS to a broader class of signals.
  • Fusion Frames as a Richer Dictionary: Fusion frames provide a more flexible and structured way to represent signals compared to traditional bases, allowing for the capture of complex relationships between signal components.
  • Fusion Coherence as a Key Metric: The introduction of "fusion coherence" provides a crucial metric for understanding how well a sampling matrix is suited for recovering signals represented by fusion frames. It elegantly combines the geometry of the subspaces with the properties of the sampling matrix.
  • Bridging Classical CS and Subspace Models: The work successfully bridges the gap between classical CS (sparse vectors) and more advanced models like joint sparsity and block sparsity, providing a unified framework.

Key Results

The paper establishes theoretical guarantees for recovering signals that are sparse in a fusion frame representation. Specifically, it shows that if a signal is concentrated in $k$ subspaces and the sampling matrix satisfies certain conditions (low fusion coherence or RIP), then the signal can be uniquely recovered from a compressed set of measurements using $\ell_1$ minimization. The sampling conditions derived are analogous to those in standard CS, suggesting that the number of measurements required is still significantly reduced compared to the signal's full dimension.

Limitations and Future Work

  • Worst-Case Analysis: The current analysis is worst-case, which can be pessimistic. The authors suggest that an average-case analysis could provide more informative guarantees for practical applications.
  • Noise and Approximation: The current framework primarily addresses the noiseless, exactly sparse case. Extensions to handle measurement noise and signals that are only well-approximated by sparse fusion frame representations are acknowledged as important future work.
  • RIP Extension: The analysis for RIP guarantees is still under development and is noted as an open problem.
  • Dimension of Subspaces: The RIP analysis does not impose constraints on the dimensions of the subspaces ($m_j$), and the authors speculate that larger subspace dimensions might intuitively lead to easier recovery, though this is not proven in the current worst-case setting.
  • Practical Implementation: While theoretical guarantees are provided, the paper focuses on the mathematical framework. Further research into efficient practical algorithms for implementing these recovery techniques would be valuable.

Summary updated

Abstract

Compressed Sensing (CS) is a new signal acquisition technique that allows sampling of sparse signals using significantly fewer measurements than previously thought possible. On the other hand, a fusion frame is a new signal representation method that uses collections of subspaces instead of vectors to represent signals. This work combines these exciting new fields to introduce a new sparsity model for fusion frames. Signals that are sparse under the new model can be compressively sampled and uniquely reconstructed in ways similar to sparse signals using standard CS. The combination provides a promising new set of mathematical tools and signal models useful in a variety of applications. With the new model, a sparse signal has energy in very few of the subspaces of the fusion frame, although it needs not be sparse within each of the subspaces it occupies. We define a mixed &ell;<sub>1</sub>/&ell;<sub>2</sub> norm for fusion frames. A signal sparse in the subspaces of the fusion frame can thus be sampled using very few random projections and exactly reconstructed using a convex optimization that minimizes this mixed &ell;<sub>1</sub>/&ell;<sub>2</sub> norm. The sampling conditions we derive are very similar to the coherence and RIP conditions used in standard CS theory.
BibTeX
@inproceedings{boufounos2009compressed,
  author = {Petros T. Boufounos and Gitta Kutyniok and Holger Rauhut},
  title = {{Compressed sensing for fusion frames}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {2009},
  doi = {10.1117/12.826327},
}
Figure