## DIMACS TR: 2004-42

##
Nonuniform Sparse Approximation with Haar Wavelet Basis

### Author: S. Muthukrishnan

**
ABSTRACT
**
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