圧縮センシングにおけるデノイズ保証付き、部分的に決定論的なサンプリング

要旨: サンプリングベクトルがユニタリ行列の行から選ばれる場合の圧縮センシングを研究する。文献においては、これらのサンプリングベクトルは通常ランダムに選ばれる。ランダム性の利用は、この分野において主要な実証的および理論的進展をもたらしてきた。しかし実際には、重要なサンプリングベクトルが特定の場合にしばしば存在し、その場合実務者は理論から逸脱して、そのような行を決定論的にサンプルする。本研究では、ベルヌーイ・セレクタに対する最適化されたサンプリング手法を導出し、それが行のランダム選択と決定論的選択を自然に組み合わせることで、どの行を決定論的にサンプルすべきかを厳密に決定する。このサンプリング手法は、理論的結果と数値実験によって示すように、置換ありおよび置換なしのサンプリング手法と比較して、生成的事前分布および疎な事前分布の両方における画像圧縮センシングで測定可能な改善をもたらす。さらに、我々の理論的保証は、先行研究と比べて改善されたサンプル複雑性の上界を備えており、この設定における新規なデノイズ（ノイズ除去）の保証も提供する。