逆問題

同義語:inverse problem

概要

逆問題(inverse problem)とは、順写像 $F$ による観測 $y=F(x)$ から原因 $x$ を求める問題である。解の存在・一意性・データへの連続依存がそろう問題を適切といい、階数が無限のコンパクト作用素の逆は連続でないので、第 1 種の積分方程式の多くは不適切である。解ける条件は特異値で判定でき(Picard の条件)、正則化で雑音の増幅を抑える。ソース条件のもとで誤差の順は $\delta^{2\nu/(2\nu+1)}$ で、どの方法もこれより速い順にはできない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: コンパクト作用素, 特異値分解, Hilbert空間, 随伴作用素

原因から結果を計算するのが順問題で、結果の観測から原因を求めるのが 逆問題(inverse problem)である。CT の投影データから体内の密度を求める、ぼけた画像からもとの画像を求める、終わりの温度分布から始めの温度分布を求める、といった問題がこれにあたる。
逆問題の難しさは、順問題の計算が滑らかにする方向に働くことから来る。滑らかにする写像は細かい成分を弱めるので、逆にたどると細かい成分が増幅される。たとえば $f$ に $\delta\sin(x/\delta^2)$ という大きさ $\delta$ の雑音が乗ると、微分した $f'$ には振幅 $1/\delta$ の雑音が乗る。積分という順問題の逆である微分は、データの小さな誤差で大きく変わる。
この記事は分野の入口である。逆問題の不安定性がコンパクト作用素の性質から必ず起こること(thm-ip-compact)、解ける条件が特異値で読めること(thm-ip-picard)を示し、不安定性を抑える正則化の一般論(thm-ip-filter)と、事前の情報なしには超えられない精度の限界(thm-ip-lower)を述べる。個々の方法と問題は、下の一覧から各記事へ進む。

定義と使える条件

$X,Y$ をノルム空間、$D\subset X$ を部分集合とし、$F\colon D\to Y$ を写像とする。$F$ を 順写像(forward map)という。

逆問題と適切性

$y\in Y$ から $F(x)=y$ を満たす $x\in D$ を求める問題を 逆問題 という。次の 3 条件がすべて成り立つとき、この問題は 適切(well-posed)であるという。

  1. 存在:すべての $y\in Y$ に解がある。
  2. 一意性:解は高々 1 つである。
  3. 安定性:解は $y$ に連続に依存する。つまり $F^{-1}\colon Y\to X$ が連続である。
    適切でない問題を 不適切(ill-posed)という。

実際に難しいのは 3 である。1 と 2 は最小二乗解と最小ノルム解に取り替えれば、線形の問題では多くの場合に解消できる。

最小ノルム最小二乗解

$A\colon X\to Y$ を Hilbert 空間の間の有界線形作用素とする。$\|Ax-b\|$ を最小にする $x$ のうちノルムが最小のものを $b$ の 最小ノルム最小二乗解 といい、$x^\dagger$ と書く。$x^\dagger$ が存在するのは $b\in R(A)+R(A)^\perp$ のときで、その $b$ の全体を $D(A^\dagger)$ と書く。$b\mapsto x^\dagger$ を $A^\dagger$ と書く。行列のときは Moore–Penrose逆行列 である。

「逆問題」という語は別の意味でも使う。Jacobi の逆問題は正則 1 形式の積分の値から因子を求める問題(Abel–Jacobiの定理)で、Hartogs の逆問題は Levi問題 の別名であり、逆 Galois 問題は与えられた群を Galois 群にもつ拡大を問う(逆Galois問題)。いずれもこの記事の主題ではない。

分野の一覧

問題順写像難しさ記事
正則化線形作用素 $A$雑音の増幅を抑えるTikhonov正則化
第 1 種の方程式積分作用素逆写像の非有界性積分方程式
断層撮影$f\mapsto Rf$中程度の不安定性、データ不足で非一意Radon変換
境界からの電気探査伝導率 $\mapsto$ 境界の応答非線形で対数型の安定性Calderón問題
非線形波の解法ポテンシャル $\mapsto$ 散乱データ逆写像を積分方程式で構成逆散乱法
太鼓の形図形 $\mapsto$ 固有値の列一意性が成り立たない等スペクトル問題
疎な信号の復元$x\mapsto Ax$($m< d$)疎という仮定で一意性を回復圧縮センシング
統計的な定式化事前分布と観測の分布不確かさごと求めるBayes統計

