Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition

Y. C. Pati; R. Rezaiifar; P. S. Krishnaprasad

doi:10.1109/acssc.1993.342465

Abstract

We describe a recursive algorithm to compute representations of functions with respect to nonorthogonal and possibly overcomplete dictionaries of elementary building blocks e.g. affine (wavelet) frames. We propose a modification to the matching pursuit algorithm of Mallat and Zhang (1992) that maintains full backward orthogonality of the residual (error) at every step and thereby leads to improved convergence. We refer to this modified algorithm as orthogonal matching pursuit (OMP). It is shown that all additional computation required for the OMP algorithm may be performed recursively.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>

Keywords

Matching pursuitOrthogonalityResidualAlgorithmWaveletConvergence (economics)Matching (statistics)Affine transformationMathematicsComputer scienceFunction (biology)Mathematical optimizationArtificial intelligenceCompressed sensingPure mathematics

Affiliated Institutions

Related Publications

Greed is Good: Algorithmic Results for Sparse Approximation

Joel A. Tropp

This article presents new results on using a greedy algorithm, orthogonal matching pursuit (OMP), to solve the sparse approximation problem over redundant dictionaries. It provi...

2004 IEEE Transactions on Information Theory 3639 citations

Atomic Decomposition by Basis Pursuit

Scott Shaobing Chen , David L. Donoho , Michael A. Saunders

The time-frequency and time-scale communities have recently developed a large number of overcomplete waveform dictionaries---stationary wavelets, wavelet packets, cosine packets...

2001 SIAM Review 5046 citations

Atomic Decomposition by Basis Pursuit

Scott Shaobing Chen , David L. Donoho , Michael A. Saunders

The time-frequency and time-scale communities have recently developed a large number of overcomplete waveform dictionaries --- stationary wavelets, wavelet packets, cosine packe...

1998 SIAM Journal on Scientific Computing 6879 citations

Entropy-based algorithms for best basis selection

Ronald R. Coifman , Mladen Victor Wickerhauser

Adapted waveform analysis uses a library of orthonormal bases and an efficiency functional to match a basis to a given signal or family of signals. It permits efficient compress...

1992 IEEE Transactions on Information Theory 3140 citations

Matching pursuits with time-frequency dictionaries

Stéphane Mallat , Zhifeng Zhang

The authors introduce an algorithm, called matching pursuit, that decomposes any signal into a linear expansion of waveforms that are selected from a redundant dictionary of fun...

1993 IEEE Transactions on Signal Processing 8998 citations

Publication Info

Year: 2002
Type: article
Citations: 4259
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

4259

OpenAlex

Cite This

APA Style

                            
                                    Y. C. Pati, 
                                
                                    R. Rezaiifar, 
                                
                                    P. S. Krishnaprasad
                                
                            (2002). 
                            Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition. 
                            
                            .
                            https://doi.org/10.1109/acssc.1993.342465

Identifiers

DOI: 10.1109/acssc.1993.342465