Module matching_pursuit 

Matching Pursuit Module

Provides sparse signal decomposition using Matching Pursuit (MP) and Orthogonal Matching Pursuit (OMP) algorithms. These methods decompose signals into a sparse linear combination of atoms from an overcomplete dictionary.

Mathematical Background

Given a signal x and a dictionary D = {d_k}, Matching Pursuit finds a sparse representation:

x ≈ Σ α_k d_k

where only a few coefficients α_k are non-zero.

Matching Pursuit (MP):

• Greedy algorithm selecting best-matching atoms iteratively
• Simple but may have redundant atom selection
• Convergence: Overall energy decreases, but NOT monotonically (residual can occasionally increase between iterations)

Orthogonal Matching Pursuit (OMP):

• Orthogonalizes selected atoms at each iteration via least squares
• Better reconstruction quality than MP (typically 5-10x better)
• Guaranteed monotonic residual decrease (strict mathematical property)

Applications

• Compression: Sparse representation for data compression
• Denoising: Signal denoising via sparse coding
• Feature Extraction: Identifying significant signal components
• Classification: Sparse features for machine learning

See Also

• High-level user guide: docs/USER_GUIDE.md
• Wavelet families and atom choices for dictionaries: docs/WAVELET_FAMILIES.md
• Advanced analysis overview (coherence, matching pursuit, multifractal): docs/ADVANCED_ANALYSIS.md

Example

use iron_wave::decomposition::matching_pursuit::*;
use iron_wave::wavelets::{Haar, Daubechies, DaubechiesType};
use iron_wave::{Signal, Wavelet};

// Create a test signal (sine wave)
let signal_data: Vec<f64> = (0..128)
    .map(|i| (i as f64 * 0.1).sin())
    .collect();
let signal = Signal::new(signal_data);

// Build wavelet dictionary with multiple wavelets
let wavelets: Vec<Box<dyn Wavelet>> = vec![
    Box::new(Haar::new()),
    Box::new(Daubechies::new(DaubechiesType::Db4)),
];
let dictionary = WaveletDictionary::new(wavelets, 4, signal.len())?;

// Run OMP for sparse decomposition
let result = orthogonal_matching_pursuit(
    &signal,
    &dictionary,
    50,    // max iterations
    1e-6,  // tolerance
)?;

// Analyze sparsity
println!("Sparsity: {}/{}", result.atoms_used.len(), dictionary.size());
println!("Reconstruction error: {:.6}", result.residual_energy.last().unwrap());

// Verify reconstruction
assert!(result.atoms_used.len() < dictionary.size());
assert!(*result.residual_energy.last().unwrap() < result.residual_energy[0]);

Structs

AtomIndex

Identifier for a dictionary atom

MatchingPursuitResult

Result of Matching Pursuit decomposition

WaveletDictionary

Wavelet-based dictionary for Matching Pursuit

Traits

Dictionary

Dictionary trait for Matching Pursuit

Functions

matching_pursuit

Matching Pursuit algorithm for sparse signal decomposition

orthogonal_matching_pursuit

Orthogonal Matching Pursuit algorithm