スパースモデリング
より具体的には、 l 0 {\displaystyle \ell _{0}} を l 1 {\displaystyle \ell _{1}} ノルムに変更すると、
min α ∈ R p λ ‖ α ‖ 1 + 1 2 ‖ x − D α ‖ 2 2 {\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\lambda \|\alpha \|_{1}+{\frac {1}{2}}\|x-D\alpha \|_{2}^{2}}
が得られ、これは基底追跡ノイズ除去(英語版)として知られている。同様に、マッチング追跡(英語版)も上記問題の解を近似するために使用することができ、誤差しきい値に達するまで、非ゼロの位置を1つずつ見つけていく。ここでも、BPとMPは、 D {\displaystyle D} の特性と解 k {\displaystyle k} のカーディナリティに応じて、ほぼ最適な解を導くことが理論的に保証されている。
もう一つの興味深い理論的結果は、 D {\displaystyle D} がユニタリ行列である場合に言及され、この仮定の下では、上述の問題( l 0 {\displaystyle \ell _{0}} または l 1 {\displaystyle \ell _{1}} を持つ)は、非線形縮退の形で閉形式解を認める。