Showing $x=A^\dagger b$ is the unique minimum norm solution of $\Vert A_{m\times n}x_n - b_m \Vert$

Question

Consider the least squares problem.

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

---

Problem

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$.

---

Try

It is not difficult to show

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

because

$$ \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.

Answer 1

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. $$