Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

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.

share|cite|improve this question
up vote 1 down vote accepted

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)

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.