Classifying compact convex sets with frames

Amina Chebira, Matthew Fickus, Jelena Kovačević

Research output: Contribution to journalArticlepeer-review


Classification is a fundamental image processing task. Recent empirical evidence suggests that classification algorithms which make use of redundant linear transforms will regularly outperform their nonredundant counterparts. We provide a rigorous explanation of this phenomenon in the single-class case. We begin by developing a measure-theoretic analysis of the set of points at which a given decision rule will have an intolerable chance of making a classification error. We then apply this general theory to the special case where the class is compact and convex, showing that such a class may be arbitrarily well approximated by frame sets, namely, preimages of hyperrectangles under frame analysis operators. This leads to a frame-based classification scheme in which frame coefficients are regarded as features. We show that, indeed, the accuracy of such a classification scheme approaches perfect accuracy as the redundancy of the frame grows large.

Original languageEnglish (US)
Pages (from-to)73-86
Number of pages14
JournalApplied and Computational Harmonic Analysis
Issue number1
StatePublished - Jul 2009


  • Classification
  • Convex sets
  • Decision rule
  • Frames

ASJC Scopus subject areas

  • Applied Mathematics


Dive into the research topics of 'Classifying compact convex sets with frames'. Together they form a unique fingerprint.

Cite this