DIMACS TR: 2004-25

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)$.