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

-

## 1 Answer

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)

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 18, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.920316219329834, "perplexity_flag": "middle"}