I have a sequence of points $\{(x_k,y_k,z_k)\}$ and I need to fit some $2D$ model $P(x,y)$ that approximates $z$ in some sense.

The $z_k$$'s$ are noisy samples of some $2D$ function $z_k = f(x,y) + n(x,y)$.
The noise $n$ is mainly shot noise ($std(n(x,y)) \approx \sqrt{f(x,y)}$).
The noise in $x_k,y_k$ can be neglected.
The data is being received sequentially and I can't "step back", i.e. once I moved to data point k+1 I can't get data point k again.

For $1D$ illustration look at the following figure: Illustration figure

I get the points one by one together with some noise component (First I get (1,3+noise), then (2,-2+noise) and so on and once I got (2,-2+noise) I can't access (1,3+noise) anymore unless I saved it somewhere).
I need a method to find\approximate the correct model parameters (In this case the polynomial coefficients: (1,-8,10) ).

I have two main objectives:
1. Good approximation.
2. Low memory requirements.

I have used least squares polynomial approximation and it's o.k. but if $C$ is the number of terms in my polynomial (Or, more generally, the number of free parameters in my model) then it requires $O(C^2)$ memory (to store the covariance matrix). I would like to be able to use only $O(C)$ memory.

Polynomial isn't mandatory.
I can give up optimality and settle for "good" approximation.
Even more, bounded error is preferred over mean error.


1 Answer 1


Actually, least squares polynomial fit will do the trick. It can be done in $O(C)$ memory (And $O(C)$ operations) as long as you use orthogonal polynomials.
In this case, the covariance matrix is diagonal (By definition of orthogonality) and there is no need in storing non diagonal elements.

Use $orthonormal$ basis so there is no need in normalization.
Carefully choose your basis according to your application needs (For example, If your problem is periodic, use sines and cosines)


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .