論文の概要: Sharp Analysis of Power Iteration for Tensor PCA
- arxiv url: http://arxiv.org/abs/2401.01047v1
- Date: Tue, 2 Jan 2024 05:55:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-03 14:48:03.409212
- Title: Sharp Analysis of Power Iteration for Tensor PCA
- Title（参考訳）: テンソルPCAのパワーイテレーションのシャープ解析
- Authors: Yuchen Wu and Kangjie Zhou
- Abstract要約: リヒャルトおよびモンタナリ2014で導入されたテンソルPCAモデルのパワーアルゴリズムについて検討する。
まず、植込み信号に収束するためにパワーメソッドに必要なイテレーション数について、鋭い境界を定めます。
第二に、我々の分析は、実力の閾値がポリログ(n)因子によって推測されるものよりも小さいことを明らかにしている。
- 参考スコア（独自算出の注目度）: 1.9571840167193135
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the power iteration algorithm for the tensor PCA model
introduced in Richard and Montanari (2014). Previous work studying the
properties of tensor power iteration is either limited to a constant number of
iterations, or requires a non-trivial data-independent initialization. In this
paper, we move beyond these limitations and analyze the dynamics of randomly
initialized tensor power iteration up to polynomially many steps. Our
contributions are threefold: First, we establish sharp bounds on the number of
iterations required for power method to converge to the planted signal, for a
broad range of the signal-to-noise ratios. Second, our analysis reveals that
the actual algorithmic threshold for power iteration is smaller than the one
conjectured in literature by a polylog(n) factor, where n is the ambient
dimension. Finally, we propose a simple and effective stopping criterion for
power iteration, which provably outputs a solution that is highly correlated
with the true signal. Extensive numerical experiments verify our theoretical
results.
- Abstract（参考訳）: リチャードとモンタナリ(2014)で導入されたテンソルPCAモデルの電力反復アルゴリズムについて検討する。
テンソルパワーイテレーションの性質を研究する以前の研究は、一定数の反復に制限されるか、あるいは非自明なデータ独立初期化を必要とする。
本稿では,これらの限界を超えて,ランダムに初期化されたテンソルパワー反復のダイナミクスを多項式的に多くのステップまで解析する。
まず、電力法が植えられた信号に収束するために必要なイテレーションの数を、信号対雑音比の広い範囲に対して鋭い境界を定めます。
第2に, パワーイテレーションのアルゴリズム閾値は, n が環境次元であるポリログ(n)因子によって文献で予想される値よりも小さいことを明らかにする。
最後に、実信号と高い相関性を持つ解を証明的に出力する、電力繰り返しの単純かつ効果的な停止基準を提案する。
広範な数値実験が我々の理論結果を検証する。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。
我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。
また、異なるアンサンブルを区別する新しい問題も分析できます。
論文 参考訳（メタデータ） (2024-04-29T14:33:24Z) - Statistical Estimation in the Spiked Tensor Model via the Quantum
Approximate Optimization Algorithm [17.955614278088238]
量子近似最適化アルゴリズム(QAOA)は、最適化のための汎用アルゴリズムである。
我々は,1ドルステップのQAOAの弱い回復しきい値が1ドルステップのテンソルパワーの繰り返し値と一致することを証明した。
ある$p$と$q$に対して、QAOAはテンソルパワーオーバーラップよりも定数係数が大きいオーバーラップを達成する。
論文 参考訳（メタデータ） (2024-02-29T18:50:28Z) - Sublinear scaling in non-Markovian open quantum systems simulations [0.0]
プロセステンソルを計算する数値的精度のアルゴリズムを導入する。
我々のアプローチでは、無限メモリを持つ環境に対して$mathcalO(nlog n)$の特異値分解しか必要としない。
論文 参考訳（メタデータ） (2023-04-11T15:40:33Z) - Lower Bounds for the Convergence of Tensor Power Iteration on Random
Overcomplete Models [3.7565501074323224]
テンソルパワー反復を任意の真の成分に収束させるためには、テンソルの多くのステップが必要であることを示す。
我々は、テンソル分解の一般的な目的関数が、電力反復経路に沿って厳密に増大していることを証明する。
論文 参考訳（メタデータ） (2022-11-07T19:23:51Z) - Selective Multiple Power Iteration: from Tensor PCA to gradient-based
exploration of landscapes [7.648784748888189]
Selective Multiple Power Iterations (SMPI) はスパイクを回復する重要な問題に対処する新しいアルゴリズムである。
これらの予期せぬ性能は、ノイズが信号の回復に重要な役割を果たす強力なメカニズムに起因していることを示す。
これらの結果は、実用的および理論的応用の両方に強い影響を与える可能性がある。
論文 参考訳（メタデータ） (2021-12-23T01:46:41Z) - Lattice partition recovery with dyadic CART [79.96359947166592]
我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。
この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。
本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。
我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
論文 参考訳（メタデータ） (2021-05-27T23:41:01Z) - Stochastic Approximation for Online Tensorial Independent Component
Analysis [98.34292831923335]
独立成分分析(ICA)は統計機械学習や信号処理において一般的な次元削減ツールである。
本稿では,各独立成分を推定する副産物オンライン時系列アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-28T18:52:37Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳（メタデータ） (2020-04-09T17:54:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。