【圧縮センシング】OMPアルゴリズムにおける観測ベクトルの長さとスパースベクトルの復元失敗率の関係 - Qiita

0. はじめに 圧縮センシングは、観測ベクトルをy、あるスパースなベクトルをxとし、y = Axとモデリングできる場合に、xがスパースであることを条件にyからxを復元する技術です。 圧縮センシングを利用するときの注意点は、観測ベクトルyの長さが十分でないと、xの復元に必要な情報を得ることができずに復元に失敗することです。 観測ベクトルyの長さ(M)に関しては、以下のように理論的な目安（復元成功の理論閾値）が示されています[1]。 ここで、Nはベクトルxの長さ、Sはxの非ゼロ成分の数、Cは固定値です。 復元成功の理論閾値は示されていますが、行列Aの構成と圧縮センシングのアルゴリズムによって、復元に失敗する場合があります。 本稿では、圧縮センシングのアルゴリズムの一つである、Orthogonal Matching Pursuit (OMP) を対象に、復元に失敗する確率をシミュレーションで確認