基礎追求

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

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

ここで、xはN次元の解ベクトル（信号）、yは観測値（測定値）のM次元ベクトル、 A はM  ×  N変換行列（通常は測定行列）であり、 M  <  Nです。

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

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

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

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

${\displaystyle {\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}}}$

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

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

${\displaystyle {\begin{aligned}&{\text{ベクトルを見つける}}&&(\mathbf {x^{+}} ,\mathbf {x^{-}} )\\&{\text{ }}&&\mathbf {1} ^{T}\mathbf {x^{+}} +\mathbf {1} ^{T}\mathbf {x^{-}} \\&{\text{対象}}&&A\mathbf {x^{+}} -A\mathbf {x^{-}} =\mathbf {y} \\&{\text{and}}&&\ mathbf {x^{+}} ,\mathbf {x^{-}} \geq \mathbf {0} .\end{aligned}}}$

• 基礎追跡ノイズ除去
• 圧縮センシング
• 周波数スペクトル
• グループテスト
• ラッソ（統計）
• 最小二乗スペクトル解析
• マッチング追求
• スパース近似

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

• シャオビン・チェン、デイビッド・ドノホ：基礎追求
• Terence Tao : 圧縮センシング。Mahler 講演シリーズ (スライド)