Least Square

Definition:

• Minimize the square distance

Ordinary Least Square:

• Goal: ${\min }_x||Ax-b|{|}^2$ where $A$ and $b$ are parameters
• $f(x)=||Ax-b|{|}^2=||Ax|{|}^2-2(Ax{)}^{⊺}b+||b|{|}^2=x^{⊺}(A^{⊺}A)x-2x^{⊺}(A^{⊺}b)+||b|{|}^2$
• $\nabla f(x)=2A^{⊺}Ax-2A^{⊺}b=0$
• Therefore, the solution, $x^{\ast }=(A^{⊺}A{)}^{-1}{A}^{⊺}b$
  • $A$ must be full rank to have a unique solution
• Solution with QR Decomposition:
  • given an m × n matrix A with linearly independent columns and an m-vector b.
  1. QR factorization. Compute the QR factorization $A=QR$
  2. Compute $Q^{⊺}b$
  3. Back substitution. Solve the triangular equation $R\hat{x}=Q^{⊺}b$
• Solution with SVD
• When $A$ is not full rank, it is advisable to choose the minimum-norm solution to the set of solutions. This particular solution is $x=A^{†}y$

Variants of least-square problem:

Minimum-norm solutions to linear equations:

• When equations are under-determined, we may want to single out a solution with minimum Euclidean norm: ${\min }_x||x|{|}_2:Ax=y$
• Here, $A\in {\mathbb{R}}^{m\times n}$ with $m<n$, and $y\in \mathcal{R}(A)$
• Optimality conditions and full row rank case:
  • From the fundamental theorem of linear algebra, any candidate $x$ can be written as $x=A^{⊺}v+r$ where $Ar=0$. Since $A^{⊺}v,r$ are orthogonal we see that $||x|{|}_2^2=||A^{⊺}v|{|}_2^2+||r|{|}_2^2$ which proves optimal $r=0$ and $A{A}^{⊺}v=y$
  • If $A$ is full row rank, $A{A}^{⊺}$ is invertible and the unique $v$ is $(A{A}^{⊺}{)}^{-1}y$ then $x^{\ast }=A^{⊺}(A{A}^{⊺}{)}^{-1}y$

Equality-constrained LS:

• A generalization of the basic LS problem allows for the addition of linear equality constraints on the $x$ variable, resulting in the Constrained Least Square ${\min }_x||Ax-y|{|}_2^2$ subject to $Cx=d$
• This problem can be converted to standard LS by eliminating the equality constraints via a standard procedure
• First, suppose the problem is feasible, let $\bar{x}$ be such that $C\bar{x}=d$
• All feasible points (regardless of least square) can be expressed as a form $x=\hat{x}+Nz$ where $N$ contains by the column basis for $\mathcal{N}(C)$ and $z$ is a new variable
• Then we need to find $z$ such that ${\min }_z||\tilde{A}z-\tilde{y}|{|}_2^2$ where $\tilde{A}\doteq AN$ and $\tilde{y}\doteq y-A\tilde{x}$
• then replace $x=\tilde{x}+Nz$

Weighted LS:

• Sometimes the square errors have different weights. The objective function can be written as $f_0(x)=||W(Ax-y)|{|}_2^2=||A_{w}x-y|{|}_2^2$ where
  • $W=\text{diag}(w_1,...,w_m),A_w\doteq WA,y_w=Wy$
• Then the problem turns to a ordinary ls problem

$l_2$ regularized LS:

• ${\min }_x||Ax-y|{|}_2^2+\lambda ||x|{|}_2^2,\lambda \ge 0$
• $||Ax-y|{|}_2^2+\lambda ||x|{|}_2^2=||\tilde{A}x-\tilde{y}|{|}_2^2$ where $\tilde{A}\doteq \left[\begin{array}{c}A\\ \sqrt{\lambda }{I}_n\end{array}\right]$ and $\tilde{y}\doteq \left[\begin{array}{c}y\\ 0_n\end{array}\right]$
• $\lambda \ge 0$ is a tradeoff parameter. Interpretation in terms of tradeoff between output tracking accuracy and input effort.
• The optimal regulation parameter, $x^{\ast }(\lambda ):=\arg {\min }_x||Ax-y|{|}_2^2+\lambda ||x|{|}_2^2$
• Train/test

Least Square Data Fitting

Constrained Least Square