ノイズのある圧縮サンプリングに関するシャノン理論的限界

本論文では、ノイズが存在する中で、圧縮サンプルからL個の非ゼロ係数を持つC Mのスパース信号を復元するために必要な測定数を研究します。信号の支持を正確に復元することを含むいくつかの異なる復元基準を考慮し、文献で以前に論じられていたものだけでなく、信号の支持の大部分を復元するための新しい基準や信号のエネルギーの大部分を復元する基準も考慮します。これらの復元基準に対して、LがMの線型関数として線形に増加する場合、信号復元に必要かつ十分な測定数はO(L)（Lの漸近線形倍数）であることを証明します。これは、O(L log(M - L))の測定が必要な特定の復元アルゴリズムの変種に主に焦点を当てた既存の文献に改善をもたらします。対照的に、私たちの証明方法の実装はより高い複雑さを持つことになります。また、O(L log(M - L))の測定がサブリニア領域（L - o(M)）で必要であることも示します。私たちの十分性の証明には、共同的典型性に基づくシャノン理論的デコーダーを導入し、ランダム変数の比較が必要な以前の情報理論的研究とは異なり、エラーイベントが単一のランダム変数に基づいて定義できるようにします。また、ランダムに選択されたガウス行列が高い確率で十分であることを示すエラー境界に対する集中結果も証明します。必要性の証明に関しては、チャネル符号化とレート歪み理論の結果に依存します。