逆問題, 非線形問題と凸性, 不動点定理, ハイブリッド最急降下法



１．逆問題とその解法の基本戦略

信号処理は、現実世界のデータに潜む真実を推定するための方法を探究する学問 であるから、その多くは、逆問題として定式化される。
例えば、線形写像 A:X→Y (X,Yはベクトル空間を表す)によって

y=A(x)+n (nは未知の雑音を表す)

が観測されるとき、yからxを推定する問題が最も簡単な線形逆問題である。 逆問題の解法は、主に、非線形関数の最小化問題に帰着されるのが普通である。 上記の問題は、関数

ψ(x)=‖A(x)-y‖^2 (x∈X)

を最小化する問題として定式化するのが一番素朴な考え方である。 ところが、ψの最小化問題の解は、一意に決まらないのが普通である (例えば、Aの行列表現がランク落ちしているような状況を想像していただきたい)。 我々は、たくさんの解の候補から一番尤もらしいものを選択する必要が生じるの である。

線形逆問題では、しばしば、ψを最小にする解の候補の中で、最小ノルムを 持つ唯一の『特別な候補 x*』が選択される。yからx*を対応付ける写像が、 有名な Moore-Penrose の一般逆に他ならない(簡単でしょ)。このことから、 特にAが正則であるとき、A^{-1}と一致することもわかる。
Moore-Penrose の一般逆の戦略を簡単にまとめておこう。まず、 ベクトル空間Xのすべての点が解の第１段階の候補として扱われていたことに注 意しよう。 第2段階では、関数ψの最小化問題の解の集合に候補が絞られた。更に、第２段階で 絞られた解の候補から第３段階でノルム最小となる解が絞られていることがわかる。
以上の解法の例から我々は、『"逆問題の困難さ"は、要するに解の候補 となる集合が大きすぎることであり、逆問題解法の基本戦略は、なるべく自然な条件 から順に条件を課していき、複数の段階で解の候補を選択していくプロセスを計算可能な 形で実現することにある。』 ことを学ぶことが出来る。ψの最小化問題の解集合に候補を絞ったり、更に、ノルム最小となる 唯一解に候補に絞ったのも、順次、自然と思われる条件を追加していく プロセスに他ならない。

さて、Moore-Penrose の一般化逆は、線形理論の枠組みで 極めて重要な到達点を与えてきた。実際に、Moore-Penrose の一般化逆は、 統計学をはじめ、データ解析、信号処理、制御理論など多くの分野の古典理論の 花形として大きな役割を果たしてきた。その成功の重要な理由の１つは、 Moore-Penrose の一般逆は、 有限回のステップで 計算可能であり(数値的な不安定性に関する問題はあるが...)、 その性質も詳細に調べられていることが挙げられる。
Moore-Penrose の一般逆の考え方を更に強力に進化させることはできないだろうか？ まず、考えられるのは上の第1段階の役割である。空間を選ぶという意味はあるが、 ここで解の候補をもっと絞っておくことはできないだろうか？ 例えば、画像信号を対象とする逆問題では、「画像信号は各ピクセルで非負値を とる」という最も自明な先験情報がある。 非負値をとる画像信号の集合は、ピクセルの数を次元 とするユークリッド空間X=R^N の特別な部分集合(K⊂Xと表す)であるから、 第1の候補をKの段階まで限定し、上の第2段階、第3段階をK上で実行する 戦略が自然な拡張と考えられる。ところが、 Kは、線形部分空間でないので(Kに所属する画像信号に-1を乗じるととたんに Kから飛び出してしまうことに注意せよ)、線形理論のエース(Moore-Penrose の一般逆の理論)は、とたんに適用不能となってしまう。 Kを導入するだけで、我々は、非線形の世界に 飛び込まなければならないのである。


２．非線形問題と凸性

