論文の概要: A Smooth Computational Transition in Tensor PCA
- arxiv url: http://arxiv.org/abs/2509.09904v1
- Date: Fri, 12 Sep 2025 00:21:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-15 16:03:07.948405
- Title: A Smooth Computational Transition in Tensor PCA
- Title（参考訳）: テンソルPCAの滑らかな計算遷移
- Authors: Zhangsong Li,
- Abstract要約: 重み付きハイパーグラフの特定の族をカウントしたテンソルPCAの効率的なアルゴリズムを提案する。
この結果から,信号対雑音比と計算コストとの間には円滑なトレードオフが認められた。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose an efficient algorithm for tensor PCA based on counting a specific family of weighted hypergraphs. For the order-$p$ tensor PCA problem where $p \geq 3$ is a fixed integer, we show that when the signal-to-noise ratio is $\lambda n^{-\frac{p}{4}}$ where $\lambda=\Omega(1)$, our algorithm succeeds and runs in time $n^{C+o(1)}$ where $C=C(\lambda)$ is a constant depending on $\lambda$. This algorithm improves a poly-logarithmic factor compared to previous algorithms based on the Sum-of-Squares hierarchy \cite{HSS15} or based on the Kikuchi hierarchy in statistical physics \cite{WEM19}. Furthermore, our result shows a smooth tradeoff between the signal-to-noise ratio and the computational cost in this problem, thereby confirming a conjecture posed in \cite{KWB22}.
- Abstract（参考訳）: 重み付きハイパーグラフの特定の族をカウントしたテンソルPCAの効率的なアルゴリズムを提案する。
順序-$p$のテンソルPCA問題では、$p \geq 3$が固定整数である場合、信号-雑音比が$\lambda n^{-\frac{p}{4}}$であるとき、$\lambda=\Omega(1)$で、我々のアルゴリズムが成功し、時間で$n^{C+o(1)}$で走る場合、$C=C(\lambda)$は$\lambda$に依存する定数であることを示す。
このアルゴリズムは、統計物理学における Sum-of-Squares 階層 \cite{HSS15} や菊池階層をベースとした従来のアルゴリズムと比較して、多対数係数を改善する。
さらに,この結果から,信号対雑音比と計算コストとの円滑なトレードオフが示され,従って \cite{KWB22} の予想が確定される。
関連論文リスト
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
我々は,暗黙のモーメントテンソル複雑性を表わす汎用的アルゴリズムを開発した。
暗黙のモーメント推定アルゴリズムを利用して、以下のモデルに対して最初の$mathrmpoly(d, k, 1/epsilon)$-time学習アルゴリズムを得る。
論文 参考訳（メタデータ） (2024-11-23T23:13:24Z) - A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。
我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
論文 参考訳（メタデータ） (2024-03-07T18:23:51Z) - Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
すべての$t ll k$に対して、[gtrsim fracksqrtntsqrtln(2 + td/k2)$] さえあれば、この問題を解決するアルゴリズムがncdot dO(t)$で実行されていることを示す。
スパース植込みベクター問題に対する時間アルゴリズムは,一部の制度における技術状況よりも高い保証が得られる。
論文 参考訳（メタデータ） (2023-02-20T18:45:24Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor
Decompositions [51.19236668224547]
テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。
テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。
さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
論文 参考訳（メタデータ） (2022-07-15T11:55:09Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - The Complexity of Sparse Tensor PCA [1.90365714903665]
1leq leq k$の場合、我々のアルゴリズムは信号対雑音比$lambda geq tildemathcalO (sqrtt cdot (k/t)p/2)$のスパースベクトルを時間内に回収する。
PCAの制限されたケースでさえ、既知のアルゴリズムは、$lambda geq tildemathcalO(k cdot r)のスパースベクトルのみを復元する一方、我々のアルゴリズムは$lambda geを必要とする。
論文 参考訳（メタデータ） (2021-06-11T10:57:00Z) - The Kikuchi Hierarchy and Tensor PCA [50.840260149979265]
テンソルPCA(主成分分析)問題に対して,ランタイムの増大を伴うアルゴリズムの階層化を提案する。
我々の階層は、SOS(sum-of-squares)階層に似ているが、代わりに統計物理学や関連するアルゴリズムにインスパイアされている。
論文 参考訳（メタデータ） (2019-04-08T06:26:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。