論文の概要: 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$の両方)で最適な測定数を必要とする唯一の実用的で効率的な(多項時間)アルゴリズムである。
これはまた、適切な構造条件下で、非凸問題に対する正しい解に収束する勾配降下アルゴリズムの例である。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - 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) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳(メタデータ) (2022-01-05T15:17:35Z) - 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) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳(メタデータ) (2020-09-29T18:48:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。