公式の表

$A$ はコンパクト作用素、$(\sigma_i,v_i,u_i)$ はその特異系、$\|b^\delta-b\|\le\delta$ とする。

内容公式条件根拠
逆の非有界性$\Vert x_k\Vert=1$、$\Vert Ax_k\Vert\to0$ となる列がある$A$ の階数が無限thm-ip-compact
Picard の判定$b\in D(A^\dagger)\iff\sum_i\lvert\langle b,u_i\rangle\rvert^2/\sigma_i^2< \infty$$A$ がコンパクトthm-ip-picard
解の展開$x^\dagger=\sum_i\sigma_i^{-1}\langle b,u_i\rangle v_i$$b\in D(A^\dagger)$thm-ip-picard
誤差の分解偏り $+\ C_\alpha\delta$フィルタ法thm-ip-filter
最良の速さ$E^{1/(2\nu+1)}\delta^{2\nu/(2\nu+1)}$$x^\dagger=(A^*A)^\nu w$、$\Vert w\Vert\le E$thm-ip-filter, thm-ip-lower

不安定性の原因

コンパクト作用素の逆

積分作用素や、滑らかな核をもつ作用素の多くはコンパクトである(Hilbert–Schmidt作用素)。すると次の定理により、逆問題は必ず不適切になる。

コンパクト作用素の逆は連続でない

$X,Y$ を Hilbert 空間、$A\colon X\to Y$ を階数が無限のコンパクト作用素とする。

  1. $N(A)^\perp$ の正規直交列 $(x_k)$ で $\|Ax_k\|\to0$ となるものがある。
  2. $A^\dagger\colon D(A^\dagger)\to X$ は有界でない。
  3. $R(A)$ は閉でない。したがって $D(A^\dagger)\ne Y$ である。
正規直交列は弱収束で $0$ に近づく
  1. $A$ の階数が無限なので、$N(A)^\perp$ は無限次元である(有限次元なら $A$ の像も有限次元になる)。その正規直交列 $(x_k)$ をとる。Bessel の不等式より $\sum_k\lvert\langle x_k,z\rangle\rvert^2\le\|z\|^2$ なので、すべての $z$ で $\langle x_k,z\rangle\to0$、つまり $x_k$ は弱収束で $0$ に近づく。コンパクト作用素は弱収束する列をノルム収束する列に写すから、$\|Ax_k\|\to0$ である。
  2. $A^\dagger Ax_k=x_k$ である。$x_k\in N(A)^\perp$ は $Ax_k$ の最小ノルムの解だからである。$\|A^\dagger Ax_k\|/\|Ax_k\|=1/\|Ax_k\|\to\infty$ なので、$A^\dagger$ は有界でない。
  3. $R(A)$ が閉なら、$A\colon N(A)^\perp\to R(A)$ は Banach 空間の間の全単射の有界線形作用素なので、開写像定理より逆も有界である。これは 1 に反する。$R(A)$ が閉でないとき、$b\in\overline{R(A)}\setminus R(A)$ をとる。$b=Ax+c$($c\perp R(A)$)と書けたとすると $c=b-Ax\in\overline{R(A)}\cap R(A)^\perp=\{0\}$ となり $b\in R(A)$ となるので、$b\notin D(A^\dagger)$ である。$\square$

定理の 1 の意味を確かめておく。$x$ が $Ax=b$ の解なら、大きさ $\delta$ の雑音 $\delta Ax_k/\|Ax_k\|$ を $b$ に加えると、解は $\delta x_k/\|Ax_k\|$ だけ動く。この動きは $k$ を大きくすれば $\delta$ がどれほど小さくても限りなく大きくなる。計算機の精度を上げても、測定を良くしても、問題の性質は変わらない。

特異値で読む

コンパクト作用素 $A$ には 特異系 がある。正の数の減少列 $\sigma_1\ge\sigma_2\ge\cdots>0$ と、$N(A)^\perp$ の正規直交基底 $(v_i)$、$\overline{R(A)}$ の正規直交基底 $(u_i)$ で、$Av_i=\sigma_iu_i$、$A^*u_i=\sigma_iv_i$ を満たすものである($A^*A$ のスペクトル分解から作る)。階数が無限なら $\sigma_i\to0$ である。

Picard の判定条件

