Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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$)? – J. M. 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
up vote 1 down vote accepted

This is known as the basis-pursuit problem. See the tutorials that I pointed to here:

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.