Consider the least squares problem.

" Find minimizer $x \in \mathbb{C}^n$ : $\Vert A_{m\times n}x_n - b_m \Vert$"


Assume $\Vert Ax - b \Vert_2 = \Vert A A^\dagger b - b\Vert_2 $

Show : $\Vert x \Vert_2 > \Vert A^\dagger b \Vert$, if $\exists x \neq A^\dagger b$

where $A^\dagger$ denotes Moore-Penrose inverse of $A$.


It is not difficult to show

$$ \Vert Ax - b \Vert_2 \ge \Vert A A^\dagger b -b \Vert_2 $$


$$ \begin{aligned} \Vert Ax - b \Vert_2^2 = \Vert A A^\dagger b -b \Vert_2^2 + \Vert Ax - A A^\dagger b\Vert_2^2 + c + \bar{c} \end{aligned} $$

where $c = (Ax - A A^\dagger b)^\ast(Ax - A A^\dagger b) = x^\ast A^\ast A A^\dagger b - x^\ast A^\ast b - b^\ast (A A^\dagger)^2 b + b^\ast (A A^\dagger) b = 0$

thus we get

$$ \Vert Ax - b\Vert_2^2 \ge \Vert A A^\dagger b -b \Vert_2^2 $$

Now, I would like to show that

$$ \Vert x \Vert_2^2 = \Vert A A^\dagger \Vert_2^2 + \Vert x - A^\dagger b \Vert_2^2 $$

So I wrote:

$$ \begin{aligned} \Vert x \Vert_2^2 &= \Vert A^\dagger b + x - A^\dagger \Vert_2^2 \\ &= \Vert A^\dagger b \Vert_2^2 + \Vert x - A^\dagger b \Vert_2^2 + c + \bar{c} \end{aligned} $$

where $c = b^\ast (A^\dagger)^\ast (x - A^\dagger b)$.

But I'm stuck at showing $c = 0$

Any help will be appreciated.


I am sure I have answered this kind of question some years ago, but I cannot find the answer now.

It is the easiest to prove that $c=0$ (step 4 below) if you use the explicit form of the solution $x$ (all solutions to the LS problem).

The steps:

  1. All LS solutions are the solutions to the normal equation $A^*Ax=A^*b$.
  2. All solutions are given by the formula $$ x=(A^*A)^+A^*b+(I-(A^*A)^+A^*A)w. $$
  3. Use the property $A^+=(A^*A)^+A^*$ to rewrite $$ x=A^+b+(I-A^+A)w. $$
  4. Prove that $A^+b\ \bot\ (I-A^+A)w$ e.g. by $$ (I-A^+A)^*A^+=[(A^+A)^*=A^+A]=(I-A^+A)A^+=A^+-A^+AA^+=0. $$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.