logo

最短ベクトル定理の証明 📂ヒルベルト空間

最短ベクトル定理の証明

定理1

(H,,)\left( H, \left\langle \cdot,\cdot \right\rangle \right)ヒルベルト空間としよう。MHM \lneq H空集合ではなく閉じた部分集合としよう。するとx(HM)\mathbf{x} \in ( H \setminus M)に対して

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

を満たすm0M\mathbf{m}_{0} \in Mが唯一存在する。

説明

部分空間MMであるというのは、全てのx,yM\mathbf{x},y \in Mλ[0,1]\lambda \in [0,1]に対して以下が成立するということだ。

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

些細なことに見えるけど、よく考えれば、ただの一般的な位相空間ではm0\mathbf{m}_{0}が唯一である理由がない。

20181119\_041823.png

簡単に図式化して考えると、上の図の右の部分空間MMがかなり単純で、この定理が成立する理由だ。

一方、証明からわかるように、ヒルベルト空間でない内積空間では成立しない。

証明

  • パート1. δ>0\delta >0

    δ=0\delta = 0と仮定すると、

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

    この条件を満たす数列{mk}kN\left\{ \mathbf{m}_{k} \right\}_{k \in \mathbb{N}}が存在する。つまりkk \to \inftyの時mkxM=M\mathbf{m}_{k} \to \mathbf{x} \in \overline{M} = Mで、これはx(HM)\mathbf{x} \in ( H \setminus M)に矛盾する。

  • パート2. 存在

    平行四辺形等式により、

    mkmj2=(xmk)(xmj)2=2xmk2+2xmj2(xmk)+(xmj)2=2xmk2+2xmj24xmk+mj222xmk2+2xmj24δ2 \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*}

    したがってk,jk,j \to \inftyの時、

    mkmj24δ24δ2 \| \mathbf{m}_{k} - \mathbf{m}_{j} \|^2 \to 4 \delta^2 - 4 \delta^2

    {mk}kN\left\{ \mathbf{m}_{k} \right\}_{k \in \mathbb{N}}はコーシー列だ。したがってHHはヒルベルト空間であるため、mkm0\mathbf{m}_{k} \to \mathbf{m}_{0}となるm0H\mathbf{m}_{0} \in Hが存在する。

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

    ノルムは連続関数であるため、

    xm0=xlimkmk=limkxmk=δ \| \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

  • パート3. 唯一性

    xm0=δ\| \mathbf{x} - \mathbf{m}_{0} ' \| = \deltaとなるm0M\mathbf{m}_{0} ' \in Mが存在すると仮定してみると、

    m0m02m0mk2+2m0mj24δ2=4δ24δ2=0 \| \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

    したがってm0=m0\mathbf{m}_{0} = \mathbf{m}_{0} ' でなければならない。


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