Introduction and Least Squares

2023-07-11

Standard form of optimization

$$ p*=min_x f_0(x) \\ \text{subject to}: f_{i}(x) \leq 0,i=1,\dots,m, \\ $$

where

• vector $x \in R^n$ is the decision variable(optimization variable);
• $f_0:R^n \rightarrow R$ is the objective function;
• $f_i:R^n \rightarrow R, i=1,\dots,m$ represent the constraints
• $p^\star$ (or $x^\star$) is the optimal value

Gauss: Least square technique

Given matrix $A$, find $x$ that $Ax \approx b$.

$$ minimize_{x} ||Ax-b||^2 $$

Linear regression

$y=mx+c$

Data: $(x_n,y_n)$

$$ \begin{bmatrix} x_1 & 1 \\ x_2 & 1 \\ \vdots & \vdots \\ x_n & 1 \end{bmatrix} \begin{bmatrix} m \\ c \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix} $$

Find $m, c$ to minimize a quadratic function(a convex function)

$$ minimize_{m,c}\sum_{i=1}^n(y_i-(mx_i+c))^2. $$

How do we solve least-square

Find $Ax \in Col(A)$ that is closed to $b$.

Because $col(A)$ is a subspace, it contains zero vector. If we place $b$ starting at zero vector in $col(A)$ and we do a orthogonal projection of $b$ onto $col(A)$. Let's say the projected point on $col(A)$ is P. $BP$ is orthogonal to any vector in $col(A)$.

Let's prove vector $OP$ is the closest to $OB$. For any point in $Col(A)$ denoted as Q(other than P), is it possible $BQ$ shorter than $BP$?

Triangle BPQ is a right triangle. BQ is the hypotenuse. $BQ$ is strictly bigger than $BP$.

Want: $(Ax-b)=e$ must be orthogonal to all of the columns of A.

Dot product of every column of A and e is zero.

$$ A^T(Ax-b)=0\\ A^TAx=A^Tb\\ $$

If $A$ is invertible, $x=(A^TA)^{-1}A^Tb$. This is the vecotr $x$ that solves $min_{x}||Ax-b||^2$.