Guha, Sudipto ;
Harb, Boulos
Nonlinear Approximation and Image Representation using Wavelets
Abstract
We address the problem of finding sparse wavelet representations of high-dimensional vectors. We present a lower-bounding technique and use it to develop an algorithm for computing provably-approximate instance-specific representations minimizing general $ell_p$ distances under a wide variety of compactly-supported wavelet bases. More specifically, given a vector $f in mathbb{R}^n$, a compactly-supported 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 one-pass sublinear-space 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 bit-budget rather than a term-budget. 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:DSP:2007:1063,
author = {Sudipto Guha and Boulos Harb},
title = {Nonlinear Approximation and Image Representation using Wavelets},
booktitle = {Web Information Retrieval and Linear Algebra Algorithms},
year = {2007},
editor = {Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
number = {07071},
series = {Dagstuhl Seminar Proceedings},
ISSN = {1862-4405},
publisher = {Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2007/1063},
annote = {Keywords: Nonlinear approximation, wavelets, approximation algorithms, streaming algorithms}
}
|
Keywords: |
|
Nonlinear approximation, wavelets, approximation algorithms, streaming algorithms |
|
Seminar: |
|
07071 - Web Information Retrieval and Linear Algebra Algorithms
|
|
Related Scholarly Article: |
|
|
|
Issue date: |
|
2007 |
|
Date of publication: |
|
2007 |
2007