A sparse approximation problem

Given an orthonormal basis of vectors B_1,...,B_n over n dimensions, k and n-dimensional vector V, the problem is to represent V using linear combination of at most k basis vectors. That is, find U=\sum_{i=1,..,k} a_i B_X_i, where each X_i is some B_j. Goal is to minimize ||V-U||^2 = \sum_i (V[i]-U[i])^2. Parseval's theorem implies that one can pick the k largest of | V DOT B_i |'s to minimize the error.

I have been interested in the problem of minimizing \sum_i W[i](V[i]-U[i])^2 for a given weight vector W. That is, the problem is to minimize weighted sum squared error where different dimensions have possibly different weights. It is a natural extension. Parseval's is not optimal anymore; it is acutally a long conversation to convince researchers that simple hacks like reducing the problem to \sqrt{W[i]}V[i] or (B_i DOT W) and applying Parseval's does not get optimal results (all such heuristics essentially end of solving the problem with a transform not in the original basis).

Problem: Design a polynomial time algorithm for any basis (even specific ones such as say Fourier) or prove its hardness. Known results: Special cases of Haar wavelets. Guha and Harb show that picking k largest with different scaling gives good approximations for other errors such as L_p and MAX_i ||V[i]-U[i]||, in SODA06.

Evangelizing: There is an applied algorithms perspective here that many miss. The reason a certain basis is used is because in a given application, most realistic signals are well represented by only a small number k of them and hence the basis is the most suitable for signals from that application. Therefore, it is really only sensible to ask the problem above when W has some of the properties of the basis vectors, and is not arbitrary. This eventually gets tricky to formalize. I tried an approach for the weighted problem and Haar basis in a paper, but this is far from what we need to know for other basis, and say for other error norms.