1 Search Results for "Guha, Sudipto"

Document

Nonlinear Approximation and Image Representation using Wavelets

Authors: Sudipto Guha and Boulos Harb

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)

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.

Cite as

Sudipto Guha and Boulos Harb. Nonlinear Approximation and Image Representation using Wavelets. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@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 =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.14},
  URN =		{urn:nbn:de:0030-drops-10634},
  doi =		{10.4230/DagSemProc.07071.14},
  annote =	{Keywords: Nonlinear approximation, wavelets, approximation algorithms, streaming algorithms}
}

Refine by Author
1 Guha, Sudipto
1 Harb, Boulos

Refine by Classification

Refine by Keyword
1 Nonlinear approximation
1 approximation algorithms
1 streaming algorithms
1 wavelets

Refine by Type
1 document

Refine by Publication Year
1 2007

1 Search Results for "Guha, Sudipto"

Nonlinear Approximation and Image Representation using Wavelets

Abstract

Cite as

Thanks for your feedback!

Could not send message