logo

Proof of the Shortest Vector Theorem 📂Hilbert Space

Proof of the Shortest Vector Theorem

Theorem1

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.

20181119\_041823.png

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.


  1. Ole Christensen, Functions, Spaces, and Expansions: Mathematical Tools in Physics and Engineering (2010), p67-68 ↩︎