WUT_Computer_Science/NotProgramming/ENUME/projectC/sections/02-theoretical-introduction.tex

\section{Theoretical introduction}
\subsection{Linear Least Squares Problem}
We have polynomial function:
\[ y(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x^1 + a_0 \]
where n - degree of the polynomial we use to approximate function \\
Given matrix $\mathbf{A} \in \mathbb{R}^{m \times n} \quad (m > n)$ and vector $\mathbf{y} \in \mathbb{R}^m$ \\
We need to find vector \^{x} such that:
\[ 	\forall x \in \mathbb{R}^n \quad|| \mathbf{y} - \mathbf{A} \hat{x} ||_2 \leq || \mathbf{y} - \mathbf{A}x ||_2  \]
$\mathbf{A}\hat{x}$ is the vector of values of the approximating function at each data point and $y$ is the vector of values of data points. \\
We have to minimize the Euclidean norm of difference between approximation and data points. \\
To obtain $\hat{x}$ we will calculate the derrivative of error function with respect to $b_n$ and equate it to 0. This way we will get system of equations caled \textbf{normal equations} which have unique solution in form of vector $\hat{x}$

\subsection{Gram matrix and QR decomposition}
We will use Gram's matrix since it's condition number tends to be pretty high which improves the accuracy of our solution. \\
Gram's matrix is a matrix of set of normal equations. The simplest way to present normal equations is by using formula:
\[ \langle \phi_i, \phi_k \rangle \myeq \sum_{j=0}^N \phi_i(x_j)fi_k(x_j) \]
Which then leads to following matrix \textbf{A}:

\[
A = \begin{bmatrix}
\phi_0(x_0) & \phi_1(x_0) &  \dots & \phi_n(x_0) \\
\phi_0(x_1) & \phi_1(x_1) & \dots & \phi_n(x_1) \\
\phi_0(x_2) & \phi_1(x_2) & \dots & \phi_n(x_2) \\
\vdots & \vdots & \vdots & \vdots \\
\phi_0(x_N) & \phi_1(x_N) & \dots & \phi_n(x_N) \\
\end{bmatrix}
\]

In our case we define matrix \textbf{A} as:
\[
A = \begin{bmatrix}
1 & x_0 & (x_0)^2  & \dots & (x_0)^n \\
1 & x_1 & (x_1)^2 &  \dots & (x_1)^n\\
1 & x_2 & (x_2)^2 &  \dots & (x_2)^n\\
\vdots & \vdots & \vdots & \vdots \\
1 & x_N & (x_N)^2 &  \dots & (x_N)^n\\
\end{bmatrix}
\]

Where $x_N$ is the x-axis position for the N-th data point. Then we can express system of natural equations using A in this way:
\[ A^Ty = (A^TA)\hat{x} \]

With condition number of A equal to square root of condition number of Gram's matrix which gives us small errors. It is also usefull for QR factoization since we can rewrite it as follows:
\[ (R^TQ^T)(QR)\hat{x} = (R^TQ^T)y \]
Since determinant of $R \neq 0$ and $Q^TQ = I$ we can simplify aforementioned equation to:
\[ R\hat{x} = Q^Ty \]
And to optimize even further ahead insetead of using QR decomposition we can use faster $\tilde{Q}\tilde{R}$ decomposition:
\[ \tilde{R}\hat{x} = (\tilde{Q}^T\tilde{Q})^{-1}(\tilde{Q}^T) \]
This is faster since $\tilde{R}$ is an upper triangular matrix, easily solved using back-substitution.

\subsection{Gram-Schmidt algorithm}
We will use Gram-Schmidt algorithm for $\tilde{Q}\tilde{R}$ decomposition.
Gram-Schmidt algorithm takes non-orthogonal function basis denoted as:
\[ \phi_0, \dots, \phi_n \]
and orthogonalizes it into orthogonal function basis denoted as:
\[ \psi_0, \dots, \psi_n \]
Standard Gram-Schmid algorithm looks like this:
\[ \psi_0 = \phi_0 \]
\[ \psi_1 = \phi_1 - \frac{\langle \psi_0, \phi_1 \rangle}{\langle \psi_0, \psi_0 \rangle} \psi_0 \]
\[ \psi_n = \phi_n - \sum_{j = 0}^{i-1}  \frac{\langle \psi_j, \phi_i \rangle}{\langle \psi_j, \psi_j \rangle} \psi_j \]
Where $ i = 2, \dots, n $
Then we get a very well conditioned set of normal equations:
\[ a_0\langle \psi_0, \psi_0 \rangle = \langle f, \psi_0 \rangle \]
\[ a_1\langle \psi_1, \psi_1 \rangle = \langle f, \psi_1 \rangle \]
\[ \vdots \]
\[ a_n\langle \psi_n, \psi_n \rangle = \langle f, \psi_n \rangle \]