Cooperative Greedy Pursuit Strategies

Cooperative Greedy Pursuit algorithms are designed for producing the atomic decomposition of a signal partition, subjected to a global constraint on sparsity.

The cooperation between partition units is realized in several ways:

i)By ranking the partition units for their sequential stepwise approximation: Hierarchiezed Blockwise Orthogonal Matching Pursuit (HBW-OMP) and Hierarchiezed Blockwise Optimized Orthogonal Matching Pursuit (HBW-OOMP)

ii)By ranking the partition units for stepwise downgrading of the whole approximation: Hierarchiezed Blockwise Backwards Optimized Orthogonal Matching Pursuit (HBW-BOOMP).

iii)By allowing for migration of atoms, from some partition units to another partition units, to improve the approximation quality: Hierarchiezed Blockwise Swapping Refinement of OMP/OOMP (HBW-SR-OMP/OOMP).

The algorithm details are given in the paper:

`Cooperative Greedy Pursuit Strategies for Sparse Signal Representation by Partitioning'
by Laura Rebollo-Neira

The MATLAB routines for implementing the numerical examples in the papers are available in the archive Cooperative.zip. A description of the archive content can be found in the file Cooperative_info.pdf. The routines are dedicated to the use of trigonometric dictionaries for achieving high quality approximation of musical signals. The examples illustrate:

i)The gain in the sparsity achieved by redundant trigonometric dictionaries, in comparison with the corresponding trigonometric orthogonal basis (133% improvement in the piano melody given below, approximated up to SNR=36dB).

ii)The gain in the sparsity achieved by the proposed HBW-OMP/OOMP strategies, restricted by a global constraint on sparsity, in comparison with the standard OMP/OOMP approximation of every partition to the same quality (133% improvement in the piano melody below).

Piano melody. Credit: Julius O. Smith, Center for Computer Research in Music and Acoustics (CCRMA), Stanford University, website Reproduced below

Play original melody

Piano melody approximated up to SNR=36dB

Play sparse approximation

Highly Nonlinear Approximations for Sparse Signal Representation

Cooperative Greedy Pursuit Strategies