DocumentCode
79963
Title
An Exact Tree Projection Algorithm for Wavelets
Author
Cartis, Coralia ; Thompson, Andrew
Author_Institution
Sch. of Math. & the Maxwell Inst., Univ. of Edinburgh, Edinburgh, UK
Volume
20
Issue
11
fYear
2013
fDate
Nov. 2013
Firstpage
1026
Lastpage
1029
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
approximation theory; dynamic programming; signal processing; trees (mathematics); wavelet transforms; O(Nk) complexity; approximate tree projections; dynamic programming; exact tree projection; signal dimension; sparsity; tree approximation; wavelet tree structures; Approximation algorithms; Approximation methods; Context; Dynamic programming; Heuristic algorithms; Vectors; Wavelet transforms; Complexity analysis; compressed sensing; dynamic programming; sparse representations; wavelets;
fLanguage
English
Journal_Title
Signal Processing Letters, IEEE
Publisher
ieee
ISSN
1070-9908
Type
jour
DOI
10.1109/LSP.2013.2278147
Filename
6578067
Link To Document