Approximation algorithms for wavelet transform coding of data streams

Simple item page
dc.creatorGuha, Sudipto
dc.creatorHarb, Boulos
dc.date2006-04-25
dc.date2007-07-22
dc.date.accessioned2026-07-07T08:19:28Z
dc.date.available2026-07-07T08:19:28Z
dc.descriptionThis paper addresses the problem of finding a B-term wavelet representation of a given discrete function $f \in \real^n$ whose distance from f is minimized. The problem is well understood when we seek to minimize the Euclidean distance between f and its representation. The first known algorithms for finding provably approximate representations minimizing general $\ell_p$ distances (including $\ell_\infty$) under a wide variety of compactly supported wavelet bases are presented in this paper. For the Haar basis, a polynomial time approximation scheme is demonstrated. These algorithms are applicable in the one-pass sublinear-space data stream model of computation. They generalize naturally to multiple dimensions and weighted norms. A universal representation that provides a provable approximation guarantee under all p-norms simultaneously; and the first approximation algorithms for bit-budget versions of the problem, known as adaptive quantization, are also presented. Further, it is shown that the algorithms presented here can be used to select a basis from a tree-structured dictionary of bases and find a B-term representation of the given function that provably approximates its best dictionary-basis representation.
dc.descriptionAdded a universal representation that provides a provable approximation guarantee under all p-norms simultaneously
dc.identifierhttps://arxiv.org/abs/cs/0604097
dc.identifierhttp://arxiv.org/abs/cs/0604097
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/134775
dc.subjectData Structures and Algorithms
dc.subjectG.1.2
dc.titleApproximation algorithms for wavelet transform coding of data streams
dc.typetext

Files

Collections

arXiv