§E20.25逆問題と正則化

証明.(1)を示す。$1\le i\le m$について$u_i^{\mathsf T}A=\sum_{j=1}^p\sigma_j(u_i^{\mathsf T}u_j)v_j^{\mathsf T}$は、$i\le p$ならば$\sigma_iv_i^{\mathsf T}$、$i>p$ならば$0$である。同様に$Av_i$は、$i\le p$ならば$\sigma_iu_i$、$i>p$ならば$0$である。$\sigma_i$は大きい順に並んでいるから、$\sigma_i>0$であることと$i\le r$であることは同値であり、$A=\sum_{i=1}^r\sigma_iu_iv_i^{\mathsf T}$である。したがって$\im A\subseteq\operatorname{span}\{u_1,\dots,u_r\}$であり、$1\le i\le r$について$u_i=A(\sigma_i^{-1}v_i)\in\im A$であるから、$\im A=\operatorname{span}\{u_1,\dots,u_r\}$であって$\operatorname{rank}A=r$である。§D3.18 命題 2.1により$\sigma_i=\sigma_i(A)$であるから、§E20.9 命題 6.1 (1)と§E20.9 定義 6.2により$A^\dagger=\sum_{i=1}^r\sigma_i^{-1}v_iu_i^{\mathsf T}$である。$x^\dagger=\sum_{i=1}^r\sigma_i^{-1}(u_i^{\mathsf T}b)v_i$と$v_1,\dots,v_n$の正規直交性から、$v_i^{\mathsf T}x^\dagger$は$i\le r$ならば$\sigma_i^{-1}u_i^{\mathsf T}b$、$i>r$ならば$0$である。

$b\in\im A$とする。$\lVert Ax-b\rVert_2$の最小値は$0$であるから、$Ax=b$の最小二乗解の全体は$Ax=b$を満たす$x$の全体であり、§E20.9 命題 6.1 (1)により$x^\dagger$はそのうちノルムが最小のただ一つのものである。$Ax=b$ならば、$1\le i\le r$について$\sigma_iv_i^{\mathsf T}x=u_i^{\mathsf T}Ax=u_i^{\mathsf T}b$であり、$\sigma_i>0$から$v_i^{\mathsf T}x=\sigma_i^{-1}u_i^{\mathsf T}b=v_i^{\mathsf T}x^\dagger$である。

(2)を示す。$Ge=\sum_{i=1}^rg_i(u_i^{\mathsf T}e)v_i$であり、$v_1,\dots,v_r$と$u_1,\dots,u_m$の正規直交性から

である。$e=\delta u_k$ならば$Ge=\delta g_kv_k$であり、$\lVert Ge\rVert_2=\delta\lvert g_k\rvert$である。

(3)を示す。(1)により$1\le i\le r$について$u_i^{\mathsf T}b=\sigma_iv_i^{\mathsf T}x^\dagger$であり、$x^\dagger=\sum_{i=1}^r(v_i^{\mathsf T}x^\dagger)v_i$である。したがって

であり、$G(b+e)=Gb+Ge$から等式を得る。右辺の第1項のノルムは$v_1,\dots,v_r$の正規直交性により$\bigl(\sum_{i=1}^r(1-\sigma_ig_i)^2(v_i^{\mathsf T}x^\dagger)^2\bigr)^{1/2}$であり、(2)を$\delta=\lVert e\rVert_2$として用いると第2項のノルムは$\max_i\lvert g_i\rvert\,\lVert e\rVert_2$以下である。三角不等式により不等式を得る。

(4)を示す。(3)により$G(b+e)-x^\dagger\in\operatorname{span}\{v_1,\dots,v_r\}$である。(1)により$1\le i\le r$について$v_i^{\mathsf T}(x-x^\dagger)=0$であるから、$x-x^\dagger\in\operatorname{span}\{v_{r+1},\dots,v_n\}$である。二つの部分空間は直交するから、$G(b+e)-x=(G(b+e)-x^\dagger)-(x-x^\dagger)$に Pythagoras の定理を適用して等式を得る。▨

