An Exact Tree Projection Algorithm for Wavelets

Coralia Cartis, Andrew Thompson

Research output: Contribution to journalArticlepeer-review

Abstract

We propose a dynamic programming algorithm for projection onto wavelet tree structures. In contrast to other recently proposed algorithms which only give approximate tree projections for a given sparsity, our algorithm is guaranteed to calculate the projection exactly. We also prove that our algorithm has O(N kappa) complexity, where N is the signal dimension and is the sparsity of the tree approximation.

Original languageEnglish
Pages (from-to)1028-1031
Number of pages4
JournalIEEE Signal Processing Letters
Volume20
Issue number11
DOIs
Publication statusPublished - Nov 2013

Keywords

  • Complexity analysis
  • compressed sensing
  • dynamic programming
  • sparse representations
  • wavelets
  • APPROXIMATION

Cite this