DIMACS TR: 2004-42

Nonuniform Sparse Approximation with Haar Wavelet Basis

Author: S. Muthukrishnan

Sparse approximation theory concerns representing a given signal on $N$ pointsas a linear combination of at most $B$ ($B\ll N$) elements from a dictionary so that the error of the representation is minimized; traditionally, error is taken {\em uniformly} as the sum of squares of errors at each point.

In this paper, we initiate the study of {\em nonuniform} sparse approximation theory where each point has an {\em importance}, and we want to minimize the sum of individual errors weighted by their importance. In particular, we study this problem with the basic Haar wavelet dictionary that has found many applications since being introduced in 1910. Parseval's theorem from 1799 which is central in solving uniform sparse approximation for Haar wavelets does not help under nonuniform importance.

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 the given importance of the points. The algorithm takes time $O(N^2B/\log B)$. When the importance function is well-behaved, we present another algorithm that takes near-linear time. Our methods also give first known, efficient algorithms for a number of related problems with nonuniform importance.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-42.ps.gz

DIMACS Home Page