DIMACS TR: 2004-25
Workload-Optimal Wavelet Synposis
Author: S. Muthukrishnan
ABSTRACT
We present the first known polynomial time for the problem of finding
$B$ wavelet vectors to represent a signal of length $N$ so that the
representation has the smallest error, averaged over a given workload
of the probability of each point in the signal being queried.
Previously known results trivially
determined the $B$ wavelet vectors with the largest (in absolute
value) coefficients; by Parseval's inequality, this is the representation
with least error for {\em uniform} workload where all points are equally
likely to be queried. This is no longer true for arbitrary, non-uniform
workloads, and our first known polynomial time algorithm makes use of
two different kinds of exhaustive searches to determine the workload
optimal $B$-term representation in time $O(N^2B/\log B)$.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-25.ps.gz
DIMACS Home Page