📂Hilbert Space

Proof of the Shortest Vector Theorem

Theorem¹

Let $\left( H, \left\langle \cdot,\cdot \right\rangle \right)$ be a Hilbert space. Let $M \lneq H$ be a non-empty closed convex subset. Then, for $\mathbf{x} \in ( H \setminus M)$,

$$ \delta := \| \mathbf{x} - \mathbf{m}_{0} \| = \inf_{\mathbf{m} \in M} \| \mathbf{x} - \mathbf{m} \| > 0 $$

there exists a unique $\mathbf{m}_{0} \in M$ that satisfies this.

Explanation

The fact that subspace $M$ is convex means for all $\mathbf{x},y \in M$ and $\lambda \in [0,1]$ the following holds true.

$$ \lambda \mathbf{x} + (1-\lambda) y \in M $$

It might seem trivial, but upon closer inspection, it’s not necessarily obvious since there’s no reason in a general topological space for $\mathbf{m}_{0}$ to be unique.

Simplifying the concept as shown above, the right subspace $M$ is quite straightforward, which is why this theorem holds.

On the other hand, as can be seen from the proof, this does not hold for inner spaces that are not Hilbert spaces.

Proof

• Part 1. $\delta >0$

  Assuming $\delta = 0$,

  $$ \lim_{k \to \infty } \| \mathbf{x} - \mathbf{m}_{k} \| = \delta = 0 $$

  there exists a sequence $\left\{ \mathbf{m}_{k} \right\}_{k \in \mathbb{N}}$ that satisfies this condition. This means when $k \to \infty$, $\mathbf{m}_{k} \to \mathbf{x} \in \overline{M} = M$, which contradicts $\mathbf{x} \in ( H \setminus M)$.

• Part 2. Existence

  Due to the parallelogram law,

  $$ \begin{align*} \| \mathbf{m}_{k} - \mathbf{m}_{j} \|^2 &= \| ( \mathbf{x} - \mathbf{m}_{k} ) - ( \mathbf{x} - \mathbf{m}_{j} ) \|^2 \\ =& 2 \| \mathbf{x} - \mathbf{m}_{k} \|^2 + 2 \| \mathbf{x} - \mathbf{m}_{j} \|^2 - \| ( \mathbf{x} - \mathbf{m}_{k} ) + ( \mathbf{x} - \mathbf{m}_{j} ) \|^2 \\ =& 2 \| \mathbf{x} - \mathbf{m}_{k} \|^2 + 2 \| \mathbf{x} - \mathbf{m}_{j} \|^2 - 4 \left\| \mathbf{x} - {{ \mathbf{m}_{k} + \mathbf{m}_{j} } \over {2}} \right\|^2 \\ \le & 2 \| \mathbf{x} - \mathbf{m}_{k} \|^2 + 2 \| \mathbf{x} - \mathbf{m}_{j} \|^2 - 4 \delta^2 \end{align*} $$

  Hence, when $k,j \to \infty$,

  $$ \| \mathbf{m}_{k} - \mathbf{m}_{j} \|^2 \to 4 \delta^2 - 4 \delta^2 $$

  $\left\{ \mathbf{m}_{k} \right\}_{k \in \mathbb{N}}$ is a Cauchy sequence. Therefore, since $H$ is a Hilbert space, there exists $\mathbf{m}_{0} \in H$ such that $\mathbf{m}_{k} \to \mathbf{m}_{0}$.

  $$ \mathbf{m}_{k} \to \mathbf{m}_{0} \in \overline{M} = M $$

  Since the norm is a continuous function,

  $$ \| \mathbf{x} - \mathbf{m}_{0} \| = \left\| \mathbf{x} - \lim_{k \to \infty} \mathbf{m}_{k} \right\| = \lim_{k \to \infty} \left\| \mathbf{x} - \mathbf{m}_{k} \right\| = \delta $$

• Part 3. Uniqueness

  Assuming that there exists $\mathbf{m}_{0} ' \in M$ such that $\| \mathbf{x} - \mathbf{m}_{0} ' \| = \delta$,

  $$ \| \mathbf{m}_{0} - \mathbf{m}_{0} ' \| \le 2 \| \mathbf{m}_{0} - \mathbf{m}_{k} \|^2 + 2 \| \mathbf{m}_{0}’ - \mathbf{m}_{j} \|^2 - 4 \delta^2 = 4 \delta^2 - 4 \delta^2 = 0 $$

  Hence $\mathbf{m}_{0} = \mathbf{m}_{0} ' $ must hold.

■