スパースモデリング
を解く。ここで ‖ α ‖ 0 = # { i : α i ≠ 0 , i = 1 , ... , p } {\displaystyle \|\alpha \|_{0}=\#\{i:\alpha _{i}\neq 0,\,i=1,\ldots ,p\}} は l 0 {\displaystyle \ell _{0}} 半ノルムで、 α {\displaystyle \alpha } の非ゼロ成分の数を数える。この問題は、組合せ最適化におけるNP完全な部分集合選択問題への還元を伴うNP困難であることが知られている。
α {\displaystyle \alpha } のスパース性とは、その中で少数の成分( k ≪ m < p {\displaystyle k\ll m<p} )だけが非ゼロであることを意味する。このようなスパース分解(sparse decomposition)を行う潜在的な動機は、 x {\displaystyle x} を D {\displaystyle D} のできるだけ少ない列(アトムとも呼ばれる)の線形結合として、可能な限り単純に説明したいという欲求にある。このように、信号 x {\displaystyle x} は、 D {\displaystyle D} から取り出したいくつかの基本要素(アトム)から構成される分子と見なすことができる。