Recovery of sparse translation-invariant signals with continuous basis pursuit

Chaitanya Ekanadham, Daniel Tranchina, Eero P. Simoncelli

Research output: Contribution to journalArticle

Abstract

We consider the problem of decomposing a signal into a linear combination of features, each a continuously translated version of one of a small set of elementary features. Although these constituents are drawn from a continuous family, most current signal decomposition methods rely on a finite dictionary of discrete examples selected from this family (e.g., shifted copies of a set of basic waveforms), and apply sparse optimization methods to select and solve for the relevant coefficients. Here, we generate a dictionary that includes auxiliary interpolation functions that approximate translates of features via adjustment of their coefficients. We formulate a constrained convex optimization problem, in which the full set of dictionary coefficients represents a linear approximation of the signal, the auxiliary coefficients are constrained so as to only represent translated features, and sparsity is imposed on the primary coefficients using an L1 penalty. The basis pursuit denoising (BP) method may be seen as a special case, in which the auxiliary interpolation functions are omitted, and we thus refer to our methodology as continuous basis pursuit (CBP). We develop two implementations of CBP for a one-dimensional translation-invariant source, one using a first-order Taylor approximation, and another using a form of trigonometric spline. We examine the tradeoff between sparsity and signal reconstruction accuracy in these methods, demonstrating empirically that trigonometric CBP substantially outperforms Taylor CBP, which, in turn, offers substantial gains over ordinary BP. In addition, the CBP bases can generally achieve equally good or better approximations with much coarser sampling than BP, leading to a reduction in dictionary dimensionality.

Original languageEnglish (US)
Article number5893953
Pages (from-to)4735-4744
Number of pages10
JournalIEEE Transactions on Signal Processing
Volume59
Issue number10
DOIs
StatePublished - Oct 2011

Keywords

  • Basis pursuit
  • L1 optimization
  • feature decomposition
  • interpolation
  • sparsity
  • transformation-invariance

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Recovery of sparse translation-invariant signals with continuous basis pursuit'. Together they form a unique fingerprint.

  • Cite this