1.2a Least Squares

Least Squares Optimization

Least squares optimization is a method for finding an approximate solution to a system of equations $A\vec{x}=\vec{y}$ for which $\nexists \vec{y}\in \mathcal{R}(A)$. Formally, given a real matrix $A\in {\mathbb{R}}^{m\times n}$ and a vector $\vec{y}\in {\mathbb{R}}^m$, the least squares problem finds (at least one) vector ${\vec{x}}^{\ast }\in {\mathbb{R}}^n$ such that $A{\vec{x}}^{\ast }$ is the orthogonal projection of $\vec{y}$ onto $\mathcal{R}(A)$,
${\vec{x}}^{\ast }\in \arg \underset{\vec{x}\in {\mathbb{R}}^n}{\min }\Vert A\vec{x}-\vec{y}{\Vert }_2^2,$
where ${\vec{x}}^{\ast }$ is always an optimal solution to the system of normal equations $A^{T}A\vec{x}=A^T\vec{y}$.

Particularly, if $A$ is in full column rank (i.e., $\mathrm{Rank}(A)=n$), and therefore $Ax=y$ is overdetermined, then the least squares solution is given as
${\vec{x}}^{\ast }=(A^{T}A{)}^{-1}{A}^T\vec{y}.$

Moreover, if $A$ is in full row rank (i.e., $\mathrm{Rank}(A)=m\le n$), and therefore $A\vec{x}=\vec{y}$ is undetermined with infinite solutions, then the least squares solution is defined as the solution of the system with the smallest Euclidean norm, such that
${\vec{x}}^{\ast }=\arg \underset{\vec{x}:A\vec{x}=\vec{y}}{\min }\Vert \vec{x}{\Vert }_2=A^T(A{A}^T{)}^{-1}\vec{y}.$

Least Squares and the Pseudoinverse ${\mathcal{X}}_{\text{opt}}=A^{†}\vec{y}+\mathcal{N}(A),$ where $A^{†}\vec{y}$ is the minimum-norm point in the optimal set. This means that if $\mathrm{Rank}(A)=\min (m,n)$ (i.e., $A$ is full rank), then the optimal solution $x^{\ast }=A^{†}\vec{y}$.

Note that the set of optimal solutions to the least squares problem can be expressed as

Proofs

1. General Solution

Per the Projection Theorem, we know that given any $y\in {\mathbb{R}}^m$, there exists some $\bar{y}\in \mathcal{R}(A)$ at minimal distance from $\vec{y}$. We also know that $(y-\bar{y})\perp \mathcal{R}(A)\equiv (y-\bar{y})\in \mathcal{N}(A^T)$. As such, for all $y$,
$A^T(y-\bar{y})=0.$
Furthermore, since $\bar{y}\in \mathcal{R}(A)$, there certainly exists some $x$, such that $Ax=\bar{y}$. Combining the two equations,
$A^{T}y-A^{T}Ax=0⟺A^{T}Ax=A^{T}y.$

2. Full Col. Rank Solution

Since $A^{T}A$ is invertible for wide matrices of full column rank, we have $x^{\ast }=(A^{T}A{)}^{-1}{A}^{T}y$.

3. Full Row Rank Solution

When a tall matrix $A$ has full row rank $m\le n$, the rank-nullity theorem implies that the nullspace of $A$ is nontrivial, such that $\text{Nullity}(A)=n-m\ge 1$.

4. Pseudoinverse Solution

Variants

(Weighted LS) For $W=\mathrm{diag}(w_1,\dots ,w_m)$, $\exists {\vec{x}}_w^{\ast }=\arg \underset{\vec{x}\in {\mathbb{R}}^n}{\min }\Vert W(A\vec{x}-\vec{y}){\Vert }_2^2$, such that $A^T{W}^{T}WA{\vec{x}}_w^{\ast }=A^T{W}^{T}W\vec{y}$.

The proof is simple. We know from the proof of general LS that $x^{\ast }$ is the optimal solution to $A^{T}Ax=A^{T}y$. We then take $A_w=WA$, $y_w=Wy$, and substitute for the solution, such that
$A_w^T{A}_w\vec{x}=A_w^T{y}_w⟺A^T{W}^{T}WAx=A^T{W}^{T}Wy.$

(Linearly Constrained LS) For \begin{aligned} \min_\limits{x} \quad & c^T x \\ \text{s.t.:} \quad & Ax \leq b\end{aligned}

(${\ell }^2$-Regularized LS) For $\lambda >0$, $x^{\ast }=\arg \underset{\vec{x}\in {\mathbb{R}}^n}{\min }\Vert A\vec{x}-\vec{y}{\Vert }_2^2+\lambda \Vert \vec{x}{\Vert }_2^2$ is the optimal solution to $(A^{T}A+\lambda L^{T}L)\vec{x}=A^T\vec{y}$.