Take the 2-minute tour ×

Suppose I have a one-parameter family of basis functions $b(s,x)$, and a function $f(x)$ that I know can be represented (up to some low-amplitude noise) as a finite linear combination of these functions. If the number of functions $j$ is known, finding this combination is a trivial optimization problem, for example:

$$\min_{s_i, \lambda_i} \left\| f(x) - \sum_{i=1}^j \lambda_i b(s_i, x) \right\|_{L^2}$$

The problem is what to do if $j$ isn't known; I want to find the smallest possible $j$ such that the minimum of the above problem is less than some tolerance. I can of course try $j=1, 2, \ldots$ and stop as soon as my minimum is within tolerance, but surely there's a better way?

EDIT: It sounds like even when $j$ is known, this problem is a lot harder than I expected, due to presence of local minima. What techniques can be used to solve it?

share|improve this question
The magic words are "sparsity" and "regression". If you really want sparsity, it helps to have a richer, over-complete dictionary. –  Emre May 1 '11 at 0:53
It's not quite clear to me that this question is well-posed. Is the set of basis functions finite? How do you know that the $\min$ is attained? –  cardinal May 1 '11 at 1:01
What are your $b(s_i,x)$ like? A nonlinear least-squares problem can display a crapload of multiple minima for, say, trigonometric or exponential fitting problems. Do you even have good initial estimates for your $s_i$ (there are algorithms like "variable projection" that only need estimates for the nonlinear parameters $s_i$ and derive estimates of the linear parameters $\lambda_i$)? –  Guess who it is. May 1 '11 at 1:11
@J.M. Good point. Let's say that the bs are Gaussians centered at s_i of some fixed standard variation. –  user7530 May 1 '11 at 1:15
crapload: That must be a technical term. –  cardinal May 1 '11 at 1:15

1 Answer 1

up vote 1 down vote accepted

This is known as the basis-pursuit problem. See the tutorials that I pointed to here: http://cstheory.stackexchange.com/questions/5608/survey-on-optimization-algorithms/8612#8612

share|improve this answer

Your Answer