研究者はいつまでも線形の問題に しがみついている訳にいかない。線形理論の枠組みの中に、 『現実世界のデータに潜む真実を推定する』目標への十分な勝算が見込め なくなってきたためである。研究者は、 線形理論という"静かな内海"から非線形理論という"大海原"に出て行くことを 余儀なくされたのである。外海には、どんな海があるだろう。 どこで網を投げるのがよいだろう。現在は正に大航海時代にたとえることが できる。我々は既にかなりよい海図を持っており、いろいろな 非線形の海があることがわかっている。多くの研究者は、各々、 自分が信じる海で網を投げているのである。ニューロンやファジイもカオスも 遺伝的アルゴリズムもみんな非線形理論の特別な海である。これらは、どちらか と言うと、 データ解析を源流としない海なのではないかと思う(多くの栄養が含まれており、 おいしい魚がたくさん棲んでいそうな気もするが...)。 例えば、(人工)ニューロンを基本的な構成要素とする 非線形理論は、脳科学や生物学を源流としていることは明白である。 確かに、人間の脳の機能は驚異的であり、これを工学的に実現するべく 研鑽を積み重ねれば、線形理論が達し得なかった高次の機能を実現することも 可能だろう。ところが、「脳科学や生物学の知見に倣った 道をたどることが、ベストな方向なのだろうか？」 「"何だか天下り的な感じがする。"のは、私だけなのだろうか？」 この疑問は、多くの研究者がどこかで考えたことがあるに違いない。 問題の定式化に関しては、線形理論のわりと自然な一般化が可能である。 そこまでは問題ないように見えるのだが、問題はその解法である。 問題の計算法を実現しなければならないのである。多くの非線形理論は、 結局のところ問題を非線形関数の最小化(あるいは最大化)問題に帰着している。 あとは、最適化理論で研究されている方法に任せる戦略をとっている。 また、ここで登場する非線形関数は、通常山脈のような形をしており、 理想的な最適解は、最も深い谷の底に佇んでいるのが普通である。 "解の計算"段階に至って最大の難関に遭遇してしまうのである。

線形理論のエース：Moore-Penrose の一般化逆問題では、こういう 状況は現れなかった。第2段階に現れた関数ψ(x)や第3段階に現れた 関数‖x‖^2も微分可能な凸関数であり、複数の谷が出現する余地は無かったのである。 複数の谷があるとどういうことが起るのか？最深でない谷に迷い込んだときには、 周りの様子がわからないので、とりあえず、迷い込んだ谷の最深部を目指すことに なるだろう。ところが、より深い谷があるかもしれないので、探索を打ち切るわけ にいかない。たとえ、今、探索している谷が最深の谷であっても、その事実を判定する 方法がなければ、懐疑的になり、新たな谷を探ることになるだろう。 大域的最適化理論の成果に頼ってもよいが、大域的最適解への収束を保証する アルゴリズムの計算コストは膨大となるのが普通である。小さなサイズの問題 でしか利用できない手法の用途は自然に限定され、淘汰されてしまう。

我々が注目する非線形問題の海は、凸(トツと読む)とよばれる海である。 この海の景色は、なつかしい内海に似ている。 実際、 この問題群では、登場する非線形関数は、お椀のような形をした凸関数に限定される。 お椀は、１つの谷しかないので安心して最小化することができるのである。 線形理論が、基本的に

f(λx+μy)=λf(x)+μf(y), ∀x,y∈X, ∀λ,μ∈(-∞,∞),

を満たす関数を扱っているのに対し、凸解析では、

f(λx+(1-λ)y)≦λf(x)+(1-λ)f(y), ∀x,y∈C⊂X, ∀λ∈[0,1],

を満たす関数も守備範囲としている。但し、Cは、ベクトル空間Xの部分集合で凹み (ヘコミ)のない集合を現す。凹み(ヘコミ)がないので、∀x,y∈Cに対し、これらを 結ぶ直線分は、Cにすっぽり含まれ、λx+(1-λ)y∈C が成り立つ。

