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

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.

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