$A$ をコンパクト作用素、$(\sigma_i,v_i,u_i)$ をその特異系とする。$b\in Y$ について次は同値である。

  1. $b\in D(A^\dagger)=R(A)+R(A)^\perp$
  2. $\displaystyle\sum_i\frac{\lvert\langle b,u_i\rangle\rvert^2}{\sigma_i^2}< \infty$
    このとき
    $$ x^\dagger=\sum_i\frac{\langle b,u_i\rangle}{\sigma_i}v_i $$
    である。
係数を比べる

1 ならば 2:$b=Ax+c$、$c\perp R(A)$ と書く。$u_i\in\overline{R(A)}$ なので $\langle c,u_i\rangle=0$ で、
$$ \langle b,u_i\rangle=\langle Ax,u_i\rangle=\langle x,A^*u_i\rangle=\sigma_i\langle x,v_i\rangle $$
である。Bessel の不等式より $\sum_i\lvert\langle b,u_i\rangle\rvert^2/\sigma_i^2=\sum_i\lvert\langle x,v_i\rangle\rvert^2\le\|x\|^2$ である。
2 ならば 1:2 の和が有限なので $x:=\sum_i\sigma_i^{-1}\langle b,u_i\rangle v_i$ は収束し、$N(A)^\perp$ に入る。$A$ は連続だから $Ax=\sum_i\langle b,u_i\rangle u_i=Qb$ である。ここで $Q$ は $\overline{R(A)}$ への直交射影である。$b-Qb\perp R(A)$ なので $b=Ax+(b-Qb)\in R(A)+R(A)^\perp$ である。
解の式:$\|Az-b\|^2=\|Az-Qb\|^2+\|b-Qb\|^2$ なので、最小二乗解は $Az=Qb$ の解の全体 $x+N(A)$ である。$x\in N(A)^\perp$ なのでその中でノルムが最小なのは $x$ である。$\square$

Picard の条件は、データの係数 $\langle b,u_i\rangle$ が特異値より速く減ることを求めている。雑音の係数は特異値より速くは減らないのがふつうなので、雑音の乗ったデータは一般にこの条件を満たさない。特異値の減り方が不安定性の程度を決める。

問題弱まり方程度詳しくは
積分 $\int_0^xf$$\sigma_k\sim1/(k\pi)$多項式ex-ip-volterra、Volterra作用素
Radon 変換周波数 $\sigma$ の成分を $\lvert\sigma\rvert^{-(n-1)/2}$ 倍多項式Radon変換 の定理「Plancherel の公式」
Gauss ぼかし周波数 $\xi$ の成分を $e^{-s^2\xi^2/2}$ 倍指数ex-ip-blur
逆向きの熱方程式$\sigma_k=e^{-k^2\pi^2T}$指数の 2 乗ex-ip-heat
Laplace 方程式の Cauchy 問題データ $1/k$ で解 $\sinh(k)/k^2$指数偏微分方程式 の例「Laplace 方程式の Cauchy 問題」
境界からの伝導率の決定非線形で対数型の評価対数Calderón問題 の注意「安定性」

正則化と精度の限界

フィルタ法の誤差

不安定なのは小さい特異値で割るからである。そこで $1/\sigma$ を、大きい $\sigma$ では $1/\sigma$ に近く、小さい $\sigma$ では有界な関数 $g_\alpha(\sigma)$ に取り替える。

フィルタ法

パラメータ $\alpha>0$ ごとに関数 $g_\alpha\colon(0,\|A\|]\to\mathbb{R}$ を与え、
$$ R_\alpha y:=\sum_ig_\alpha(\sigma_i)\langle y,u_i\rangle v_i $$
とおく。$C_\alpha:=\sup_\sigma\lvert g_\alpha(\sigma)\rvert< \infty$ とし、$r_\alpha(\sigma):=1-\sigma g_\alpha(\sigma)$ が $\lvert r_\alpha\rvert\le c_0$ を満たし、各 $\sigma$ で $\alpha\to0$ のとき $r_\alpha(\sigma)\to0$ となるものを フィルタ法 という。

代表的な方法は次の 3 つである。Landweber 法は $x_{k+1}=x_k+A^*(b-Ax_k)$、$x_0=0$ という反復で、$\|A\|\le1$ に正規化し、$\alpha=1/k$ とする。