(1)明らかに、凸解析は、線形理論よりも広い問題を含んでいることがわかる。

凸理論は、線形からいきなり、荒れ狂う大海に出航するといった命知らずの 理論では無いのである。一方、内海に似た景色故に、「この海には大した 魚はいないのではないか？」と考える御仁も多いと思う。これは、凸という海が、 個人の単純な推測で推し量れないほど深遠な世界を持っている事実に気づいていない だけだと思うのだが..

我々は驚くほど多くの重要な未解決問題が(内海に似た景色を もつ)凸という海に潜んでいることを 実感している。実際に問題の定式化を工夫することによって一見、 凸の海に入らない問題に ほぼ等価な問題が凸の海の中で発見され、本質的な問題解決に繋がることも多い。 例えば、谷が複数ある非線形問題の最小化問題に帰着される問題があるとき、 １つの谷の最深部をカバーする部分集合C⊂Xを持ってくることによって 凸の海の問題にすることもできる(Cは、問題の解に関する先験情報を 反映した集合を表す)。

我々は凸の海に網を投げ込んでいる。そのおかげで、我々は、長年、線形の海で名人達が 培ってきたすばらしい芸をお手本として凸で通用する芸の創設に邁進することが できる。定式化を工夫することによって現実の問題の本質を確実に 捉えることができ、また、一旦定式化されてしまえば、様々な強力な計算法が 存在する。その１つは、凸計画問題で開発されてきた数々の数理計画法 (例えば、90年代に登場した(内点法に基づく) Semi Definite Programming, 2nd Order Cone Programmingの名人芸は凸性の特長を 最大限に利用している)であり、また、主に凸解析の世界で建設されてきた (現代)不動点理論の多くの成果を計算法の開発に利用することができるのである。

３．不動点理論

写像 T:X→Xが与えられるとき、T(x*)=x* を満たす点 x*∈X をTの不動点という (一般にTは線形でも非線形でもよい)。既に数々の不動点定理が知られている。 不動点定理は、『T:X→Xが○○の性質を満たすとき、Xの中にTの 不動点が存在する』という類の定理の総称である。○○の性質の種類や考えている ベクトル空間Xによって様々なタイプの不動点定理が知られており、 既に多くの応用科学に不動点理論が積極的に応用され、大きな成功が見られている。 経済学では古くから「ブラウアーの不動点定理」や「角谷の不動点定理」が 均衡理論やゲーム理論の強力な道具となっていた。 不動点定理は、問題の解を写像の不動点として解釈することにより、 写像の不動点(=問題の解)が存在することを証明する常套手段として利用する ことができる。いくつかの不動点定理は、不動点の存在性 を主張しているだけでなく、不動点を逐次近似するアルゴリズムをも与えている。 バナッハによる「縮小写像の不動点定理」は、その１つの例である。 写像 T:X→Xが

(0<∃k<1, ∀x,y∈X) ‖T(x)-T(y)‖≦k‖x-y‖

を満足するとき、T は縮小写像であるという。 特にXがバナッハ空間(完備なノルム空間)であるとき、「縮小写像の不動点定理」は、 Tが、Xの中に唯一の不動点 x* を持つことを保証する。更に、 ∀x_{0}∈X に対して、

lim_n→∞ T^{n}(x_{0})=x*

を満足する。 これは、不動点を逐次近似する具体的なアルゴリズムとなっている。 「縮小写像の不動点定理」は、不動点の存在性を保証しているだけでなく その計算法をも提供しているのである。 このアルゴリズムは実際に多くの方程式の数値解法の原理となってきた。 身近な例では、線形方程式の解の 逐次近似法(反復法と呼ばれる方法群)が挙げられる。ヤコビ法やSOR法の収束定理は、 基本的に「縮小写像の不動点定理」を拠り所としている。また、非線形方程式の零点を 逐次近似するニュートン(-ラプソン)法も「縮小写像の不動点定理」を拠り所としている のである。「方程式の解」を「写像の不動点」と同一視することによって、 純粋数学の土壌で生まれた「縮小写像の不動点定理」は、 応用科学の多くの数値解法の最も重要な指導原理の１つとなっているのである。

