Sparse representations for image decompositions

Davi Geiger, Tyng Luh Liu, Michael J. Donahue

Research output: Contribution to journalArticlepeer-review


We are given an image I and a library of templates L, such that L is an overcomplete basis for I. The templates can represent objects, faces, features, analytical functions, or be single pixel templates (canonical templates). There are infinitely many ways to decompose I as a linear combination of the library templates. Each decomposition defines a representation for the image I, given L. What is an optimal representation for I given L and how to select it? We are motivated to select a sparse/compact representation for I, and to account for occlusions and noise in the image. We present a concave cost function criterion on the linear decomposition coefficients that satisfies our requirements. More specifically, we study a 'weighted Lp norm' with 0 < p < 1. We prove a result that allows us to generate all local minima for the Lp norm, and the global minimum is obtained by searching through the local ones. Due to the computational complexity, i.e., the large number of local minima, we also study a greedy and iterative 'weighted Lp Matching Pursuit' strategy.

Original languageEnglish (US)
Pages (from-to)139-156
Number of pages18
JournalInternational Journal of Computer Vision
Issue number2
StatePublished - Sep 1999

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


Dive into the research topics of 'Sparse representations for image decompositions'. Together they form a unique fingerprint.

Cite this