方法$g_\alpha(\sigma)$$r_\alpha(\sigma)$$C_\alpha$$\sigma^{2\nu}\lvert r_\alpha\rvert$ の上界
Tikhonov正則化$\sigma/(\sigma^2+\alpha)$$\alpha/(\sigma^2+\alpha)$$1/(2\sqrt\alpha)$$\alpha^\nu$($0< \nu\le1$ のときだけ)
打ち切り特異値分解$\sigma^2\ge\alpha$ で $1/\sigma$、他は $0$$\sigma^2< \alpha$ で $1$、他は $0$$1/\sqrt\alpha$$\alpha^\nu$(すべての $\nu>0$)
Landweber 法$(1-(1-\sigma^2)^k)/\sigma$$(1-\sigma^2)^k$$\sqrt k=1/\sqrt\alpha$ 以下$(\nu/e)^\nu\alpha^\nu$(すべての $\nu>0$)

いずれも $c_0=1$ である。表の値は次のように確かめる。Tikhonov の $C_\alpha$ は $\sigma^2+\alpha\ge2\sigma\sqrt\alpha$ から、$\sigma^{2\nu}$ の上界は重み付きの相加相乗平均 $\sigma^{2\nu}\alpha^{1-\nu}\le\nu\sigma^2+(1-\nu)\alpha\le\sigma^2+\alpha$ から出る。Landweber の $C_\alpha$ は $1-(1-t)^k\le\min\{1,kt\}$ から $g\le\min\{1/\sigma,k\sigma\}\le\sqrt k$ となり、$\sigma^{2\nu}$ の上界は $(1-t)^k\le e^{-kt}$ と $\sup_{t>0}t^\nu e^{-kt}=(\nu/(ek))^\nu$ から出る。

フィルタ法の誤差と収束

$A$ をコンパクト作用素、$b\in D(A^\dagger)$、$x^\dagger:=A^\dagger b$、$\|b^\delta-b\|\le\delta$ とし、$x_\alpha^\delta:=R_\alpha b^\delta$ とする。

  1. 次の誤差の分解が成り立つ。
    $$ \|x_\alpha^\delta-x^\dagger\|\le\Bigl\|\sum_ir_\alpha(\sigma_i)\langle x^\dagger,v_i\rangle v_i\Bigr\|+C_\alpha\delta $$
  2. $\alpha\to0$ のとき $R_\alpha b\to x^\dagger$ である。
  3. $\delta\to0$ のとき $\alpha(\delta)\to0$ かつ $C_{\alpha(\delta)}\delta\to0$ となるように $\alpha(\delta)$ を選ぶと、$x_{\alpha(\delta)}^\delta\to x^\dagger$ である。
  4. $\nu>0$ について $x^\dagger=(A^*A)^\nu w$、$\|w\|\le E$ とし、$\sup_\sigma\sigma^{2\nu}\lvert r_\alpha(\sigma)\rvert\le\omega_\nu\alpha^\nu$、$C_\alpha\le c/\sqrt\alpha$ とする。$\alpha=(\delta/E)^{2/(2\nu+1)}$ と選ぶと
    $$ \|x_\alpha^\delta-x^\dagger\|\le(\omega_\nu+c)\,E^{\frac1{2\nu+1}}\delta^{\frac{2\nu}{2\nu+1}} $$
    である。
偏りと雑音に分ける

