根拠追求

基底追求は、次のような数学的最適化問題である。

\min _{x}\|x\|_{1}\quad {\text{subject to}}\quad y=Ax,

ここで、xはN次元の解ベクトル（信号）、yはM次元の観測値ベクトル（測定）、AはM × Nの_変換行列（通常は測定行列）、M < Nである。L 0ノルムを最小化しようとする基底追求法はNP困難である。^[1]

これは通常、厳密に満たされなければならないy = Axの不確定な線形方程式システムがあり、L _{1 の意味で}最もスパースな解が求められる場合に適用されます。

Axとyの正確な等価性と引き換えにxをよりスパースにすることが望ましい場合は、基底追求ノイズ除去が推奨されます。

基底追求問題は多項式時間で線形計画問題に変換することができ、その逆も同様であり、2つのタイプの問題は多項式的に等価である。^[2]

線形計画法との同値性

基底追求問題は、まず次のことに注意することで線形計画問題に変換できる。

{\begin{aligned}\|x\|_{1}&=|x_{1}|+|x_{2}|+\ldots +|x_{n}|\\&=(x_{1}^{+}+x_{1}^{-})+(x_{2}^{+}+x_{2}^{-})+\ldots +(x_{n}^{+}+x_{n}^{-})\end{aligned}}

ここでです。この構成はという制約から派生しており、の値はがゼロより大きいか小さいかに応じて、それぞれまたはに格納されます。およびの値の範囲はこの制約を満たす可能性がありますが、単体法を用いるソルバーはまたはの一方または両方がゼロとなる解を求め、結果としてという関係が成立します。 $x_{i}^{+},x_{i}^{-}\geq 0$ $x_{i}=x_{i}^{+}-x_{i}^{-}$ $|x_{i}|$ $x_{i}^{+}$ $x_{i}^{-}$ $x_{i}$ $x_{i}^{+}$ $x_{i}^{-}$ $x_{i}^{+}$ $x_{i}^{-}$ $|x_{i}|=(x_{i}^{+}+x_{i}^{-})$

この展開から、問題は次のように標準的な形に書き直すことができる: ^[2]

{\begin{aligned}&{\text{Find a vector}}&&(\mathbf {x^{+}} ,\mathbf {x^{-}} )\\&{\text{that minimizes}}&&\mathbf {1} ^{T}\mathbf {x^{+}} +\mathbf {1} ^{T}\mathbf {x^{-}} \\&{\text{subject to}}&&A\mathbf {x^{+}} -A\mathbf {x^{-}} =\mathbf {y} \\&{\text{and}}&&\mathbf {x^{+}} ,\mathbf {x^{-}} \geq \mathbf {0} .\end{aligned}}

参照

注記

^ Natarajan, BK (1995年4月). 「線形システムのスパース近似解」 . SIAM Journal on Computing . 24 (2): 227– 234. doi :10.1137/S0097539792240406. ISSN 0097-5397.
^ ab AM Tillmann線形計画法と基底追求の同値性、PAMM（応用数学および力学の議事録）第15巻、2015年、pp. 735-738、DOI: 10.1002/PAMM.201510351

参考文献と参考文献

スティーブン・ボイド、リーヴェン・ヴァンデンバーグ著：凸最適化、ケンブリッジ大学出版局、2004年、ISBN 9780521833783、337～337ページ
Simon Foucart、Holger Rauhut著『圧縮センシングへの数学的入門』Springer、2013年、 ISBN 9780817649487、77～110ページ

外部リンク

シャオビン・チェン、デイヴィッド・ドノホ：基礎追求
テレンス・タオ：圧縮センシング。マーラー講演シリーズ（スライド）

[1] Natarajan, BK (1995年4月). 「線形システムのスパース近似解」 . SIAM Journal on Computing . 24 (2): 227– 234. doi :10.1137/S0097539792240406. ISSN 0097-5397.

[Tillmann-2] AM Tillmann線形計画法と基底追求の同値性、PAMM（応用数学および力学の議事録）第15巻、2015年、pp. 735-738、DOI: 10.1002/PAMM.201510351