群衆内アルゴリズム

インクラウドアルゴリズムは、基底追求ノイズ除去を迅速に解く数値手法であり、大規模で疎な問題に対する他のどのアルゴリズムよりも高速です。^[1]このアルゴリズムはアクティブセット法であり、グローバル基底追求ノイズ除去のサブ問題を反復的に最小化します。

${\displaystyle \min_{x}{\frac{1}{2}}\|y-Ax\|_{2}^{2}+\lambda\|x\|_{1}.}$

ここで、は観測信号、は回復されるスパース信号、での期待信号、 は信号の忠実度と単純さをトレードオフする正則化パラメータです。ここで単純さは、解 のスパース性を使用して測定され、その-ノルムで測定されます。このコンテキストでは、非ゼロとなる係数はごくわずかであるため、アクティブ セット戦略は非常に効率的です。したがって、係数を識別できれば、これらの係数に制限して問題を解くことで、解が得られます。ここで、特徴は、現在の推定値における勾配の絶対値に基づいて貪欲に選択されます。 ${\displaystyle y}$${\displaystyle x}$${\displaystyle 斧}$${\displaystyle x}$${\displaystyle \lambda}$${\displaystyle x}$${\displaystyle \ell_{1}}$

基底追求ノイズ除去のための他のアクティブセット法としては、アクティブセットの選択が問題の双対性ギャップを使用して実行されるBLITZ ^{[2]や、特徴がその符号の推定に基づいて含められる特徴符号検索[3]}などがあります。

内容は次のとおりです。

1. 0と宣言すると、説明できない残差${\displaystyle x}$${\displaystyle r=y}$
2. アクティブセットを空セットとして宣言し、その補集合（非アクティブセット）として宣言する${\displaystyle I}$${\displaystyle I^{c}}$
3. 各コンポーネントの有用性を計算する${\displaystyle u_{j}=|\langle rA_{j}\rangle |}$${\displaystyle I^{c}}$
4. オンの場合、いいえ、終了${\displaystyle I^{c}}$${\displaystyle u_{j}>\lambda }$
5. それ以外の場合は、有用性に基づいてコンポーネントを追加します${\displaystyle L\approx 25}$${\displaystyle I}$
6. 正確に 上で基底追求ノイズ除去を解き、値が正確に 0 になる の成分をすべて捨てます。この問題は稠密なので、このサブ問題には二次計画法の手法が非常に適しています。${\displaystyle I}$${\displaystyle I}$
7. 更新- の外側のすべての要素が0であるため、nbはサブ問題で計算できます。${\displaystyle r=y-Ax}$${\displaystyle I}$
8. ステップ3に進みます。

インクラウドアルゴリズムはグローバル検索を実行するたびにアクティブセットにコンポーネントを追加するため、この検索が計算コストが高い場合、最良の代替アルゴリズムよりも 1 倍高速になる可能性があります。定理^[1]は、インクラウドアルゴリズムの一度に多数回実行される性質にもかかわらず、グローバル最適解に到達することを保証します。 ${\displaystyle L}$${\displaystyle L}$