$Q$ を $\overline{R(A)}$ への直交射影とすると $Ax^\dagger=Qb$ である。thm-ip-picard の証明と同様に $\langle b,u_i\rangle=\sigma_i\langle x^\dagger,v_i\rangle$ である。

  1. 三角不等式で
    $$ \|x_\alpha^\delta-x^\dagger\|\le\|R_\alpha b-x^\dagger\|+\|R_\alpha(b^\delta-b)\| $$
    と分ける。$x^\dagger\in N(A)^\perp$ は $\sum_i\langle x^\dagger,v_i\rangle v_i$ と展開できるので、
    $$ R_\alpha b-x^\dagger=\sum_i\bigl(g_\alpha(\sigma_i)\sigma_i-1\bigr)\langle x^\dagger,v_i\rangle v_i=-\sum_ir_\alpha(\sigma_i)\langle x^\dagger,v_i\rangle v_i $$
    である。第 2 項は Bessel の不等式より $\|R_\alpha y\|^2=\sum_i\lvert g_\alpha(\sigma_i)\rvert^2\lvert\langle y,u_i\rangle\rvert^2\le C_\alpha^2\|y\|^2$ で抑えられる。
  2. $\|R_\alpha b-x^\dagger\|^2=\sum_i\lvert r_\alpha(\sigma_i)\rvert^2\lvert\langle x^\dagger,v_i\rangle\rvert^2$ の各項は $0$ に収束し、$c_0^2\lvert\langle x^\dagger,v_i\rangle\rvert^2$ で抑えられ、この上界の和は有限である。項別に極限をとれる(優収束定理)ので、和は $0$ に収束する。
  3. 1 の右辺の第 1 項は 2 により、第 2 項は仮定により $0$ に収束する。
  4. $\langle x^\dagger,v_i\rangle=\sigma_i^{2\nu}\langle w,v_i\rangle$ なので、1 の第 1 項は $\sup_\sigma\sigma^{2\nu}\lvert r_\alpha(\sigma)\rvert\cdot\|w\|\le\omega_\nu\alpha^\nu E$ 以下である。$\alpha=(\delta/E)^{2/(2\nu+1)}$ を代入すると
    $$ \omega_\nu E\Bigl(\frac\delta E\Bigr)^{\frac{2\nu}{2\nu+1}}=\omega_\nu E^{\frac1{2\nu+1}}\delta^{\frac{2\nu}{2\nu+1}},\qquad \frac{c\,\delta}{\sqrt\alpha}=c\,\delta\Bigl(\frac\delta E\Bigr)^{-\frac1{2\nu+1}}=c\,E^{\frac1{2\nu+1}}\delta^{\frac{2\nu}{2\nu+1}} $$
    となる。$\square$

定理の 3 は、雑音を小さくする速さに合わせて $\alpha$ を小さくすれば解に近づくことを述べる。$\alpha$ が小さすぎると雑音の項 $C_\alpha\delta$ が、大きすぎると偏りが誤差を支配する。正則化の仕事はこの釣り合いをとることである。Tikhonov の方法の個別の定理、とくに不一致原理の証明と飽和の現象は Tikhonov正則化 にある。
逆に $b\notin D(A^\dagger)$ なら、打ち切りの $\|R_\alpha b\|^2=\sum_{\sigma_i^2\ge\alpha}\lvert\langle b,u_i\rangle\rvert^2/\sigma_i^2$ は thm-ip-picard により $\alpha\to0$ で発散する。

条件付き安定性と超えられない限界

定理の 4 の仮定 $x^\dagger=(A^*A)^\nu w$ を ソース条件 という。解が $A$ に比べて滑らかであるという事前の情報で、$\nu$ が大きいほど強い。事前の情報があると、問題は安定になる。

条件付き安定性

$A$ をコンパクト作用素、$\nu>0$ とし、$x=(A^*A)^\nu w$、$\|w\|\le E$ とする。
$$ \|x\|\le E^{\frac1{2\nu+1}}\|Ax\|^{\frac{2\nu}{2\nu+1}} $$
が成り立つ。

Hölder の不等式

$N(A)$ の成分は $(A^*A)^\nu$ で消えるので $w\in N(A)^\perp$ としてよい。$c_i:=\langle w,v_i\rangle$ とおくと $\|x\|^2=\sum_i\sigma_i^{4\nu}c_i^2$、$\|Ax\|^2=\sum_i\sigma_i^{4\nu+2}c_i^2$ である。$p:=2\nu+1$、$q:=(2\nu+1)/(2\nu)$ とすると $1/p+1/q=1$ で、$\sigma_i^{4\nu}c_i^2=(c_i^2)^{1/p}(\sigma_i^{4\nu+2}c_i^2)^{1/q}$ である。Hölder の不等式より
$$ \|x\|^2\le\Bigl(\sum_ic_i^2\Bigr)^{1/p}\Bigl(\sum_i\sigma_i^{4\nu+2}c_i^2\Bigr)^{1/q}=\|w\|^{\frac2{2\nu+1}}\|Ax\|^{\frac{4\nu}{2\nu+1}} $$
である。$\square$

$x=E\sigma_i^{2\nu}v_i$ で等号が成り立つ。この不等式の指数は、どんな方法でも超えられない。

どの再構成にも共通の下界

