Tikhonov正則化(Tikhonov regularization)とは、有界線形作用素 $A$ の方程式 $Ax=b$ を解く代わりに、$\|Ax-b\|^2+\alpha\|x\|^2$ を最小にする $x_\alpha=(A^*A+\alpha I)^{-1}A^*b$ を解とする方法である。$\alpha>0$ なら解は常にただ 1 つで $b$ に連続に依存し、特異値 $\sigma$ の項はフィルタ $\sigma^2/(\sigma^2+\alpha)$ で抑えられる。雑音の大きさ $\delta$ に対し $\alpha\to0$、$\delta^2/\alpha\to0$ なら最小ノルム解に収束し、不一致原理で $\alpha$ を決めることもできる。統計ではリッジ回帰と呼ぶ。
連立方程式 $Ax=b$ の $A$ の特異値が小さいと、$b$ のわずかな誤差で解が大きく動く。たとえば $A=\begin{pmatrix}1&1\\1&1.001\end{pmatrix}$ では、$b=(2,\ 2.001)$ の解は $(1,1)$ なのに、$b$ を $0.001$ だけ変えた $(2,\ 2.002)$ の解は $(0,2)$ である。測定値には誤差があるので、この方程式を素直に解いても意味のある答えは得られない。Tikhonov正則化 は、残差だけでなく解の大きさにも罰則を付けて
$$
\|Ax-b\|^2+\alpha\|x\|^2
$$
を最小にする方法である。解は $x_\alpha=(A^*A+\alpha I)^{-1}A^*b$ と書け、小さい特異値の影響だけが抑えられる。
この記事では、解の存在と安定性、$\alpha\to0$ での収束、雑音があるときの誤差の上界、不一致原理の正しさを証明する。統計ではこの方法を リッジ回帰 と呼ぶので、平均二乗誤差についても述べる。
$X,Y$ を Hilbert空間、$A\colon X\to Y$ を有界線形作用素とする(行列を含む)。$A^*$ は 随伴作用素 である。方程式 $Ax=b$ が 適切(Hadamard の意味)であるとは、解が存在し、一意で、$b$ に連続に依存することをいう。$A$ がコンパクト作用素で値域が無限次元なら、$A$ の逆は(存在しても)有界でない。積分方程式 の第 1 種の方程式がこの形である。
$Q$ を $\overline{R(A)}$ への直交射影とし、$b\in R(A)+R(A)^\perp$ とする。このとき $Qb\in R(A)$ で、$\|Ax-b\|$ を最小にする $x$ は $Ax=Qb$ の解全体である。その中でノルム最小のものを 最小ノルム解 といい、$x^\dagger$ と書く。$x^\dagger\in N(A)^\perp$、$A^*Ax^\dagger=A^*b$ である。行列なら $x^\dagger=A^+b$ で、Moore–Penrose逆行列 の定理「最小二乗解とその最小ノルム性」がこれを述べる。
$\alpha>0$ を 正則化パラメータ とする。Tikhonov 汎関数 $T_\alpha(x)=\|Ax-b\|^2+\alpha\|x\|^2$ を最小にする $x$ を、$b$ の Tikhonov 正則化解 といい、$x_\alpha$ と書く。$b$ の代わりに誤差を含む $b^\delta$($\|b^\delta-b\|\le\delta$)を使ったものを $x_\alpha^\delta$ と書く。
結論を使う条件は次のとおりである。
| 量 | 式 | 使える条件 | 根拠 |
|---|---|---|---|
| 解の式 | $x_\alpha=(A^*A+\alpha I)^{-1}A^*b=A^*(AA^*+\alpha I)^{-1}b$ | $\alpha>0$ | thm-tik-main |
| 安定性 | $\Vert x_\alpha^\delta-x_\alpha\Vert\le\delta/(2\sqrt\alpha)$ | $\Vert b^\delta-b\Vert\le\delta$ | thm-tik-main |
| 特異値の形 | $x_\alpha=\sum_i\frac{\sigma_i}{\sigma_i^2+\alpha}\langle b,u_i\rangle v_i$ | 行列またはコンパクト作用素 | cor-tik-filter |
| 誤差の式 | $x_\alpha-x^\dagger=-\alpha(A^*A+\alpha I)^{-1}x^\dagger$ | $b\in R(A)+R(A)^\perp$ | thm-tik-limit |
| 速さ | $\Vert x_\alpha-x^\dagger\Vert\le\frac{\sqrt\alpha}2\Vert w\Vert$ | $x^\dagger=A^*w$ | thm-tik-limit |
| 速さ | $\Vert x_\alpha-x^\dagger\Vert\le\alpha\Vert w\Vert$ | $x^\dagger=A^*Aw$ | thm-tik-limit |
| 雑音込みの最良の順 | $\sqrt{\delta\Vert w\Vert}$($\alpha=\delta/\Vert w\Vert$) | $x^\dagger=A^*w$ | thm-tik-noise |
| 不一致原理 | $\Vert x_\alpha^\delta-x^\dagger\Vert\le\sqrt{2(\tau+1)\delta\Vert w\Vert}$ | $b=Ax^\dagger$、$x^\dagger=A^*w$、$\tau>1$ | thm-tik-morozov |
| リッジ回帰の平均二乗誤差 | $\sum_i\frac{s^2\sigma_i^2+\alpha^2\beta_i^2}{(\sigma_i^2+\alpha)^2}$ | $\sigma_i>0$、雑音が無相関で分散 $s^2$ | prop-tik-ridge |
| 実効自由度 | $\sum_i\sigma_i^2/(\sigma_i^2+\alpha)$ | 行列 | prop-tik-ridge |
$\alpha>0$ とする。
1:$B=A^*A+\alpha I$ は自己随伴で、$\operatorname{Re}\langle Bx,x\rangle=\|Ax\|^2+\alpha\|x\|^2\ge\alpha\|x\|^2$ である。Schwarz の不等式から $\|Bx\|\ge\alpha\|x\|$ なので、$B$ は単射で値域は閉じている。値域の直交補は $N(B^*)=N(B)=0$ なので全射である。逆の評価は $\|Bx\|\ge\alpha\|x\|$ そのものである。
2:$x_\alpha=B^{-1}A^*b$ とおくと $A^*(Ax_\alpha-b)+\alpha x_\alpha=0$ である。展開すると
$$
T_\alpha(x_\alpha+h)=T_\alpha(x_\alpha)+2\operatorname{Re}\langle A^*(Ax_\alpha-b)+\alpha x_\alpha,h\rangle+\|Ah\|^2+\alpha\|h\|^2
$$
で、中央の項は $0$ である。$h\ne0$ なら増えるので、最小点はこれだけである。$A^*(AA^*+\alpha I)=(A^*A+\alpha I)A^*$ に両側から逆を掛けると、もう 1 つの式を得る。
3:正規方程式と $x_\alpha$ の内積をとると $\alpha\|x_\alpha\|^2=\operatorname{Re}\langle b,Ax_\alpha\rangle-\|Ax_\alpha\|^2\le\|b\|\,\|Ax_\alpha\|-\|Ax_\alpha\|^2\le\|b\|^2/4$ である。これは $\|B^{-1}A^*b\|\le\|b\|/(2\sqrt\alpha)$ を意味する。$x_\alpha^\delta-x_\alpha=B^{-1}A^*(b^\delta-b)$ なので後半が従う。$\square$
$A=\sum_i\sigma_iu_iv_i^*$($\sigma_i>0$、行列またはコンパクト作用素)なら
$$
x_\alpha=\sum_i\frac{\sigma_i^2}{\sigma_i^2+\alpha}\cdot\frac{\langle b,u_i\rangle}{\sigma_i}v_i
$$
である。最小ノルム解の各項 $\langle b,u_i\rangle v_i/\sigma_i$ に フィルタ $\sigma_i^2/(\sigma_i^2+\alpha)$ が掛かり、$\sigma_i^2\gg\alpha$ の項はほぼそのまま残り、$\sigma_i^2\ll\alpha$ の項は抑えられる。
$A^*Av_i=\sigma_i^2v_i$ で、$v_i$ の直交補の上では $A^*A=0$ である。$A^*b=\sum_i\sigma_i\langle b,u_i\rangle v_i$ に $(A^*A+\alpha I)^{-1}$ を掛ける。$\square$
$b\in R(A)+R(A)^\perp$ とし、$e_\alpha=x_\alpha-x^\dagger$ とする。
$B=A^*A+\alpha I$ とする。1:$A^*b=A^*Ax^\dagger=(B-\alpha I)x^\dagger$ なので $x_\alpha=x^\dagger-\alpha B^{-1}x^\dagger$ である。$\|\alpha B^{-1}\|\le1$ から評価を得る。
2:thm-tik-main の 3 から $\|\alpha B^{-1}A^*w\|\le\frac{\sqrt\alpha}2\|w\|$ である。また $B^{-1}A^*A=I-\alpha B^{-1}$ のノルムは $1$ 以下なので $\|\alpha B^{-1}A^*Aw\|\le\alpha\|w\|$ である。
1 の収束:$x^\dagger\in N(A)^\perp=\overline{R(A^*)}$ なので、$\varepsilon>0$ に対し $\|x^\dagger-A^*w\|<\varepsilon$ となる $w$ がある。$\|\alpha B^{-1}\|\le1$ と 2 の計算から $\|e_\alpha\|\le\varepsilon+\frac{\sqrt\alpha}2\|w\|$ である。
3:$y=B^{-1}x^\dagger$ とすると $\|x^\dagger\|=\|By\|\le(\|A\|^2+\alpha)\|y\|$、$\|e_\alpha\|=\alpha\|y\|$ である。
4:$\alpha_n\to0$ で $x_n=x_{\alpha_n}$ が有界だとする。部分列をとって $x_n$ は $x$ に弱収束するとしてよい。$A^*Ax_n=A^*b-\alpha_nx_n\to A^*b$ で、$A^*A$ は弱連続なので $A^*Ax=A^*b$ である。よって $b-Ax\in N(A^*)=R(A)^\perp$ で、$b\in R(A)+R(A)^\perp$ となり矛盾する。$\square$
3 の現象を 飽和 という。$x^\dagger$ がいくら滑らかでも、誤差は $\alpha$ の 1 次より速く減らない。
$b\in R(A)+R(A)^\perp$、$\|b^\delta-b\|\le\delta$ とする。
$$
\|x_\alpha^\delta-x^\dagger\|\le\frac\delta{2\sqrt\alpha}+\|e_\alpha\|
$$
である。したがって次が成り立つ。
三角不等式と thm-tik-main の 3 による。1 は thm-tik-limit の 1 から従う。2 は $\frac\delta{2\sqrt\alpha}+\frac{\sqrt\alpha}2\|w\|$ に代入する。3 は $\frac\delta{2\sqrt\alpha}+\alpha\|w\|$ に代入すると、$\alpha^{3/2}=\delta/(4\|w\|)$ から第 1 項が $2\alpha\|w\|$ になり、和は $3\alpha\|w\|$ である。$\square$
第 1 項は $\alpha$ を小さくすると増え、第 2 項は減る。この 2 つの釣り合いで最良の $\alpha$ が決まり、$\alpha$ を小さくしていくと誤差は一度減ってから増える(ex-tik-integral)。ただし上の $\alpha$ は $\|w\|$ を知らないと決められない。
雑音の大きさ $\delta$ だけ分かるなら、残差が雑音と同じ大きさになるところまで緩める。これを 不一致原理 という(Morozov)。
$b=Ax^\dagger$、$\delta>0$、$\|b^\delta-b\|\le\delta$、$\tau>1$、$\|b^\delta\|>\tau\delta$ とし、$\varphi(\alpha)=\|Ax_\alpha^\delta-b^\delta\|$ とおく。
$x_\alpha=x_\alpha^\delta$ と略す。
1:$b^\delta-Ax_\alpha=\alpha(AA^*+\alpha I)^{-1}b^\delta$ である(thm-tik-main の 2 の式による)。したがって $\varphi$ は連続である。$\alpha<\beta$ とする。$T_\alpha(x_\alpha)\le T_\alpha(x_\beta)$ と $T_\beta(x_\beta)\le T_\beta(x_\alpha)$ を足すと $\|x_\beta\|\le\|x_\alpha\|$ を得て、最初の不等式から
$$
\varphi(\beta)^2-\varphi(\alpha)^2\ge\alpha(\|x_\alpha\|^2-\|x_\beta\|^2)\ge0
$$
である。等号なら $T_\alpha(x_\beta)=T_\alpha(x_\alpha)$ なので最小点の一意性から $x_\alpha=x_\beta$ で、2 つの正規方程式の差から $x_\alpha=0$、すなわち $A^*b^\delta=0$ である。
極限を調べる。$\alpha\to\infty$ では $\|Ax_\alpha\|\le\|A\|\,\|b^\delta\|/(2\sqrt\alpha)\to0$ なので $\varphi\to\|b^\delta\|$ である。$\alpha\to0$ では、$H=AA^*$ として $C_\alpha=\alpha(H+\alpha I)^{-1}$ は $\|C_\alpha\|\le1$ を満たし、$z\in N(A^*)$ で $C_\alpha z=z$、$z=Au$ で $\|C_\alpha Au\|=\alpha\|A(A^*A+\alpha I)^{-1}u\|\le\frac{\sqrt\alpha}2\|u\|\to0$ である($A(A^*A+\alpha I)^{-1}$ は thm-tik-main の 3 の作用素の随伴である)。稠密性から $C_\alpha b^\delta\to(I-Q)b^\delta$ で、$b\in R(A)$ なので $\lim_{\alpha\to0}\varphi=\|(I-Q)(b^\delta-b)\|\le\delta$ である。
$\tau>1$ と仮定から、$\lim_{\alpha\to0}\varphi\le\delta< \tau\delta< \|b^\delta\|=\lim_{\alpha\to\infty}\varphi$ である。とくに $\varphi$ は定数でなく、$A^*b^\delta\ne0$($A^*b^\delta=0$ なら $\varphi\equiv\|b^\delta\|$)なので狭義単調である。中間値の定理から解はただ 1 つある。
2:$T_\alpha(x_\alpha)\le T_\alpha(x^\dagger)$ から $\tau^2\delta^2+\alpha\|x_\alpha\|^2\le\delta^2+\alpha\|x^\dagger\|^2$ で、$\tau>1$ より $\|x_\alpha\|\le\|x^\dagger\|$ である。残差は三角不等式による。
3:2 から
$$
\|x_\alpha-x^\dagger\|^2\le2\|x^\dagger\|^2-2\operatorname{Re}\langle x_\alpha,x^\dagger\rangle=2\operatorname{Re}\langle x^\dagger-x_\alpha,A^*w\rangle=2\operatorname{Re}\langle b-Ax_\alpha,w\rangle\le2(\tau+1)\delta\|w\|
$$
である。
4:$b=0$ なら $x^\dagger=0$ で、$\|x^\delta\|\le\|x^\dagger\|$ から明らかである($\|b^\delta\|\le\tau\delta$ なら $x^\delta=0$)。$b\ne0$ なら、小さい $\delta$ で $\|b^\delta\|\ge\|b\|-\delta>\tau\delta$ である。$\varepsilon>0$ に対し $x^\dagger=A^*w+z$、$\|z\|<\varepsilon$ とすると、3 と同じ計算で $\|x_\alpha-x^\dagger\|^2\le2(\tau+1)\delta\|w\|+4\|x^\dagger\|\varepsilon$ である。$\delta\to0$、$\varepsilon\to0$ の順に極限をとる。$\square$
計画行列 $Z$($n\times p$)、$y=Z\beta+\varepsilon$ の線形回帰で、$A=Z$、$b=y$ とした $\hat\beta_\alpha=(Z^{\mathsf T}Z+\alpha I)^{-1}Z^{\mathsf T}y$ を リッジ回帰 の推定量という(HTF09 §3.4.1、pp. 63–64。BV04 §6.3.2、p. 306 の問題と同じものである)。
$Z$ の特異値を $\sigma_1,\dots,\sigma_p>0$、右特異ベクトルを $v_i$、$\beta_i=\langle\beta,v_i\rangle$ とし、$\varepsilon$ は平均 $0$、共分散行列 $s^2I$($s>0$)とする。
$$
\operatorname{MSE}(\alpha):=E\|\hat\beta_\alpha-\beta\|^2=\sum_{i=1}^p\frac{s^2\sigma_i^2+\alpha^2\beta_i^2}{(\sigma_i^2+\alpha)^2}
$$
である。$\operatorname{MSE}'(0)=-2s^2\sum_i\sigma_i^{-4}< 0$ なので、十分小さい $\alpha>0$ でリッジ回帰の平均二乗誤差は最小二乗推定量より小さい。また $\operatorname{tr}\bigl(Z(Z^{\mathsf T}Z+\alpha I)^{-1}Z^{\mathsf T}\bigr)=\sum_i\sigma_i^2/(\sigma_i^2+\alpha)$(実効自由度)である。
$\tilde\varepsilon_i=\langle\varepsilon,u_i\rangle$ とすると $E\tilde\varepsilon_i=0$、$E\tilde\varepsilon_i^2=s^2$ である。cor-tik-filter から $\langle\hat\beta_\alpha,v_i\rangle=\frac{\sigma_i}{\sigma_i^2+\alpha}(\sigma_i\beta_i+\tilde\varepsilon_i)$ なので、
$$
\langle\hat\beta_\alpha-\beta,v_i\rangle=-\frac{\alpha\beta_i}{\sigma_i^2+\alpha}+\frac{\sigma_i\tilde\varepsilon_i}{\sigma_i^2+\alpha}
$$
である。第 1 項が偏り、第 2 項の分散が $s^2\sigma_i^2/(\sigma_i^2+\alpha)^2$ で、平方の期待値を足すと式を得る。$\alpha=0$ で微分すると、分子の項は $\alpha$ の 2 次なので寄与せず、$-2s^2\sigma_i^2/\sigma_i^6$ が残る。跡は $Z$ を特異値分解すれば分かる。$\square$
最小二乗推定量は線形不偏推定量の中で分散が最小である(Gauss–Markovの定理)。この命題は、不偏性を捨てれば平均二乗誤差でそれを超えられることを示す。$\beta$ の事前分布を $N(0,(s^2/\alpha)I)$、雑音を $N(0,s^2I)$ とすれば、$\hat\beta_\alpha$ は事後分布の最頻値である(HTF09 p. 64、Bayes統計)。
図: 左は特異値 σ に対するフィルタ σ²/(σ²+α) のグラフで、α を 10⁻⁴、10⁻²、1 としたとき、σ² が α より十分大きければ 1 に近く、十分小さければ 0 に近い。右は例題「積分作用素」の誤差を α に対して両対数目盛で描いたもので、誤差は α を小さくすると一度減ってから増え、不一致原理の α は最小の近くにある。
$A=\begin{pmatrix}1&1\\1&1.001\end{pmatrix}$、$b=(2,\ 2.001)$、$x^\dagger=(1,1)$、$b^\delta=(2,\ 2.002)$($\delta=0.001$)とする。
使う公式:thm-tik-main、thm-tik-noise、thm-tik-morozov。
答え:特異値は $2.0005,\ 0.0005$、条件数は $4002.0$ で、素朴な解は $(0,2)$(誤差 $1.414$)である。$\tau=1.1$ の不一致原理では $\alpha\approx0.0011926$、$x_\alpha^\delta\approx(0.99949,\ 1.00041)$、誤差 $6.53\times10^{-4}$ である。
| $\alpha$ | $x_\alpha^\delta$ | 誤差 | 残差 |
|---|---|---|---|
| $10^{-6}$ | $(0.80008,\ 1.20032)$ | $0.2830$ | $5.65\times10^{-4}$ |
| $10^{-5}$ | $(0.97562,\ 1.02486)$ | $0.0348$ | $6.90\times10^{-4}$ |
| $10^{-4}$ | $(0.99748,\ 1.00297)$ | $0.00389$ | $7.09\times10^{-4}$ |
| $10^{-3}$ | $(0.99950,\ 1.00050)$ | $7.07\times10^{-4}$ | $9.995\times10^{-4}$ |
| $10^{-2}$ | $(0.99748,\ 0.99803)$ | $0.00320$ | $0.00709$ |
| $10^{-1}$ | $(0.97562,\ 0.97611)$ | $0.0341$ | $0.0690$ |
$A=\operatorname{diag}(1,\ 0.1,\ 0.01)$、$x^\dagger=(1,1,1)$、$b^\delta=Ax^\dagger+0.01\cdot(1,1,1)/\sqrt3$ とする。
使う公式:cor-tik-filter。
答え:素朴な解は $(1.00577,\ 1.05774,\ 1.57735)$(誤差 $0.5803$)で、誤差は最も小さい特異値の成分に集まる。
| $\alpha$ | フィルタ | $x_\alpha^\delta$ | 誤差 |
|---|---|---|---|
| $10^{-4}$ | $(0.9999,\ 0.9901,\ 0.5)$ | $(1.00567,\ 1.04726,\ 0.78868)$ | $0.2166$ |
| $10^{-3}$ | $(0.9990,\ 0.9091,\ 0.0909)$ | $(1.00477,\ 0.96158,\ 0.14340)$ | $0.8575$ |
| $10^{-2}$ | $(0.9901,\ 0.5,\ 0.0099)$ | $(0.99581,\ 0.52887,\ 0.01562)$ | $1.0913$ |
$\alpha$ が大きいと第 3 成分が失われ、誤差はかえって増える。$\alpha$ は大きいほど良いのではない。
$(Ax)(t)=\int_0^tx(s)\,ds$ を $[0,1]$ の幅 $h=0.01$ の 100 個の格子で離散化する。行列は $h$ に下三角の $1$ を掛け、対角を $h/2$ としたもの(中点則)である。$x^\dagger_i=\sin(\pi t_i)$($t_i=(i-\frac12)h$)、$\|x^\dagger\|\approx7.071$、雑音は $\delta=0.01$ で、成分が $\delta(-1)^{i-1}/10$ のベクトルとする。
使う公式:thm-tik-noise、thm-tik-morozov。
答え:条件数は $16210.7$ で、素朴な解の誤差は $230.9$ である。$\alpha$ を小さくしていくと誤差は一度減って増える(図の右)。
| $\alpha$ | $10^{-8}$ | $10^{-6}$ | $10^{-5}$ | $10^{-4}$ | $10^{-3}$ | $10^{-2}$ | $10^{-1}$ |
|---|---|---|---|---|---|---|---|
| 誤差 | $35.25$ | $1.118$ | $0.1989$ | $0.0423$ | $0.1398$ | $0.8160$ | $2.892$ |
$\tau=1.1$ の不一致原理は $\alpha\approx2.127\times10^{-4}$、誤差 $0.0463$ で、最良の $\alpha\approx1.30\times10^{-4}$ の誤差 $0.0407$ に近い。$\delta$ を変えたときの不一致原理の誤差は次のとおりである。
| $\delta$ | $0.1$ | $0.01$ | $0.001$ | $10^{-4}$ |
|---|---|---|---|---|
| 誤差 | $0.2699$ | $0.0463$ | $0.0134$ | $0.0063$ |
$\sigma=(1,\ 0.1)$、$\beta_i=1$($i=1,2$)、$s^2=0.01$ とする。
使う公式:prop-tik-ridge。
答え:最小二乗推定量の平均二乗誤差は $1.01$ である。$\alpha=0.01$ で $0.50990$ となり、これが最小値である。実効自由度は $1.4901$ である。
$\beta_i=1$ のとき、各項 $\frac{s^2\sigma_i^2+\alpha^2}{(\sigma_i^2+\alpha)^2}$ の $\alpha$ についての微分は $\frac{2\sigma_i^2(\alpha-s^2)}{(\sigma_i^2+\alpha)^3}$ なので、$\alpha=s^2$ で最小である。値は各項が $\frac{\alpha}{\sigma_i^2+\alpha}$ となり、$\frac{0.01}{1.01}+\frac{0.01}{0.02}$ である。
各行は、結論に必要な仮定を 1 つだけ外す。
| 外す仮定 | 反例 | 成り立たなくなること |
|---|---|---|
| $\alpha>0$ | $A=(1\ \ 1)$、$b=2$、$\alpha=0$ | $x_1+x_2=2$ のすべてが最小点で、一意でない。$\alpha>0$ なら $x_\alpha=\frac2{2+\alpha}(1,1)$ |
| $b\in R(A)+R(A)^\perp$ | $\ell^2$ で $Ae_i=e_i/i$、$b_i=1/i$ | $\Vert x_\alpha\Vert\to\infty$($\alpha^{-1/4}$ の程度) |
| $\delta^2/\alpha\to0$ | $Ae_i=e_i/i$、$b=0$、$\delta=1/n$、$b^\delta=\delta e_n$、$\alpha=\delta^2$ | $\alpha,\delta\to0$ でも $\Vert x_\alpha^\delta\Vert=\frac12$ で、$x^\dagger=0$ に収束しない |
| $x^\dagger\in R(A^*)$ | $Ae_i=e_i/i$、$x^\dagger_i=1/i$、$b=Ax^\dagger$ | 収束はするが $\Vert e_\alpha\Vert$ は $\alpha^{1/4}$ の程度で、$\sqrt\alpha$ の上界が成り立たない |
| $\Vert b^\delta\Vert>\tau\delta$ | $A=1$、$b^\delta=\delta$、$\tau=2$ | $\varphi(\alpha)=\frac{\alpha\delta}{1+\alpha}< \delta< \tau\delta$ で、$\varphi(\alpha)=\tau\delta$ に解がない |
2 行目:$b_i=\sigma_i\cdot1$ で $(1,1,\dots)\notin\ell^2$ なので $b\notin R(A)$ で、$R(A)^\perp=0$ である。$x_{\alpha,i}=\frac1{1+\alpha i^2}$ で、和を積分と比べると $\Vert x_\alpha\Vert^2$ は $\alpha^{-1/2}$ の程度である。3 行目:$x_{\alpha,n}^\delta=\frac{\sigma_n\delta}{\sigma_n^2+\alpha}=\frac{n^{-2}}{2n^{-2}}=\frac12$ である。4 行目:$w_i=1$ が必要で $\ell^2$ に入らない。$e_{\alpha,i}=\frac{\alpha i^2}{1+\alpha i^2}\cdot\frac1i$ で、$\alpha=10^{-2},\ 10^{-4},\ 10^{-6}$ のとき $\Vert e_\alpha\Vert\approx0.2802,\ 0.0886,\ 0.0279$ である。比 $\Vert e_\alpha\Vert/\sqrt\alpha$ は $2.8,\ 8.9,\ 27.9$ と増える。
| 誤り | 正しくは | なぜ |
|---|---|---|
| $\alpha$ は大きいほど安定で良いとする | 偏りが増えるので、雑音との釣り合いで選ぶ | thm-tik-noise、ex-tik-diag |
| $\alpha$ を小さくすれば必ず真の解に近づくとする | 雑音があると、ある所から誤差は増える | ex-tik-integral |
| 雑音の大きさを知らずに $\tau\delta$ で止める | $\delta$ の見積もりが小さすぎると解が暴れる。分からないなら別の選び方を使う | thm-tik-morozov は $\delta$ を入力とする |
| 正規方程式を丸めの注意なく解く | 悪条件なら QR 分解か特異値分解を使う | 手順 2 |
| 説明変数の尺度を変えても解は同じとする | リッジ回帰は尺度に依存する。最小二乗法とは違う | 手順 1 |
| 解が滑らかなほど収束はいくらでも速くなるとする | 誤差は $\alpha$ の 1 次より速くならない | thm-tik-limit の 3 |
$L$ を有界線形作用素、$x_0$ を基準の点として $\|Ax-b\|^2+\alpha\|L(x-x_0)\|^2$ を最小にする形もよく使う($L$ を差分にすれば滑らかさを求める。BV04 §6.3.2、p. 307)。行列で $N(A)\cap N(L)=\{0\}$ なら $A^*A+\alpha L^*L$ は正則で、解は $(A^*A+\alpha L^*L)^{-1}(A^*b+\alpha L^*Lx_0)$ である。条件を外すと一意でない。たとえば $A=L=(1\ \ 0)$ なら行列は特異で、$x_2$ が決まらない。
| 方法 | フィルタ $f(\sigma)$ | 性質 |
|---|---|---|
| Tikhonov | $\sigma^2/(\sigma^2+\alpha)$ | 滑らか。thm-tik-limit の飽和がある |
| 打ち切り | $\sigma^2\ge\alpha$ で $1$、それ以外 $0$ | $A$ の階数の低い最良近似で解くのと同じ(Eckart–Youngの定理) |
| 反復 Tikhonov($m$ 回) | $1-\bigl(\alpha/(\sigma^2+\alpha)\bigr)^m$ | $x_{j+1}=x_j+(A^*A+\alpha I)^{-1}A^*(b-Ax_j)$、$x_0=0$ |
| Landweber($k$ 回) | $1-(1-\omega\sigma^2)^k$ | $x_{j+1}=x_j+\omega A^*(b-Ax_j)$、$x_0=0$。最小二乗の勾配降下法 で、$k$ が正則化パラメータの役をする |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する