9-19-2024 - Least Squares

Goal: “solve” $\mathbf{A}\vec{\mathbf{x}}=\vec{\mathbf{b}}$ even when there is no solution

• $\mathbf{A}$ is not invertible, but not even $\vec{\mathbf{b}}\in \mathrm{col}(\mathbf{A})$ $\mathbf{A}$ is $m\times n$, meaning it takes something from ${\mathbb{R}}^n$ and sends it to ${\mathbb{R}}^m$

The “least squares solution” is defined as $\hat{x}\in {\mathbb{R}}^n$ such that

$$|\mathbf{A}\hat{\mathbf{x}}-\vec{\mathbf{b}}|\le |\mathbf{A}\hat{\mathbf{x}}-\vec{\mathbf{b}}|,\forall x\in {\mathbb{R}}^n$$

Last time: considered this as an optimiation problem, in other wrods

$$\begin{array}{r}f(x):=|\mathbf{A}\vec{\mathbf{x}}-\vec{\mathbf{b}}{|}^2=(\mathbf{A}\vec{\mathbf{x}}-\vec{b}{)}^T(\mathbf{A}\vec{\mathbf{x}}-\vec{\mathbf{b}})\\ ={\vec{\mathbf{x}}}^T{\mathbf{A}}^T\mathbf{A}\vec{\mathbf{x}}+{\vec{\mathbf{b}}}^T\vec{\mathbf{b}}-{\vec{\mathbf{b}}}^T\mathbf{A}\vec{\mathbf{x}}-{\vec{\mathbf{x}}}^T{\mathbf{A}}^T\vec{\mathbf{b}}\\ ={\vec{\mathbf{x}}}^T\mathbf{B}\vec{\mathbf{x}}+{\vec{\mathbf{b}}}^T\vec{\mathbf{b}}-2{\vec{\mathbf{b}}}^T{\mathbf{A}}^T\end{array}$$

Seek: critical point of $f$ that is a global minimum

Notation: $\mathbf{B}:={\mathbf{A}}^T\mathbf{A}$ Theorem: any critical of f is a global mimimum. Idea: a critical point will be a local minimum if

$${\vec{\nabla }}^{2}f=\mathrm{Hess}(f)={\mathbf{H}}_f=\left[\begin{array}{cccc}\frac{{\partial }^{2}f}{\partial x_1^2}& \frac{{\partial }^{2}f}{\partial x_1\partial x_2}& \cdots & \frac{{\partial }^{2}f}{\partial x_1\partial x_n}\\ \frac{{\partial }^{2}f}{\partial x_2\partial x_1}& \frac{{\partial }^{2}f}{\partial x_2^2}& \cdots & \frac{{\partial }^{2}f}{\partial x_2\partial x_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}f}{\partial x_n\partial x_1}& \frac{{\partial }^{2}f}{\partial x_n\partial x_2}& \cdots & \frac{{\partial }^{2}f}{\partial x_n^2}\end{array}\right].$$

at the critical point is a positive symmetric matrix.

In our case:

Claim 1

$${\vec{\nabla }}^{2}f=2\mathbf{B}$$

proof:

$${\vec{\mathbf{x}}}^T\mathbf{B}\vec{\mathbf{x}}=\sum _{i,j=1}^n{\mathbf{B}}_{ij}{\vec{\mathbf{x}}}_i{\vec{\mathbf{x}}}_j$$

In our case any local minimum is automatically a global minimum Why? There exists a critical point, and nothing funny on the boundary

Critical point equation:

$$\vec{\nabla }f=\vec{0}=\left[\begin{array}{c}\frac{\partial f}{\partial x_1}\\ \frac{\partial f}{\partial x_2}\\ ⋮\\ \frac{\partial f}{\partial x_n}\end{array}\right]$$

1 vector value equation or a system of n equations

$$\vec{\nabla }f=-2\vec{\nabla }({\vec{\mathbf{b}}}^T\mathbf{A}\vec{\mathbf{x}})+\vec{\nabla }({\vec{\mathbf{x}}}^T\vec{\mathbf{B}}\vec{\mathbf{x}})$$

Claim 2

$$\vec{\mathbf{\alpha }}\in {\mathbb{R}}^n$$ $$\vec{\nabla }({\vec{\mathbf{\alpha }}}^T\vec{\mathbf{x}})={\vec{\mathbf{\alpha }}}^T$$

Claim 3

$$\sum _{i,j=1}^n{\mathbf{B}}_{ij}{x}_i{x}_j=\frac{\partial }{\partial x_1}({\mathbf{B}}_{11}{x}_1{x}_1)\dots$$