$A$ をコンパクト作用素、$\nu>0$、$E>0$ とし、$M_{\nu,E}:=\{(A^*A)^\nu w:\|w\|\le E\}$ とおく。さらに
$$ \omega(\delta,E):=\sup\{\|x\|:x\in M_{\nu,E},\ \|Ax\|\le\delta\} $$
とおく。線形とは限らない任意の写像 $R\colon Y\to X$ について
$$ \sup\bigl\{\|R(y)-x\|:x\in M_{\nu,E},\ \|y-Ax\|\le\delta\bigr\}\ge\omega(\delta,E) $$
である。さらに、$\delta_i:=E\sigma_i^{2\nu+1}$ で $\omega(\delta_i,E)=E^{1/(2\nu+1)}\delta_i^{2\nu/(2\nu+1)}$ である。

同じデータを与える 2 つの解

$x\in M_{\nu,E}$、$\|Ax\|\le\delta$ とする。$M_{\nu,E}$ は符号で不変なので $-x\in M_{\nu,E}$ で、$y=0$ は $x$ と $-x$ のどちらのデータとしても誤差 $\delta$ 以内である。三角不等式より
$$ \max\{\|R(0)-x\|,\|R(0)+x\|\}\ge\tfrac12\bigl(\|R(0)-x\|+\|R(0)+x\|\bigr)\ge\|x\| $$
である。$x$ について上限をとると下界を得る。
後半:thm-ip-stability より $\omega(\delta,E)\le E^{1/(2\nu+1)}\delta^{2\nu/(2\nu+1)}$ である。$x:=E\sigma_i^{2\nu}v_i$ は $M_{\nu,E}$ に入り($w=Ev_i$)、$\|Ax\|=E\sigma_i^{2\nu+1}=\delta_i$、$\|x\|=E\sigma_i^{2\nu}=E^{1/(2\nu+1)}\delta_i^{2\nu/(2\nu+1)}$ なので、上界に達する。$\square$

thm-ip-filter の 4 と合わせると、階数が無限なら $\delta^{2\nu/(2\nu+1)}$ が最良の順である。最良とは、$\delta\to0$ で最悪の誤差を $o(\delta^{2\nu/(2\nu+1)})$ にはできないという意味で、下界の等号は列 $\delta_i$ の上だけで成り立つ(特異値が急に減ると、列の間の $\delta$ で $\omega$ は上界より小さくなる)。打ち切りと Landweber 法($k$ は整数に丸める)はすべての $\nu$ で、Tikhonov の方法は $\nu\le1$ でこの順を達成する。thm-ip-lower の $R$ は線形でなくてよいので、非線形の方法でも順は改善しない。

Bayes の見方

有限次元で $x$ に事前分布 $N(0,\tau^2I)$ を、雑音に $N(0,s^2I)$ を仮定すると、事後密度は $\exp(-\|Ax-b\|^2/(2s^2)-\|x\|^2/(2\tau^2))$ に比例する。Gauss 分布の平均は密度の最大点なので、事後平均は
$$ \hat x=(A^{\mathsf T}A+\alpha I)^{-1}A^{\mathsf T}b,\qquad\alpha=s^2/\tau^2 $$
である。Tikhonov の解は、事前分布を選んだときの事後平均と読める(Bayes統計)。

計算の手順

  1. 順写像を書く:未知量 $x$、データ $y$、ノルムを決め、雑音の水準 $\delta$ を見積もる。
  2. 離散化して特異値を見る:行列 $K$ を作り、特異値分解を計算する。特異値の減り方で不安定性の程度が分かる(特異値分解)。
  3. Picard の図を描く:$\lvert\langle b^\delta,u_i\rangle\rvert$ と $\sigma_i$ を並べる。係数が雑音の水準で横ばいになる番号が、使える情報の限界である。
  4. 方法を選ぶ:解の事前の情報に合わせる。滑らかさなら Tikhonov や打ち切り、疎さなら LASSO や 圧縮センシング。
  5. パラメータを選ぶ:$\|Kx_\alpha^\delta-b^\delta\|\le\tau\delta$($\tau>1$)となる最大の $\alpha$ をとる。これを 不一致原理 という。
  6. 確かめる:$\tau$、離散化、雑音の見積もりを少し変えても解が大きく変わらないことを見る。

例題

積分作用素と Picard の判定

