30
$\begingroup$

Consider a linear system of equations $Ax = b$.

  • If the system is overdetermined, the least squares (approximate) solution minimizes $||b - Ax||^2$. Some source sources also mention $||b - Ax||$.

  • If the system is underdetermined one can calculate the minimum norm solution. But it does also minimize $||b - Ax||$, or am I wrong?

But if least squares is also a minimum norm, what is the difference, or the rationale of the different naming?

$\endgroup$
2
  • 5
    $\begingroup$ When $Ax=b$ is undetermined (so there are infinitely many solutions), the "least norm" solution is the solution $x$ such that $\|x\|$ is as small as possible. $\endgroup$
    – littleO
    Apr 26, 2017 at 17:44
  • $\begingroup$ For an underdetermined system, there are either (1) no exact solutions, or (2) infinitely many exact solutions. For (2), one of such solutions is the "minimum norm" solution, but since it is exact, all residuals are $0$ and hence it is also a least(-est) squares solution too. They are named differently because in (2) we are not concerned with minimising the squared sum of the residuals as they are all 0 because all solutions are exact, rather we want to pick a solution amongst all of these least-est squares solutions that has a minimum norm. $\endgroup$
    – Confounded
    May 31, 2023 at 2:55

3 Answers 3

34
$\begingroup$

Linear system $$ \mathbf{A} x = b $$ where $\mathbf{A}\in\mathbb{C}^{m\times n}_{\rho}$, and the data vector $b\in\mathbf{C}^{m}$, the solution vector in $x\in\mathbf{C}^{n}$.

Least squares problem

A least squares solution is guaranteed to exist and is defined by $$ x_{LS} = \left\{ x\in\mathbb{C}^{n} \colon \lVert \mathbf{A} x - b \rVert_{2}^{2} \text{ is minimized} \right\} $$

Least squares solution

The general least squares problem offers a $\color{blue}{particular}$ solution and a $\color{red}{homogeneous}$ solution. The confusingly named "solution of minimum norm" is just the $\color{blue}{particular}$ solution.

The minimizers are the affine set computed by $$ x_{LS} = \color{blue}{\mathbf{A}^{+} b} + \color{red}{ \left( \mathbf{I}_{n} - \mathbf{A}^{+} \mathbf{A} \right) y}, \quad y \in \mathbb{C}^{n} \tag{1} $$ where vectors are colored according to whether they reside in a $\color{blue}{range}$ space or $\color{red}{null}$ space. (See Laub, 2005, Theorem 8.1, p. 66)

The red dashed line below is the set of the least squares minimizers which appears when there is a row rank deficit $(\rho < m)$. In these cases, the solution is not unique.

hyperplane

Least squares solution of minimum norm

To find the minimizers of the minimum norm, the shortest solution vector, compute the length of the solution vectors.

$$ % \lVert x_{LS} \rVert_{2}^{2} = % \Big\lVert \color{blue}{\mathbf{A}^{+} b} + \color{red}{ \left( \mathbf{I}_{n} - \mathbf{A}^{+} \mathbf{A} \right) y} \Big\rVert_{2}^{2} % = % \Big\lVert \color{blue}{\mathbf{A}^{+} b} \Big\rVert_{2}^{2} + \Big\lVert \color{red}{ \left( \mathbf{I}_{n} - \mathbf{A}^{+} \mathbf{A} \right) y} \Big\rVert_{2}^{2} % $$ The $\color{blue}{range}$ space component is fixed, but we can control the $\color{red}{null}$ space vector. In fact, chose the vector $y$ which forces this term to $0$.

Therefore, the least squares solution of minimum norm is the particular solution $$ \color{blue}{x_{LS}} = \color{blue}{\mathbf{A}^{+} b}. $$ This is the point where the red dashed line punctures the blue plane. The least squares solution of minimum length is the point in $\color{blue}{\mathit{R}\!\left(\mathbf{A}^{*}\right)}$.

Full column rank

You ask about the case of full column rank where $n=\rho$. In this case, $$ \color{red}{\mathit{N}\left( \mathbf{A} \right)} = \left\{ \mathbf{0} \right\}, $$ the null space is trivial. There is no null space component, and the least squares solution is a point.

In other words, the complete least squares solution is just the $ \color{blue}{particular}$ solution $$ \color{blue}{x_{LS}} = \color{blue}{\mathbf{A}^{+} b} $$ When the matrix has full column rank, there is no $\color{red}{homogeneous}$ component to the solution. The solution is unique and is a point.

