少し数学の話をしましょう。或る条件を満足する最小値が存在する、という主張が通った場合、数学の世界では最小値を $A$ とおいて議論を進めることが多いです。「存在すること」が重要であるという数学特有の価値観ですね。具体的に最小の数 $A$ を使う場合でも、具体的な $A$ は求めずに $B < A < C$ というような $B,C$ を見つけることの方が容易であると考えて議論を進めます。

数学とアルゴリズムは密接に関連しますが、上記の特徴に関しては全く違った議論の進め方が要求されます。「存在すること」はアルゴリズム的には安心感へ繋がるかもしれないですが、実質的には何の意味もありません。「存在」ではなく「具体的なもの」が要求されます。

ブラインド-デコンボリューションの計算量が大きいことの原因は上の話と同じです。

ブラインド-デコンボリューションは、解が一意的に決まらない不良設定問題です。この状況で、或る条件を満たす解が存在するということは心強い安心感になります。しかし、その解を探すためにはトライアンドエラーの実験をしなければならない。これによりブラインド-デコンボリューションの計算量は肥大化します。

したがって計算量を圧縮するためには、或る条件を満たす解を、「近似的に」ではなく「解析的に」求めておく必要があります。言葉にすると簡単そうに見えるかもしれませんが、実際には解が確かに存在して解析的に求めることができるであろう「或る条件」とやらを上手いこと探し出し、解析的な解を手計算で求める必要があります。尚且つ、ここでの「或る条件」は存在するのか否か保証されていません。

実は極めてリスキーで難しい問題です。このように考えると、ブラインド-デコンボリューションはまだまだ研究の余地があると思います。(written by J.Nishigata)

その他25- ブラインド-デコンボリューションの計算量圧縮