Matching Pursuits with Random Sequential Subdictionaries

Abstract :

Matching pursuits are a class of greedy algorithms commonly used in signal processing, for solving the sparse approximation problem. They rely on an atom selection step that requires the calculation of numerous projections, which can be computationally costly for large dictionaries and burdens their competitiveness in coding applications. We propose using a non adaptive random sequence of subdictionaries in the decomposition process, thus parsing a large dictionary in a probabilistic fashion with no additional projection cost nor parameter estimation. A theoretical modeling based on order statistics is provided, along with experimental evidence showing that the novel algorithm can be efficiently used on sparse approximation problems. An application to audio signal compression with multiscale time-frequency dictionaries is presented, along with a discussion of the complexity and practical implementations.

Complete list of metadatas

Cited literature [43 references]  Display  Hide  Download

https://hal-imt.archives-ouvertes.fr/hal-00696181
Contributor : Admin Télécom Paristech <>
Submitted on : Friday, May 11, 2012 - 10:42:33 AM
Last modification on : Thursday, July 4, 2019 - 11:00:03 AM
Long-term archiving on : Sunday, August 12, 2012 - 2:22:02 AM

File

Moussallam2012_RSSMP.pdf
Files produced by the author(s)

Identifiers

Citation

Manuel Moussallam, L. Daudet, G. Richard. Matching Pursuits with Random Sequential Subdictionaries. Signal Processing, Elsevier, 2012, pp.2532-2544. ⟨10.1016/j.sigpro.2012.03.019⟩. ⟨hal-00696181⟩

Share

Metrics

Record views

348

Files downloads

662