Uniqueness proof for minimal least squares solution

Question

Let $A$ be an $m\times n$ matrix, let $v \in \mathbb{R}^m$, and let $S$ be the set of least squares solutions to the system $Ax=b$. Show that there exists a unique minimal least square solution to $Ax=b$; that is, there exists some $x\in S$ such that $||x|| \le||y||$ for all $y\in S$.

I have two questions about this.

1. How can there be a unique least square solution if the stipulation is $||x|| \le ||y||$, shouldn't it just be less than?

2. This seems tautological to me, because you're just trying to show that there is a least element in S, which should clearly exist because the norm gives you a scalar that you can compare. Is there any more to this proof?

Answer 1

Since $x \mapsto \|Ax-b\|^2$ is convex, the set of minimisers $S$ is a closed, convex set.

(In particular, if $x_0$ is a solution, then $S = \{x_0\} + \ker A$.)

A standard Hilbert space theorem states that a closed convex set has a unique point of minimum norm.

The $x$ is the question is the point of minimum norm in $S$.

Answer 2

We can't have $$\exists x \in S, \|x\| < \|y \|, \forall y \in S$$

because this would imply that $\|x\| < \|x\|$ such $x \in S$.

However, we can write

$$\exists x \in S, \|x\|<\|y\|, \forall y \in S \setminus \{x\}.$$

A minimal point need not exists in general, for example if $S=(0,1)$, try to minimize $\|x\|$, in that case, we have infimum but not minimum. We have to use some property of the least square solution to show that a minimal element exists.