４．ハイブリッド最急降下法

「問題の解」と「非線形写像の不動点」とを同一視する考え方は、 はじめに述べた逆問題を解決していく上でも強力な戦略となるに違いない。

以下、逆問題の話に立ち戻ろう。目標は、線形理論という内海で エースとしての地位を誇った「Moore-Penrose の一般逆」 の理論を拡張することによって、第1のステップで K⊂X の利用を可能にする 計算法を開発することである。

まず、Kを閉凸集合に限定することにする。 幸い、非負値をとる画像信号の集合をはじめ多くの先験情報は凸集合として 表現できる。また、複数の閉凸集合が先験情報として与えられる場合にも、 その共通部分集合(すべての先験情報を同時に満たす制約集合)も閉凸集合となる。

我々のとった戦略は、以下の３つの方針である。

(A) Xを実ヒルベルト空間に限定した。

(B) 第2段階で Kの上で関数ψの最小化問題の解の集合を工夫して構成された 非拡大写像 T:X→X のすべての不動点の集合 Fix(T)として特徴付けた。

(0<∃k≦1, ∀x,y∈X) ‖T(x)-T(y)‖≦k‖x-y‖

を満たすとき、T:X→Xは非拡大写像であるという。縮小写像とは、 定義上ほんの僅かの違いしかないように見えるが、k=1を許すことによって Tは、非可算無限個の不動点をとることができる。

(C) 非拡大写像の不動点集合Fix(T)上で実数値関数 Φ:X→R を最小化を可能にする アルゴリズム(ハイブリッド最急降下法)を開発する。

詳しくは、以下の論文を参照されたい。凸解析や不動点理論の考え方が、 現代信号処理の諸問題を解決していく上で極めて有効であることを実感して いただけると思う。

[1] 山田 功 ``凸射影アルゴリズムの考え方とハイブリッド最急降下法,'' 電子情報通信学会誌, vol.83, no.8, pp.616-623, 2000.

[2] I.Yamada, ``The hybrid steepest descent method for the variational inequality problem over the intersection of fixed point sets of nonexpansive mappings,'' pp. 473-504, in Inherently Parallel Algorithm for Feasibility and Optimization and Their Applications, (D. Butnariu, Y. Censor, and S. Reich, Eds.) Elsevier, 2001.
http://www.elsevier.nl/locate/inca/622148

[3] I.Yamada, N.Ogura and N.Shirakawa, ``A numerically robust hybrid steepest descent method for the convexly constrained generalized inverse problems,'' in Inverse Problems, Image Analysis, and Medical Imaging, (Z.Nashed and O.Scherzer, Eds.) Contemporary Mathematics, 313, American Mathematical Society, pp. 269-305, 2002.
http://www.ams.org/bookstore?fn=20&arg1=conmseries&item=CONM-313

[4] K. Slavakis, I. Yamada and K. Sakaniwa, "Computation of symmetric positive definite Toeplitz matrices by the Hybrid Steepest Descent Method," Signal Processing, 83, pp.1135--1140, 2003.
http://www.sciencedirect.com/science/journal/01651684

[5] H. K. Xu and T. H. Kim, "Convergence of hybrid steepest descent methods for variational inequalities,"Journal of Optimization Theory and Applications, Vol.119, no.1, pp.185--201, 2003. http://www.kluweronline.com/issn/0022-3239

[6] C. Byrne, "A unified treatment of some iterative algorithms in signal processing and image reconstruction," Inverse Problems, Vol.20, no.1, pp. 103--120, 2004. http://www.iop.org/EJ/toc/0266-5611/20/1


2004年2月23日 山田 功

坂庭・山田研のホームページへ戻る