論文の概要: Improved Support Recovery in Universal One-bit Compressed Sensing
- arxiv url: http://arxiv.org/abs/2210.16657v1
- Date: Sat, 29 Oct 2022 17:43:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-01 16:52:53.877911
- Title: Improved Support Recovery in Universal One-bit Compressed Sensing
- Title（参考訳）: ユニバーサル1ビット圧縮センシングにおけるサポート回復の改善
- Authors: Namiko Matsumoto, Arya Mazumdar, Soumyabrata Pal
- Abstract要約: 1ビット圧縮(1bCS)は、極端に量子化された信号取得法である。
本論文の焦点は、しばしば近似的な信号回復を促進するサポートリカバリである。
まず, $tildeO(k/epsilon), $tildeO(maxk/epsilon,k3/2), $tildeO(maxk/epsilon,k3/2)$測定を行う。
- 参考スコア（独自算出の注目度）: 37.5349071806395
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: One-bit compressed sensing (1bCS) is an extremely quantized signal
acquisition method that has been proposed and studied rigorously in the past
decade. In 1bCS, linear samples of a high dimensional signal are quantized to
only one bit per sample (sign of the measurement). Assuming the original signal
vector to be sparse, existing results in 1bCS either aim to find the support of
the vector, or approximate the signal allowing a small error. The focus of this
paper is support recovery, which often also computationally facilitate
approximate signal recovery. A {\em universal} measurement matrix for 1bCS
refers to one set of measurements that work for all sparse signals. With
universality, it is known that $\tilde{\Theta}(k^2)$ 1bCS measurements are
necessary and sufficient for support recovery (where $k$ denotes the sparsity).
To improve the dependence on sparsity from quadratic to linear, in this work we
propose approximate support recovery (allowing $\epsilon>0$ proportion of
errors), and superset recovery (allowing $\epsilon$ proportion of false
positives). We show that the first type of recovery is possible with
$\tilde{O}(k/\epsilon)$ measurements, while the later type of recovery, more
challenging, is possible with $\tilde{O}(\max\{k/\epsilon,k^{3/2}\})$
measurements. We also show that in both cases $\Omega(k/\epsilon)$ measurements
would be necessary for universal recovery.
Improved results are possible if we consider universal recovery within a
restricted class of signals, such as rational signals, or signals with bounded
dynamic range. In both cases superset recovery is possible with only
$\tilde{O}(k/\epsilon)$ measurements. Other results on universal but
approximate support recovery are also provided in this paper. All of our main
recovery algorithms are simple and polynomial-time.
- Abstract（参考訳）: 1ビット圧縮センシング(1bCS)は、過去10年間に提案され、厳密に研究されてきた非常に量子化された信号取得手法である。
1bCSでは、高次元信号の線形サンプルを1サンプルあたり1ビットに量子化する(測定の符号)。
元の信号ベクトルがスパースであると仮定すると、1bCSの既存の結果はベクターのサポートを見つけること、あるいは小さなエラーを許容するシグナルを近似する。
本稿の焦点は,信号の近似回復を計算的に促進する支援リカバリである。
1bCSの「普遍的」測定行列は、すべてのスパース信号に作用する1つの測定セットを指す。
普遍性では、$\tilde{\Theta}(k^2)$ 1bCS測定はサポート回復に十分である($k$はスパーシティを表す)ことが知られている。
2次から線形への間隔依存性を改善するため、この研究では、近似的なサポート回復(エラーの比率が$\epsilon>0$)とスーパーセット回復(偽陽性の比率が$\epsilon$%)を提案する。
最初のタイプのリカバリは$\tilde{O}(k/\epsilon)$測定で可能であるが、後のタイプのリカバリは$\tilde{O}(\max\{k/\epsilon,k^{3/2}\})$測定で可能である。
また、どちらの場合も、万能回復には$\Omega(k/\epsilon)$測定が必要であることも示している。
有理信号や有界ダイナミックレンジの信号など、制限された信号のクラス内での普遍的な回復を考えると、より良い結果が得られる。
どちらの場合も、$\tilde{O}(k/\epsilon)$測定だけで超集合回復が可能である。
本論文では, 普遍的だが近似的な支援回復に関する他の結果も提示する。
主要なリカバリアルゴリズムはすべて単純で多項式時間です。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Robust 1-bit Compressed Sensing with Iterative Hard Thresholding [18.05573480691047]
1ビット圧縮センシングでは、$k$スパース単位ベクトル$xin Sn-1$を$epsilon$エラー内で推定する。
本稿では,一部の計測値のフリップが可能な雑音バージョンを,潜在的に敵によって検討する。
BIHTallyは$tildeO(epsilon+tau)$エラーで$x$と見積もる。
論文 参考訳（メタデータ） (2023-10-12T03:41:32Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Binary Iterative Hard Thresholding Converges with Optimal Number of
Measurements for 1-Bit Compressed Sensing [29.570141048369297]
BIHT アルゴリズムは $tildeO (frackepsilon) 測定でのみ収束することを示す。
これは非問題に対する正しい解に収束する線形降下アルゴリズムの例でもある。
論文 参考訳（メタデータ） (2022-07-07T16:52:50Z) - Polynomial-time sparse measure recovery [2.0951285993543642]
慎重に設計したモーメントから最初のポリ時間回復法を提案する。
この方法は、2次元入力、有限幅、ゼロワンアクティベーションを備えた植込み2層ニューラルネットワークの回復に依存する。
論文 参考訳（メタデータ） (2022-04-16T22:12:55Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Support Recovery in Universal One-bit Compressed Sensing [54.26691979520478]
1ビット圧縮センシング (1bCS) は極端量子化信号取得法である。
少数の偽陽性で支持を普遍的に回復することは可能であることを示す。
論文 参考訳（メタデータ） (2021-07-19T18:10:51Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳（メタデータ） (2021-06-29T12:49:54Z) - Hadamard Wirtinger Flow for Sparse Phase Retrieval [24.17778927729799]
我々は、ノイズのない等級のみの測定結果から、$n$-dimensional $k$-sparse信号を再構成する問題を考察する。
この問題を非正規化経験的リスク最小化タスクとして定式化し、アダマールパラメトリゼーションを用いた勾配降下のサンプル複雑性性能について検討した。
収束時のHWFの性能を数値的に検討し、正規化の明示的な形式や$k$の知識を必要としないが、HWFは信号空間に適応し、既存の勾配法よりも少ない測定値でスパース信号を再構成することを示した。
論文 参考訳（メタデータ） (2020-06-01T16:41:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。