1．は　じ　め　に

　スパースモデリングは，データの背後に潜むスパース性を陽に考慮してモデル化を行う方法である．この方法は，大量のデータから知見を引き出すビッグデータ分析とは異なり，少ないデータしか得られない状況でデータ発生源の特性を調べるというような場面で威力を発揮する．データの取得に膨大な時間や費用がかかるような問題，例えばブラックホールの撮像⁽¹⁾や医療MRI（Magnetic Resonance Imaging）⁽²⁾などで，スパースモデリングの成功事例が報告されている．このスパースモデリングの技術は，圧縮センシング⁽³⁾やスパース表現⁽⁴⁾とも呼ばれる．上記の応用のほか，データ分析⁽⁵⁾や画像・信号処理⁽⁶⁾，情報通信⁽⁷⁾，システム制御^(8),(9)など様々な分野へ応用され，大きく注目されている．

　スパースモデリングでは，ベクトルのスパース性をノルム（ベクトルの非ゼロ要素の数）で測り，ノルムを最小化するという定式化を行う．しかし，ノルムを含む最適化問題は組合せ最適化問題となり，更にNP困難であることが知られている⁽¹⁰⁾．よって，サイズの大きい最適化問題を直接解くことは極めて難しい．スパースモデリングでは，主に以下の二つのアイデアによってこの問題に対応する．

・ノルムをノルムで近似して解く．

・貪欲法アルゴリズムにより局所的に解く．

　第1の方法は，ノルムが凸であるため，凸最適化問題に帰着でき，内点法などの高速アルゴリズムが利用できる⁽¹¹⁾．また，ノルムで近似して求めた解と元の最適解の関係についても，多くの研究がある（例えば文献(12)）．ただし，それらが等価であるかどうかをチェックすること自体がNP困難であるため⁽¹³⁾，現実問題として，で求めた解，例えば画像処理結果を人間の目で見て，その良し悪しを判断するというようなことが行われる．

　第2の貪欲法は，組合せ最適化問題を解くための強力な手法であるが，大域的最適解が得られるという保証はない．本稿でも説明するが，例えば最適化により求めた解を初期値として，より良い解を見つけるために，貪欲法アルゴリズムを使うこともよく行われる．