証明.$B:=\begin{pmatrix}A\\\lambda L\end{pmatrix}\in\R^{(m+q)\times n}$、$c':=\begin{pmatrix}c\\0\end{pmatrix}\in\R^{m+q}$と置く。任意の$x\in\R^n$について$\lVert Bx-c'\rVert_2^2=\lVert Ax-c\rVert_2^2+\lVert\lambda Lx\rVert_2^2=J(x)$であるから、$J$の最小値を与える$x\in\R^n$の全体は$Bx=c'$の最小二乗解の全体に等しく、§E20.6 命題 1.2 (1)によりこの全体は空でない。$\lambda>0$から$\ker B=\ker A\cap\ker L$であり、$B^{\mathsf T}B=A^{\mathsf T}A+\lambda^2L^{\mathsf T}L$、$B^{\mathsf T}c'=A^{\mathsf T}c$である。

(1)を示す。$\ker A\cap\ker L=\{0\}$とする。$\ker B=\{0\}$であるから$B$の列は一次独立であり、§E20.6 命題 1.2 (2)により$B^{\mathsf T}B=A^{\mathsf T}A+\lambda^2L^{\mathsf T}L$は正則であって、$Bx=c'$の最小二乗解はただ一つである。§E20.6 命題 1.2 条件 (c)により、$x\in\R^n$が$Bx=c'$の最小二乗解であることは$B^{\mathsf T}Bx=B^{\mathsf T}c'$、すなわち$(A^{\mathsf T}A+\lambda^2L^{\mathsf T}L)x=A^{\mathsf T}c$と同値である。したがって$J$の最小値を与える$x$はただ一つ存在し、この方程式のただ一つの解に等しく、$Bx=c'$のただ一つの最小二乗解である。

(2)を示す。$B$の列が一次独立であることは$\ker B=\{0\}$、すなわち$\ker A\cap\ker L=\{0\}$と同値である。§E20.6 命題 1.2 (2)により、$Bx=c'$の最小二乗解、すなわち$J$の最小値を与える$x$がただ一つであることは、$\ker A\cap\ker L=\{0\}$と同値である。▨

証明.(1)を示す。$A^{\mathsf T}=\sum_{j=1}^r\sigma_jv_ju_j^{\mathsf T}$であるから、$1\le i\le r$について$A^{\mathsf T}Av_i=\sigma_iA^{\mathsf T}u_i=\sigma_i^2v_i$であり、$A^{\mathsf T}c=\sum_{i=1}^r\sigma_i\beta_iv_i$である。$y:=\sum_{i=1}^r\sigma_i(\sigma_i^2+\lambda^2)^{-1}\beta_iv_i$と置くと

であり、定義 2.3により$R_\lambda c=y$である。$c\in\R^m$は任意であるから行列の等式を得る。

(2)を示す。$\sigma^2+\lambda^2-2\lambda\sigma=(\sigma-\lambda)^2\ge0$であり、等号は$\sigma=\lambda$のときに限る。両辺を$2\lambda(\sigma^2+\lambda^2)>0$で割って第一の主張を得る。$\sigma>0$ならば$\sigma^2<\sigma^2+\lambda^2$であるから$\sigma/(\sigma^2+\lambda^2)<\sigma/\sigma^2=1/\sigma$である。

(3)を示す。(1)により$R_\lambda$は補題 1.1の$G$で$g_i=\sigma_i/(\sigma_i^2+\lambda^2)$としたものであり、$\sigma_ig_i-1=-\lambda^2/(\sigma_i^2+\lambda^2)$である。補題 1.1 (3)を$b=c$、$e=0$に適用し、補題 1.1 (1)の$A^\dagger c=\sum_{i=1}^r(v_i^{\mathsf T}A^\dagger c)v_i$を用いると

である。$1\le i\le r$について$0<\sigma_i^2/(\sigma_i^2+\lambda^2)<1$であり、$\sigma_i\ge\sigma_r$から$\lambda^2/(\sigma_i^2+\lambda^2)\le\lambda^2/(\sigma_r^2+\lambda^2)$であるので、$v_1,\dots,v_r$の正規直交性により二つの不等式を得る。$\lambda\to0$のとき右辺は$0$に収束する。

(4)を示す。(1)と$Av_i=\sigma_iu_i$により$AR_\lambda c=\sum_{i=1}^r\sigma_i^2(\sigma_i^2+\lambda^2)^{-1}\beta_iu_i$であり、$c=\sum_{i=1}^m\beta_iu_i$であるから

