RobOMP: Robust variants of Orthogonal Matching Pursuit for sparse representations

Carlos A. Loza

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


Sparse coding aims to find a parsimonious representation of an example given an observation matrix or dictionary. In this regard, Orthogonal Matching Pursuit (OMP) provides an intuitive, simple and fast approximation of the optimal solution. However, its main building block is anchored on the minimization of the Mean Squared Error cost function (MSE). This approach is only optimal if the errors are distributed according to a Gaussian distribution without samples that strongly deviate from the main mode, i.e. outliers. If such assumption is violated, the sparse code will likely be biased and performance will degrade accordingly. In this paper, we introduce five robust variants of OMP (RobOMP) fully based on the theory of M-Estimators under a linear model. The proposed framework exploits efficient Iteratively Reweighted Least Squares (IRLS) techniques to mitigate the effect of outliers and emphasize the samples corresponding to the main mode of the data. This is done adaptively via a learned weight vector that models the distribution of the data in a robust manner. Experiments on synthetic data under several noise distributions and image recognition under different combinations of occlusion and missing pixels thoroughly detail the superiority of RobOMP over MSE-based approaches and similar robust alternatives. We also introduce a denoising framework based on robust, sparse and redundant representations that open the door to potential further applications of the proposed techniques. The five different variants of RobOMP do not require parameter tuning from the user and, hence, constitute principled alternatives to OMP.

Original languageEnglish
Article numbere192
JournalPeerJ Computer Science
Issue number5
StatePublished - 2019


  • M-Estimation
  • Matching Pursuit
  • Outliers
  • Representation-based classifier
  • Robust classification
  • Sparse representation


Dive into the research topics of 'RobOMP: Robust variants of Orthogonal Matching Pursuit for sparse representations'. Together they form a unique fingerprint.

Cite this