# Iterative model fitting

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: 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) ).

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

Other:
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.

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.
Use $orthonormal$ basis so there is no need in normalization.