これはメモ。
- 次元が上がると、増えた次元に"逃げて"しまうこと。例えば、無限次元の線形空間では有界閉集合なのにコンパクトでないものがある。
- 密度推定をしようにも、スカスカで近傍に点が全然いないこと。
- 点から多面体への最短距離を計算するときのオーダが爆発すること。
- 単位球と単位立方体の体積比がどんどん0に近づくこと。
など。
我々が知っているアルゴリズムのほとんどが、ごく低次元でしか実用的でないのは驚くべきことである。
「次元の呪い」とは直接関係ないけれど、逐次的に探索を行うことで、実質的な探索空間の次元を下げる手法はしばしば用いられる。いわゆる"半全列挙"とか。結晶学の世界では、分子置換法における探索が該当例。すなわち、モデルを剛体フィッティングしようとすると並進関数3自由度・回転関数3自由度の合わせて6次元探索が必要となるが、構造因子の強度は位相情報が失われていることを逆手に取って、まず回転関数のフィッティングを行い、しかる後に並進関数のフィッティングを行う。
