Skip to main content
2 of 6
Minor edit

We have the following linear system in $\mathrm x \in \mathbb R^n$

$$\rm A x = b$$

where $\mathrm A \in \mathbb R^{m \times n}$ is fat (i.e., $n > m$) and $\mathrm b \in \mathbb R^m$.


###Least-norm

If the linear system is consistent, we look for the least-norm solution via the following (convex) quadratic program

$$\begin{array}{ll} \text{minimize} & \| \mathrm x \|_2^2\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\end{array}$$

Let the Lagrangian be

$$\mathcal L (\mathrm x, \lambda) := \frac 12 \mathrm x^{\top} \mathrm x + \lambda^{\top} (\mathrm A \mathrm x - \mathrm b)$$

Taking the partial derivatives of $\mathcal L$ and finding where they vanish, we obtain the linear system

$$\begin{bmatrix} \mathrm I_n & \mathrm A^\top\\ \mathrm A & \mathrm O_m\end{bmatrix} \begin{bmatrix} \mathrm x\\ \lambda \end{bmatrix} = \begin{bmatrix} 0_n\\ \mathrm b\end{bmatrix}$$

If $\mathrm A$ has full row rank, then $\rm A A^\top$ is invertible and we can conclude that the least-norm solution is

$$\mathrm x_{\text{LN}} := \color{blue}{\mathrm A^{\top} \left( \mathrm A \mathrm A^{\top} \right)^{-1} \mathrm b}$$