Approximation Algorithms for Wavelet Transform Coding of Data Streams

摘要

This paper addresses the problem of finding a $B$-term wavelet representation of a given discrete function $f in {cal R}^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.