TL;DR
This paper introduces LocOMP, a novel greedy algorithm for sparse signal approximation that significantly speeds up computations for large signals with shift-invariant dictionaries. By focusing on a local neighborhood of atoms, LocOMP achieves approximation quality comparable to OMP and GP but with a computational cost drastically reduced, making it practical for real-world applications.
What Problem Does This Paper Address?
Sparse approximation, the idea of representing a signal using only a few "atoms" from a larger dictionary, is crucial in many fields like signal compression and compressed sensing. However, finding the best sparse representation is computationally expensive, especially for large signals. Existing greedy algorithms like Matching Pursuit (MP), Orthogonal Matching Pursuit (OMP), and Gradient Pursuit (GP) offer different trade-offs between speed and accuracy. While MP is fast, it's less accurate. OMP and GP provide better accuracy but are prohibitively slow for large signals due to their reliance on the entire dictionary and signal dimension in their computations. This paper addresses the need for a sparse approximation algorithm that is both accurate and scalable to large signals, particularly those with shift-invariant dictionaries (like wavelets or Gabor atoms), which are common in signal processing.
Methods
The core innovation is the LocOMP (Local Orthogonal Matching Pursuit) algorithm. It builds upon the principles of OMP but introduces a crucial modification: instead of considering the entire dictionary at each step, LocOMP focuses on a local neighborhood of atoms around the currently selected ones.
Here's how it works:
- Selection: Similar to OMP, it selects an atom based on its correlation with the current residual.
- Neighborhood Selection: This is the key difference. Instead of orthogonalizing against all previously selected atoms (as in OMP), LocOMP defines a "neighborhood" of atoms around the newly selected one. This neighborhood is typically defined by the support of the atoms and is much smaller than the full dictionary.
- Update: The algorithm then updates the sparse coefficients and the residual by projecting onto this smaller sub-dictionary. This significantly reduces the computational burden.
The paper also discusses how this "locality" property, which is inherent in shift-invariant dictionaries, can be exploited. The residual only changes locally after an atom update, meaning computations can be restricted to this local region.
Datasets
The paper uses an excerpt from the RWC (Real World Computing) music database for evaluation. Specifically, a one-minute mono-channel jazz guitar audio signal, downsampled to 8kHz (resulting in a signal dimension N ≈ 5·10⁵), was used. This is a standard benchmark for audio signal processing tasks.
Key Insights and Ideas
- Locality is Key: The paper powerfully demonstrates that the inherent locality of shift-invariant dictionaries can be leveraged to dramatically speed up greedy algorithms.
- Neighborhood Matters More Than Global Orthogonalization: The insight is that for achieving good sparse approximations, focusing on a relevant local set of atoms for orthogonalization is often sufficient and much more efficient than global orthogonalization.
- Bridging the Gap: LocOMP effectively bridges the gap between the speed of MP and the accuracy of OMP/GP, offering a practical solution for large-scale sparse approximation.
- Scalability is Achieved: The algorithm's complexity scales with the dictionary's atom support size (L) rather than the signal dimension (N), making it suitable for signals with millions of samples.
Key Results
- Speedup: LocOMP achieved a computational cost that was 500 times smaller than OMP/GP on a large audio signal, while being only about 1.5 times more expensive than MP. The computation time for LocOMP was 854 seconds, compared to over 5·10⁵ seconds for OMP/GP.
- Approximation Quality: LocOMP achieved approximation quality (measured by SNR) that was nearly indistinguishable from OMP and GP. The final SNR for LocOMP was only 0.01dB lower than OMP/GP, while MP was 0.6dB lower.
- Audio Coding Application: In a preliminary application to scalable audio coding, LocOMP showed promising results, achieving a 1.4dB gain in rate/distortion at high rates compared to MP.
Limitations and Future Work
- Dictionary Dependence: The performance gain of LocOMP is most pronounced with local dictionaries. For very large scales (L), comparing with OMP/GP becomes computationally infeasible, making it hard to fully assess LocOMP's advantage in such extreme cases.
- Neighborhood Definition: The choice of the "neighborhood" size and composition is a key parameter. While the paper proposes a specific heuristic (3L-2), further research might explore optimal neighborhood selection strategies.
- Future Work: The authors are implementing a localized version of Gradient Pursuit (LocGP) and believe it will lead to even lighter code. They also anticipate that this work will enable large-scale experiments and applications of sparse approximation that were previously unachievable.
Summary updated