Sequential Non Linear Least Squares Problem

Question

I have the the following non-linear function, $$s(x;A_k,\mu_k,\sigma_k)=\sum_{k=1}^2 A_k \exp\left(\frac{-(x-\mu_k)^2}{\sigma_k^2}\right)$$ with unknown (but deterministic) parameters $A_k,\mu_k,\sigma_k$.

The received signal is as follows: $$r(x;A_k,\mu_k,\sigma_k)=t\cdot s(x;A_k,\mu_k,\sigma_k)+n(x)$$ where $n$ is standard white Gaussian noise and $t\geq 0$.

The task is to estimate/update the model parameters $A_k,\mu_k,\sigma_k$ online, when the next data point arrives, because the data points arrive sequentially.

Here the data points DO NOT ARRIVE randomly from the model. They arrive in the order as given by the model. Namely, the incoming points are first around zero level, then they increase, make a peak, and then decrease, and the same happens for the second exponent.

We know that $\sigma_1^2\approx \sigma_2^2$ and $\mu_2-\mu_1$ allows that two distinct peaks can be visible. The incoming values are allowed to be evaluated over a moving window of size $5\%$ or less of the whole data. All data points lying behind this window are simply lost, due to memory constraints.

I was thinking about using an iterative non-linear least squares algorithm but this method doesn't consider about how the data points arrive. It assumes that data points arrive randomly. However, in my case, with a few data points from the first exponent, if I know that those points are from the left tail, for example, and the noise level is low, I can even almost completly know $A_1$, $\mu_1$ and $\sigma_1^2$ but this is never possible with the regular non-linear least squares. Hence, my question is the following:

What is the best method to solve this problem?

Answer 1

I have the the following non-linear function [...]

This would be a bimodal distribution with two different means and deviations ($\mu_1, \sigma_1, \mu_2, \sigma_2$), two sub population sizes $A_1, A_2$ and an extra parameter $t$ that modulates $A_1, A_2$.

Here the data points DO NOT ARRIVE randomly from the model. They arrive in the order as given by the model. Namely, the incoming points are first around zero level, then they increase, make a peak, and then decrease, and the same happens for the second exponent.

What you are describing is plain simple curve fitting of some curve to data points as opposed to fitting data to a distribution.

The typical fitting scenario involves the use of Newton's method to find those parameters that minimise the value of the error function and here it is possible to differentiate the sum of the Gaussians with respect to the parameters (which is a common requirement for both linear and non-linear methods).

Here are a few practical examples: One, two, three (different platform).

If you can use details of your problem to fix the starting points of the fit, it will help immensely with convergence. There are some cases for example where the method converges but when you look at the fit, one curve has simply absorbed the other.

Can it be done with an online algorithm? No. Not in this case.

In general, there are online algorithms that will "learn" the coefficients of a model in a "sample-by-sample" basis. But this refers to working out parameters of a model that minimise an error function. Evaluating the error, implies a full "snapshot" of what is being fitted (i.e. all of the data to obtain one estimate of $s$).

Here, it is impossible to predict what sample comes next and from which possible realisation of the 6 parameter model. But there might be a thin region of cases where you could make an inference provided that you can apply additional constraints.

You might see this problem as a combination of a tracking and a classification problem where you can say "I know how the curve is supposed to evolve and all I have to do is track its evolution and raise a flag when the uncertainty falls below a level", but then again you don't really know which 6 parameter realisation to track. This is what you are trying to infer.

It is impossible to "guess the future" unless there are certain constraints.

What do the first few "... incoming points are first around zero level,..." tell you about the value of $A_1,\mu_1, \sigma_1, A_2, \mu_2, \sigma_2$? Nothing. You can still attempt a "fit" (batch or online) but you will get back nonsensical results and a huge error. So, we have to wait for more data. But then again, if we wait long enough to be sure we have one of the curves "in", then, we probably can make a quick guess about the $A$s provided that we know what $A_1+A_2$ is in general (another constraint). But still, this leaves us with no way of guessing what the $\mu_2, \sigma_2$ would be. We still have to wait for more data.

If the problem you are dealing with can already inform you about nonsensical values for the 6 parameters or at least the range they are supposed to be in or some sort of relationship between the two triplets of parameters, or anything else that could be used to reduce your search space, then, you might be able to pre-calculate a very large number of realisations of $s$ for all the different possible 6 parameter combinations and then track the evolution of each one as a new sample comes in. Which is basically, nearest neighbour classification.

But still, you would probably need to wait almost for the whole curve to come "in" to be able to make a certain decision.

If you start tracking a single Gaussian curve with your eye, you cannot really tell what $A, \mu, \sigma$ are until the trace starts curving to begin forming the peak. Add to this the noise and you have more than one possible curves that could be passing from the same data. So, you probably have to wait for at least $\frac{3}{4}$ of the data to come "in", before you can make a valid estimate.

Hope this helps.