$L^2(0,1)$ の $Vf(x):=\int_0^xf$ の逆問題は微分である。使う公式:thm-ip-picard。$a_k:=(k-\frac12)\pi$ とすると、特異系は
$$ \sigma_k=\frac1{a_k},\quad v_k=\sqrt2\cos(a_kx),\quad u_k=\sqrt2\sin(a_kx) $$
である。実際 $Vv_k=\sigma_ku_k$、$V^*g(x)=\int_x^1g$ で $V^*u_k=\sigma_kv_k$ である。
$b(x)=x$ のとき $\langle b,u_k\rangle=\sqrt2(-1)^{k-1}/a_k^2$ なので和は $\sum_k2/a_k^2< \infty$ で、答え $x^\dagger=\sum_k2(-1)^{k-1}\cos(a_kx)/a_k=1$ である。
$b\equiv1$ のとき $\langle b,u_k\rangle=\sqrt2/a_k$ で、和は $\sum_k2=\infty$ である。答え:$b\equiv1$ は $D(V^\dagger)$ に入らない。$Vf(0)=0$ なので定数 $1$ は $V$ の像にないことと合う。

数値微分:差分の幅が正則化になる

$f\in C^2$、$\lvert f''\rvert\le M$、$\lvert f^\delta-f\rvert\le\delta$ とする。使う公式:Taylor の定理。前進差分 $D_hf^\delta(x):=(f^\delta(x+h)-f^\delta(x))/h$ について
$$ \lvert D_hf^\delta(x)-f'(x)\rvert\le\frac{hM}2+\frac{2\delta}h $$
である。右辺の最小は $h=2\sqrt{\delta/M}$ で、答え 誤差の上界は $2\sqrt{\delta M}$ である。$M=1$ のとき次のようになる。$h$ を $\delta$ より先に小さくすると第 2 項が発散する。

$\delta$$10^{-2}$$10^{-4}$$10^{-6}$
最良の $h$$0.2$$0.02$$0.002$
誤差の上界$0.2$$0.02$$0.002$
逆向きの熱方程式

$u_t=u_{xx}$ を $(0,1)$ で $u(0,t)=u(1,t)=0$ のもとで考え、$u(\cdot,T)$ から $u_0:=u(\cdot,0)$ を求める。使う公式:thm-ip-picard。$u_0=\sum_kc_k\sqrt2\sin(k\pi x)$ なら $u(\cdot,t)$ の係数は $c_ke^{-k^2\pi^2t}$ なので、$\sigma_k=e^{-k^2\pi^2T}$ である(熱方程式)。$T=0.1$ のとき、答え 雑音の増幅率は次のとおりである。

$k$$1$$5$$10$
$1/\sigma_k$$2.68$$5.20\times10^{10}$$7.30\times10^{42}$

$\|u_0\|\le E$ を仮定すると、Hölder の不等式より $0< t\le T$ で
$$ \|u(\cdot,t)\|\le E^{1-t/T}\|u(\cdot,T)\|^{t/T} $$
である(対数凸性)。$t>0$ の時刻までは Hölder 型に戻せるが、$t=0$ では指数が $0$ になり、$\|u_0\|\le E$ だけでは安定性が得られない。

Gauss ぼかしの数値実験

$(0,1)$ の $n=200$ 個の格子点 $t_i=(i+\frac12)/n$ で、幅 $s=0.03$ の Gauss 核を行列 $K$ に離散化し、$x=\sin^2(\pi t)+\frac12e^{-((t-0.7)/0.05)^2}$ をぼかしたデータに相対 $10^{-3}$ の Gauss 雑音を加える。使う公式:thm-ip-filter。$K$ の条件数は約 $1.2\times10^{72}$ で(倍精度の計算では丸め誤差に埋もれて $10^{17}$ の程度と出る)、多倍長の計算で $K^{-1}$ を掛けただけの解の相対誤差は約 $7.6\times10^{67}$ である(条件数)。打ち切りの番号 $r$ を変えると次のようになる。

$r$$5$$10$$21$$25$$30$$40$$60$$80$
$\sigma_r$$0.90$$0.66$$0.16$$0.077$$0.025$$1.5\times10^{-3}$$6.2\times10^{-7}$$1.5\times10^{-11}$
残差 $/\delta$$75.7$$36.5$$1.09$$0.92$$0.88$$0.87$$0.81$$0.76$
相対誤差$0.11$$0.069$$0.0059$$0.0025$$0.0076$$0.051$$92$$5.4\times10^{6}$

