An exact tree projection algorithm for wavelets

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.

4 pages, 1 figure

Cited by in corpus (5)

• On problems equivalent to (min,+)-convolution
• Model-based Sketching and Recovery with Expanders
• Approximation Algorithms for Model-Based Compressive Sensing
• Inexact Gradient Projection and Fast Data Driven Compressed Sensing
• Improved Algorithms For Structured Sparse Recovery