# Moving least squares

Moving least squares is a method of reconstructing continuous functions from a set of unorganized point samples via the calculation of a weighted least squares measure biased towards the region around the point at which the reconstructed value is requested. In computer graphics, the moving least squares method is useful for reconstructing a surface from a set of points. Often it is used to create a 3D surface from a point cloud through either downsampling or upsampling.

## Definition Here is a 2D example. The circles are the samples and the polygon is a linear interpolation. The blue curve is a smooth approximation of order 3.

Consider a function $\displaystyle{ f: \mathbb{R}^n \to \mathbb{R} }$ and a set of sample points $\displaystyle{ S = \{ (x_i,f_i) | f(x_i) = f_i \} }$. Then, the moving least square approximation of degree $\displaystyle{ m }$ at the point $\displaystyle{ x }$ is $\displaystyle{ \tilde{p}(x) }$ where $\displaystyle{ \tilde{p} }$ minimizes the weighted least-square error

$\displaystyle{ \sum_{i \in I} (p(x_i)-f_i)^2\theta(\|x-x_i\|) }$

over all polynomials $\displaystyle{ p }$ of degree $\displaystyle{ m }$ in $\displaystyle{ \mathbb{R}^n }$. $\displaystyle{ \theta(s) }$ is the weight and it tends to zero as $\displaystyle{ s\to \infty }$.

In the example $\displaystyle{ \theta(s) = e^{-s^2} }$. The smooth interpolator of "order 3" is a quadratic interpolator.