スパースモデリング
上記の問題は確かにNP困難であるが、近似アルゴリズムを用いてその解を見つけることができる。そのような選択肢の一つは、 l 0 {\displaystyle \ell _{0}} の代わりに l 1 {\displaystyle \ell _{1}} ノルムを用いて問題を凸緩和 (en:英語版) することで得られる。ここで、 ‖ α ‖ 1 {\displaystyle \|\alpha \|_{1}} は α {\displaystyle \alpha } 内の要素の絶対値を単純に合計したものである。これは基底追跡(英語版)(basis pursuit、BP)アルゴリズムとして知られており、任意の線型計画法ソルバーを用いて処理することができる。もう一つの近似法は、マッチング追跡(英語版)(matching pursuit、MP)のような貪欲法で、非ゼロの位置を一度に一つずつ見つけてゆくものである。
驚くべきことに、 D {\displaystyle D} に関する穏やかな条件(Spark (数学)(英語版)、相互コヒーレンス(英語版)または制限付等長性(英語版))と、解のスパース性のレベル k {\displaystyle k} の下で、スパース表現問題は一意の解を持つことが示され、BPとMPはそれを完全に見つけることが保証されている。