答え:誤差は $r=25$ で最小の $0.0025$ で、不一致原理($\tau=1.1$)は $r=21$、誤差 $0.0059$ を選ぶ。$r=80$ では残差は小さいままで誤差だけが爆発している。Tikhonov の方法では $\alpha=10^{-8},10^{-6},10^{-4},10^{-2}$ に対し誤差は $0.56$、$0.061$、$0.0081$、$0.011$ である。
図: 左は Gauss ぼかしの特異値と、データの係数の大きさ。係数は雑音の水準で横ばいになる。右は打ち切りの番号と相対誤差で、谷の形になる。 図: 左は Gauss ぼかしの特異値と、データの係数の大きさ。係数は雑音の水準で横ばいになる。右は打ち切りの番号と相対誤差で、谷の形になる。

使える条件と反例

外す条件反例成り立たなくなること
階数が無限正則な行列逆は連続で、thm-ip-compact は起きない。ただし ex-ip-blur のように条件数は巨大になりうる
$A$ がコンパクト$\ell^2$ の恒等作用素逆は有界。なお $L^2(0,1)$ の掛け算 $f\mapsto xf$ はコンパクトでないが逆は非有界で、thm-ip-compact の逆は成り立たない
Picard の和が有限ex-ip-volterra の $b=1$$x^\dagger$ が存在せず、$\Vert R_\alpha b\Vert$ が発散する
$C_{\alpha(\delta)}\delta\to0$$\alpha$ を小さくしすぎる(ex-ip-blur の $r=80$)$\delta$ が小さくても誤差が大きい
$\alpha(\delta)\to0$$\alpha$ を固定する。$x^\dagger=v_1$ で Tikhonov の解は $\frac{\sigma_1^2}{\sigma_1^2+\alpha}v_1$偏りが残り $x^\dagger$ に収束しない
ソース条件$\sigma_i=1/i$、$\langle x^\dagger,v_i\rangle=1/(\sqrt i\log(i+1))$ の打ち切り偏りは $1/\sqrt{\log(1/\alpha)}$ の程度で、$\alpha$ のどんな正のべきより遅い。$\delta$ のべきの速さは得られない
上界 $E$$\sigma_i\to0$ で $x=(\delta/\sigma_i)v_i$$\Vert Ax\Vert=\delta$ で $\Vert x\Vert\to\infty$。$\omega$ が無限大になり、どの再構成も保証を与えない
$\nu\le1$(Tikhonov)$\nu=2$$\sigma^{2\nu}r_\alpha$ の上限は $\alpha^2$ でなく $\alpha$ の程度で、$\delta^{4/5}$ は得られない(飽和)

よくある誤り

誤り正しくはなぜ
残差が小さければ解も正しい不適切な問題では残差は誤差を測らないex-ip-blur の $r=80$
残差を $0$ に近づけるほどよい雑音まで合わせてしまう。残差は $\tau\delta$ の程度で止める不一致原理
離散化を細かくすれば精度が上がる細かくすると小さい特異値が増え、素朴な解は悪化する離散化も正則化の一種である
不安定なのは丸め誤差のせいだ問題そのものの性質で、精度を上げても残るthm-ip-compact
どんな解でも $\delta$ の 1 次で近づける順は事前の情報で決まり、$\delta^{2\nu/(2\nu+1)}$ を超えないthm-ip-lower
正則化で情報が増える増えるのは事前の仮定で、データにない成分は回復しないex-ip-heat

補足

非線形の逆問題

順写像が非線形なら、局所的に線形化して反復する(Gauss–Newton法など)か、罰則を入れて最小化する。方法の収束には $F$ の非線形性の条件が要る。Calderón問題 と 逆散乱法 は非線形の例である。

文献

線形の正則化理論の標準的な教科書は EHN96 である。正則化の創始は Tik63 に遡る。適切性の 3 条件は通常 Hadamard に帰されるが、第 3 条件が明確に述べられたのは後のことだという指摘が BB18 §2 にある。ソース条件と収束の順、条件なしでは収束が任意に遅くなりうることは BB18 §4.1 にある。thm-ip-filter と thm-ip-lower の証明はこの記事で直接書いた。

関連項目

参考文献

[2]
A. N. Tikhonov, Solution of incorrectly formulated problems and the regularization method, Soviet Math. Dokl. 4 (1963), 1035–1038, 1963
[3]
Martin Benning, Martin Burger, Modern regularization methods for inverse problems, Acta Numerica 27 (2018), 1–111; arXiv:1801.09922v1, 2018, §2、§4.1

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する