October 12, 2004

S. Muthukrishnan,
CS, Rutgers University.

Some algorithmic problems with nonuniform sparse approximation

 Abstract:

PROBLEM: Find the best M term representation for a signal using the Haar wavelet dictionary. The "new" aspect is that we are also given a weight function W. We want to minimize the *weighted* sum squared error.

RESULT: Parseval-based method does not work. We present the first known polynomial time algorithms for this problem, taking time O(n^2 M/log M) in general; when the weight function is well-behaved, the running time is near-linear.

COMMENTARY: Come for the talk, Stay for the open problems. I will play myself, an algorithmicists, asking problems in algorithmic aspects of sparse approximation theory.

Time-Frequency Brown Bag Seminar's homepage.