3
$\begingroup$

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

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

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

$\endgroup$

You must log in to answer this question.

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