least-squares problem $\|A\hat{x}-b\|_2 = \min_{x}\|Ax-b\|_2$

Given the least-squares problem $$\|A\hat{x}-b\|_2 = \min_{x}\|Ax-b\|_2$$ with $A\in\mathbb{R}^{m\times n}$, $m \geq n$ and $\text{rank}(A) = n$.

Show that the solution $\hat{x}$ is given by the solution of the linear system of equations $$\begin{bmatrix} I & A\\ A^T & 0 \end{bmatrix}\begin{bmatrix} y\\ \hat{x} \end{bmatrix}=\begin{bmatrix}b \\ 0\end{bmatrix}.$$ What is the interpretation of $y$?

2.) Let $A=QR$ be the reduced QR factorization of the matrix $A$ in the above least-squares problem. Show that the solution of the least-squares problem can be written as $x=R^{-1}Q^Tb$. Then show that $$\|\hat{x}\|_2\leq\sigma_n^{-1}\|b\|_2,$$ where $\sigma_n$ is the smallest singular value of $A$.

1 Answer

To show that the set of linear equations gives the optimal solution, we could add a apply an substitution of variable $y=b-Ax$, and then the problem would become: $$\underset{x,y}{\text{minimize }} y^Ty\\\text{subject to } y + Ax=b$$ then the first line of your matrix actually complies to the primal feasibility of the above problem, at the optimal punt we must satisfy the constraints .i.e. $$\begin{bmatrix} I &A \end{bmatrix}\begin{bmatrix} y \\x^\star \end{bmatrix}=b$$ furthermore for ease of reference lets capture the two optimization variables into a single one leading to: $$\underset{z}{\text{minimize }} z^T\begin{bmatrix} I &0 \\0 & 0\end{bmatrix}z\\\text{subject to } \begin{bmatrix} I &A \end{bmatrix} z = b$$

Now using the KKT conditions, or Lagrange multipliers in this case (Equality constrained optimization), the stationarity condition states that we must have $$\nabla f(z) = \nu \nabla h(z)$$ $f$ being the objective function, and $h$ being affine constraints. We can interpret this, that at the optimal point the gradient of our objective function, matches the gradient of the constraints, meaning there is no feasible direction we could move in, to get a better solution. Anyway solving this for our system leads to, $$\begin{bmatrix} I &0 \\0 & 0\end{bmatrix}z - \begin{bmatrix} I \\ A^T \end{bmatrix}\nu=0$$ By plugging back in $z$ and solving for $\nu$ we see that $\nu$ must equal $y$, then the second row gives us $A^Ty=0$, the second line of your matrix!

There is probably some interpretation possible, dont hold me accountible for it but here it goes: $y$ in the equation $Ax+y=b$ can be seen as the extra amount needed to actually achieve equality in the optimization problem, in our reformulation we actually minimize this 'extra' amount needed. The second equation states that $y$ must be orthogonal to column vectors of $A$. Maybe way simpler derivations of this problem exist btw.