Abstract
We address the problem of finding sparse wavelet representations of highdimensional vectors. We present a lowerbounding technique and use it to develop an algorithm for computing provablyapproximate instancespecific representations minimizing general $ell_p$ distances under a wide variety of compactlysupported wavelet bases. More specifically, given a vector $f in mathbb{R}^n$, a compactlysupported wavelet basis, a sparsity constraint $B in mathbb{Z}$, and $pin[1,infty]$, our algorithm returns a $B$term representation (a linear combination of $B$ vectors from the given basis) whose $ell_p$ distance from $f$ is a $O(log n)$ factor away from that of the optimal such representation of $f$. Our algorithm applies in the onepass sublinearspace data streaming model of computation, and it generalize to weighted $p$norms and multidimensional signals. Our technique also generalizes to a version of the problem where we are given a bitbudget rather than a termbudget. Furthermore, we use it to construct a emph{universal representation} that consists of at most $B(log n)^2$ terms and gives a $O(log n)$approximation under all $p$norms simultaneously.
BibTeX  Entry
@InProceedings{guha_et_al:DagSemProc.07071.14,
author = {Guha, Sudipto and Harb, Boulos},
title = {{Nonlinear Approximation and Image Representation using Wavelets}},
booktitle = {Web Information Retrieval and Linear Algebra Algorithms},
pages = {118},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {18624405},
year = {2007},
volume = {7071},
editor = {Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2007/1063},
URN = {urn:nbn:de:0030drops10634},
doi = {10.4230/DagSemProc.07071.14},
annote = {Keywords: Nonlinear approximation, wavelets, approximation algorithms, streaming algorithms}
}
Keywords: 

Nonlinear approximation, wavelets, approximation algorithms, streaming algorithms 
Collection: 

07071  Web Information Retrieval and Linear Algebra Algorithms 
Issue Date: 

2007 
Date of publication: 

28.06.2007 