### Technical Report ERGO 13-006

#### An exact tree projection algorithm for wavelets

*Coralia Cartis and Andrew Thompson*

##### 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(Nk)
complexity, where N is the signal dimension and k is the sparsity of the tree
approximation.

##### Keywords:

Sparse representations, wavelets, dynamic programming, complexity analysis, compressed sensing

##### Download:

ERGO-13-006.pdf

##### Status:

Submitted for publication