である。$u_1,\dots,u_m$の正規直交性により等式を得る。$\lambda^2/(\sigma_i^2+\lambda^2)=1-\sigma_i^2/(\sigma_i^2+\lambda^2)$は$\lambda>0$について非負で単調非減少であるから、右辺は$\lambda$について単調非減少である。▨

証明.(1)を示す。$\sigma_i$は大きい順に並んでいるから、$\sigma_i>\tau$であることと$i\le k$であることは同値であり、$\tau>0$から$k\le r$である。定義 2.1により$T_\tau$は補題 1.1の$G$で$g_i=\sigma_i^{-1}$（$i\le k$）、$g_i=0$（$k<i\le r$）としたものであり、$\sigma_ig_i-1$は$i\le k$ならば$0$、$k<i\le r$ならば$-1$である。補題 1.1 (3)により等式を得る。$k\ge1$ならば$\max_i\lvert g_i\rvert=\sigma_k^{-1}$であり、$\sigma_k>\tau$であるから、補題 1.1 (2)により$T_\tau e$についての主張を得る。$k=0$ならば$T_\tau=0$である。$\tau<\sigma_r$ならば$\sigma_r>\tau$から$k\ge r$であり、$k=r$であるので第1項の和は空である。

(2)を示す。$b\in\R^m$に命題 2.4 (3)を適用して第一の不等式を得る。命題 2.4 (1)により$R_\lambda$は補題 1.1の$G$で$g_i=\sigma_i/(\sigma_i^2+\lambda^2)$としたものである。命題 2.4 (2)により各$i\le r$について$g_i\le1/(2\lambda)$、$g_i<1/\sigma_i\le1/\sigma_r$であるから、補題 1.1 (2)により第二の不等式を得る。$R_\lambda(b+e)-x^\dagger=(R_\lambda b-x^\dagger)+R_\lambda e$と三角不等式により和の評価を得る。$\lambda=\sigma_j$ならば、命題 2.4 (2)により$g_j=1/(2\lambda)$は$g_1,\dots,g_r$の最大値であり、補題 1.1 (2)により$e=\delta u_j$で等号が成り立つ。

(3)を示す。(2)により

であり、右辺は$0$に収束する。$\tau_\ell\to0$であるから、ある$\ell_0$が存在して$\ell\ge\ell_0$ならば$\tau_\ell<\sigma_r$であり、(1)により$\ell\ge\ell_0$について$\lVert T_{\tau_\ell}(b+e_\ell)-x^\dagger\rVert_2=\lVert T_{\tau_\ell}e_\ell\rVert_2\le\delta_\ell/\sigma_r$である。したがって$T_{\tau_\ell}(b+e_\ell)\to x^\dagger$である。$R_{\lambda_\ell}$と$T_{\tau_\ell}$はいずれも補題 1.1の$G$の形であるから、補題 1.1 (4)により最後の二つの不等式を得る。▨

証明.(1)の証明は演習とする（問題 5.1）。

(2)を示す。$x\in\R^N$が$Cx=0$、$Lx=0$を満たすならば、§E20.16 定理 2.3により$0\le k<N$について$\hat h_k\hat x_k=0$、$\hat g_k\hat x_k=0$であり、$(\hat h_k,\hat g_k)\ne(0,0)$から$\hat x_k=0$である。§E20.16 定理 1.3 (2)により$x=0$であるから、$\ker C\cap\ker L=\{0\}$である。命題 2.2 (1)により$x_*$は$(C^{\mathsf T}C+\lambda^2L^{\mathsf T}L)x_*=C^{\mathsf T}c$を満たす。(1)を$h$と$g$に適用し、§E20.16 定理 2.3を用いると、この等式の両辺の離散 Fourier 変換の第$k$成分は

を与える。$(\hat h_k,\hat g_k)\ne(0,0)$から左辺の係数$\lvert\hat h_k\rvert^2+\lambda^2\lvert\hat g_k\rvert^2$は正であり、主張の式を得る。

(3)を示す。§E20.16 定理 2.3と離散 Fourier 変換の線形性により$\hat c_k=\hat h_k\hat x_k+\hat e_k$である。$D_k:=\lvert\hat h_k\rvert^2+\lambda^2\lvert\hat g_k\rvert^2$と置くと、(2)により