Discrete Least Squares Approximation
Introduction
Given a set of points \( (x_i, y_i) \) for \( i = 0, \dots, n \), where the \( x_i \) are distinct, there exists a unique polynomial \( p(x) \) of degree at most \( n \) such that:
\[ p(x_i) = y_i, \quad \text{for all } i = 0, \dots, n \]
This polynomial is called the interpolation polynomial of the points. When the number of points is very large or the data contains noise, it is often preferable to look for a function \( g(x) \) from a certain class (polynomials, rational functions, trigonometric, exponentials, etc.) that best fits the points. This process is known as approximation, smoothing, or regression.
Problem Formulation
Consider a family of linearly independent functions:
\[ g_0(x), g_1(x), \dots, g_m(x), \quad \text{with } m \leq n \]
We seek a linear combination:
\[ g(x) = \sum_{i=0}^{m} a_i g_i(x) \]
Define the quadratic error:
\[ E(a) = \sum_{i=0}^{n} \left( g(x_i) - y_i \right)^2 = \sum_{i=0}^{n} \left( \sum_{j=0}^{m} a_j g_j(x_i) - y_i \right)^2 \]
The approximation problem is: find \( a \in \mathbb{R}^{m+1} \) that minimizes \( E(a) \).
Polynomial Regression Case
Choosing \( g_i(x) = x^i \) for \( i = 0, \dots, m \), we get:
\[ g(x) = a_0 + a_1 x + \dots + a_m x^m \]
The function to minimize becomes:
\[ E(a) = \sum_{i=0}^{n} \left( a_0 + a_1 x_i + \dots + a_m x_i^m - y_i \right)^2 \]
Computing partial derivatives:
\[ \frac{\partial E}{\partial a_k} = 2 \sum_{i=0}^{n} \left( \sum_{j=0}^{m} a_j x_i^j - y_i \right) x_i^k, \quad k = 0, \dots, m \]
This yields a linear system \( A \cdot a = b \) where:
- \( A = \left( \sum_{i=0}^{n} x_i^{j+k} \right)_{0 \le j,k \le m} \)
- \( b = \left( \sum_{i=0}^{n} y_i x_i^j \right)_{0 \le j \le m} \)
Linear Regression (m = 1)
For the linear case, the system becomes:
\[ \begin{cases} (n+1) a_0 + \sum x_i a_1 = \sum y_i \\ \sum x_i a_0 + \sum x_i^2 a_1 = \sum x_i y_i \end{cases} \]
\[ a_1 = \frac{(n+1) \sum x_i y_i - \sum x_i \sum y_i}{(n+1) \sum x_i^2 - (\sum x_i)^2}, \quad a_0 = \frac{\sum y_i \sum x_i^2 - \sum x_i \sum x_i y_i}{(n+1) \sum x_i^2 - (\sum x_i)^2} \]
Example
Determine the least squares line approximating the following data:
| \( x_i \) | 0.5 | 0.5 | 1 | 1.5 | 2 | 2.5 | 3 | 3.5 | 4 | 4 | 4.5 | 4.75 | 5.5 | 6 | 6 | 6.5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \( y_i \) | 0.5 | 1 | 1 | 1.25 | 1 | 1 | 1.5 | 1.5 | 1.5 | 2 | 2 | 1.75 | 2 | 2 | 2.25 | 2.25 |
Calculations:
- \( n + 1 = 16 \)
- \( \sum x_i = 55.75 \)
- \( \sum y_i = 24.75 \)
- \( \sum x_i^2 = 254.5625 \)
- \( \sum x_i y_i = 101.8125 \)
Thus:
\[ a_0 = \frac{24.75 \times 254.5625 - 55.75 \times 101.8125}{16 \times 254.5625 - (55.75)^2} = 0.64706 \]
\[ a_1 = \frac{16 \times 101.8125 - 55.75 \times 24.75}{16 \times 254.5625 - (55.75)^2} = 0.25824 \]