$\endgroup$
5
  • $\begingroup$ Great answer! What would be your go to reference textbook on this topic? I $\endgroup$ Jul 16, 2017 at 16:38
  • $\begingroup$ This post shows a bit more about equation (1) from Laub's delightful book. $\endgroup$
    – dantopa
    Jul 16, 2017 at 18:41
  • 2
    $\begingroup$ Wonderful, thank you. $\endgroup$ Jul 16, 2017 at 23:12
  • 1
    $\begingroup$ In "Provided that $b\notin\color{red}{\mathcal{N}\left( \mathbf{A}^{*}\right)}$, a least squares solution exists and is defined by" why are you specifying "Provided that $b\notin\color{red}{\mathcal{N}\left( \mathbf{A}^{*}\right)}$"? Seems to be unnecesary. $\endgroup$
    – kisten
    Apr 11, 2020 at 11:57
  • $\begingroup$ @user598716 You touch on a delicate point. If the data vector is in the null space then we have the trivial solution. You have a strong argument. Perhaps the qualification could be ignored. Perhaps it could be clarified as leading to the trivial solution. Your insight furthers the discussion. $\endgroup$
    – dantopa
    Apr 12, 2020 at 18:58
21
$\begingroup$

First, it's important to understand that there are different norms. Most likely you're interested in the euclidean norm:

$\| x \|_{2} =\sqrt{\sum_{i=1}^{n}x_{i}^{2}}$

Next, note that minimizing $\| b-Ax \|_{2}^{2}$ is equivalent to minimizing $\| b-Ax \|_{2}$, because squaring the norm is a monotone transform. It really doesn't matter which one you minimize.

If $A$ has full column rank, then there is a unique least squares solution.

However, if $A$ doesn't have full column rank, there may be infinitely many least squares solutions. In this case, we're often interested in the minimum norm least squares solution. That is, among the infinitely many least squares solutions, pick out the least squares solution with the smallest $\| x \|_{2}$. The minimum norm least squares solution is always unique. It can be found using the singular value decomposition and/or the Moore-Penrose pseudoinverse.

$\endgroup$
5
  • $\begingroup$ To determine the minimum norm solution, $A$ must be full row rank, right? $\endgroup$
    – plasmacel
    Apr 26, 2017 at 17:47
  • 1
    $\begingroup$ No- you can use the Moore-Penrose pseudoinverse to find a minimum norm least squares solution no matter what rank $A$ has. The formulas for the pseudoinverse based on the inverse of $AA^{T}$ or $A^{T}A$ only work if $A$ has full row or column rank respectively. $\endgroup$ Apr 26, 2017 at 17:48
  • 1
    $\begingroup$ Yeah, I just wanted to note that if $A$ has full row rank, then there are infinitely many (non least squares approximation) solutions, so the minimum norm solution is not an approximation. Thanks by the way, you cleared up some things for me. $\endgroup$
    – plasmacel
    Apr 26, 2017 at 17:52
  • $\begingroup$ Given $b = Ax$, is the least squares solution given by $x = (A^T A)^{-1}A^Tb$ and the least norm solution given by $x = A^T(AA^T)^{-1}b$? Thank you. $\endgroup$
    – Confounded
    Sep 1, 2022 at 17:28
  • $\begingroup$ @Confounded this isn't really a comment on my answer but rather a question on its own. Why not post it as a question? $\endgroup$ Sep 1, 2022 at 18:40
9
$\begingroup$

If a system is overdetermined, there is no solution and thus we may want to find $x$ such that $||Ax-b||$ is as small as it can be (as there is no way to make $||Ax-b||=0$).

On the other hand, if the system is underdetermined, there are infinitely many solutions and thus one can find a solution of minimal norm and this is called the minimum norm solution.

$\endgroup$
4
  • 2
    $\begingroup$ Keep in mind that an underdetermined system can also be inconsistent. In that case there aren't any exact solutions to $Ax=b$, but there are still solutions that minimize $\| Ax -b \|_{2}$ and among those there is a unique minimum norm least squares solution. $\endgroup$ Feb 20, 2019 at 5:14
  • 1
    $\begingroup$ @BrianBorchers you are absolutely correct! Thanks for pointing this out! $\endgroup$
    – Zuriel
    Feb 20, 2019 at 12:23
  • $\begingroup$ @BrianBorchers So, given an underdetermined system $Ax = b$ (which might be incontinent), how do we find a solution? I have seen derivations where one seeks a solution with a minimum norm by using a constrained optimization with the Lagrangian given by $L = x^Tx + \lambda (Ax - b)$, but will this work if the system is inconsistent? Can we still use the Lagranian approach in this case? What would it be? Thank you. $\endgroup$
    – Confounded
    May 26, 2023 at 3:30
  • 1
    $\begingroup$ In order to use the Lagrangian approach, you need to have a constraint. One way to do this is to find a particular least squares solution that isn't minimum norm. Then minimize the norm of $x$ subject to the constraint that the norm of $Ax-b$ equals the best known least squares value. $\endgroup$ May 26, 2023 at 4:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .