論文の概要: Binary Iterative Hard Thresholding Converges with Optimal Number of
Measurements for 1-Bit Compressed Sensing
- arxiv url: http://arxiv.org/abs/2207.03427v1
- Date: Thu, 7 Jul 2022 16:52:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-08 14:53:26.698910
- Title: Binary Iterative Hard Thresholding Converges with Optimal Number of
Measurements for 1-Bit Compressed Sensing
- Title（参考訳）: 1ビット圧縮センシングのための最適測定数付き2成分繰り返しハード閾値収束
- Authors: Namiko Matsumoto, Arya Mazumdar
- Abstract要約: BIHT アルゴリズムは $tildeO (frackepsilon) 測定でのみ収束することを示す。
これは非問題に対する正しい解に収束する線形降下アルゴリズムの例でもある。
- 参考スコア（独自算出の注目度）: 29.570141048369297
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Compressed sensing has been a very successful high-dimensional signal
acquisition and recovery technique that relies on linear operations. However,
the actual measurements of signals have to be quantized before storing or
processing. 1(One)-bit compressed sensing is a heavily quantized version of
compressed sensing, where each linear measurement of a signal is reduced to
just one bit: the sign of the measurement. Once enough of such measurements are
collected, the recovery problem in 1-bit compressed sensing aims to find the
original signal with as much accuracy as possible. The recovery problem is
related to the traditional "halfspace-learning" problem in learning theory.
For recovery of sparse vectors, a popular reconstruction method from 1-bit
measurements is the binary iterative hard thresholding (BIHT) algorithm. The
algorithm is a simple projected sub-gradient descent method, and is known to
converge well empirically, despite the nonconvexity of the problem. The
convergence property of BIHT was not theoretically justified, except with an
exorbitantly large number of measurements (i.e., a number of measurement
greater than $\max\{k^{10}, 24^{48}, k^{3.5}/\epsilon\}$, where $k$ is the
sparsity, $\epsilon$ denotes the approximation error, and even this expression
hides other factors). In this paper we show that the BIHT algorithm converges
with only $\tilde{O}(\frac{k}{\epsilon})$ measurements. Note that, this
dependence on $k$ and $\epsilon$ is optimal for any recovery method in 1-bit
compressed sensing. With this result, to the best of our knowledge, BIHT is the
only practical and efficient (polynomial time) algorithm that requires the
optimal number of measurements in all parameters (both $k$ and $\epsilon$).
This is also an example of a gradient descent algorithm converging to the
correct solution for a nonconvex problem, under suitable structural conditions.
- Abstract（参考訳）: 圧縮センシングは線形演算に依存する高次元信号取得・回復技術として非常に成功した。
しかし、実際の信号の測定は保存または処理前に量子化する必要がある。
1(1)ビット圧縮センシングは、圧縮センシングの重定量化バージョンであり、信号の各線形測定は、測定の符号である1ビットに縮小される。
このような測定を十分に集めると、1ビット圧縮センシングにおけるリカバリ問題は、可能な限り精度で元の信号を見つけることを目的としている。
回復問題は、学習理論における伝統的な「半空間学習」問題に関連している。
スパースベクトルの回復のために、1ビットの計測から一般的な再構成手法はbinary iterative hard thresholding (biht) アルゴリズムである。
このアルゴリズムは単純な射影下勾配降下法であり、問題の非凸性にもかかわらず経験的に収束することが知られている。
BIHTの収束性は理論上は正当化されなかったが、非常に多くの測定値(例えば、$\max\{k^{10}, 24^{48}, k^{3.5}/\epsilon\}$、$k$はスパーシティ、$\epsilon$は近似誤差を示し、この式でさえ他の因子を隠蔽する)を除いては、理論上は正当化されなかった。
本稿では,BIHT アルゴリズムが $\tilde{O}(\frac{k}{\epsilon})$ で収束することを示す。
この$k$と$\epsilon$への依存は、1ビット圧縮センシングにおける任意の回復法に最適である。
この結果、我々の知る限りでは、bihtはすべてのパラメータ($k$と$\epsilon$の両方)で最適な測定数を必要とする唯一の実用的で効率的な(多項時間)アルゴリズムである。
これはまた、適切な構造条件下で、非凸問題に対する正しい解に収束する勾配降下アルゴリズムの例である。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization [48.84672493756553]
我々は,1ステップあたり$Obig(slogfrac dsbig)$クエリのみを使用する勾配のクエリ効率と精度の高い推定器を提案する。
Indyk-Price-Woodruff (IPW) アルゴリズムを線形測定から非線形関数への圧縮センシングにおいて一般化した。
論文 参考訳（メタデータ） (2024-05-27T03:52:53Z) - 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) - Improved Support Recovery in Universal One-bit Compressed Sensing [37.5349071806395]
1ビット圧縮(1bCS)は、極端に量子化された信号取得法である。
本論文の焦点は、しばしば近似的な信号回復を促進するサポートリカバリである。
まず, $tildeO(k/epsilon), $tildeO(maxk/epsilon,k3/2), $tildeO(maxk/epsilon,k3/2)$測定を行う。
論文 参考訳（メタデータ） (2022-10-29T17:43:14Z) - Support Recovery in Universal One-bit Compressed Sensing [54.26691979520478]
1ビット圧縮センシング (1bCS) は極端量子化信号取得法である。
少数の偽陽性で支持を普遍的に回復することは可能であることを示す。
論文 参考訳（メタデータ） (2021-07-19T18:10:51Z) - One-Bit Compressed Sensing via One-Shot Hard Thresholding [7.594050968868919]
1ビット圧縮センシングの問題は、いくつかのバイナリ測定からスパース信号を推定することである。
広範に使われている非制約の幅の概念から遠ざかる、斬新で簡潔な分析法を提案する。
論文 参考訳（メタデータ） (2020-07-07T17:28:03Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Differentially Quantized Gradient Methods [53.3186247068836]
微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。
あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
論文 参考訳（メタデータ） (2020-02-06T20:40:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。