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