Fugu-MT 論文翻訳(概要): A linear-time algorithm for Chow decompositions

論文の概要: A linear-time algorithm for Chow decompositions

arxiv url: http://arxiv.org/abs/2509.10450v1
Date: Fri, 12 Sep 2025 17:56:44 GMT
ステータス: 翻訳完了
システム内更新日: 2025-09-15 16:03:08.194158
Title: A linear-time algorithm for Chow decompositions
Title（参考訳）: Chow分解のための線形時間アルゴリズム
Authors: Alexander Taveira Blomenhofer, Benjamin Lovitz,
Abstract要約: 低ランクChow分解を計算する線形時間アルゴリズムを提案する。我々のアルゴリズムは、Chow ランク n/3 の n 変数において、簡潔な対称な3つのテンソルを分解することができる。
参考スコア（独自算出の注目度）: 45.88028371034407
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We propose a linear-time algorithm to compute low-rank Chow decompositions. Our algorithm can decompose concise symmetric 3-tensors in n variables of Chow rank n/3. The algorithm is pencil based, hence it relies on generalized eigenvalue computations. We also develop sub-quadratic time algorithms for higher order Chow decompositions, and Chow decompositions of 3-tensors into products of linear forms which do not lie on the generic orbit. In particular, we obtain a sub-quadratic-time algorithm for decomposing a symmetric 3-tensor into a linear combination of W-tensors.
Abstract（参考訳）: 低ランクChow分解を計算する線形時間アルゴリズムを提案する。我々のアルゴリズムは、Chow ランク n/3 の n 変数において、簡潔な対称な3つのテンソルを分解することができる。アルゴリズムは鉛筆ベースであるため、一般化された固有値計算に依存する。また、高次Chow分解のための準二次時間アルゴリズムを開発し、3つのテンソルのChow分解をジェネリック軌道上にない線形形式の積に分解する。特に,対称な3つのテンソルをW-テンソルの線形結合に分解するための準四進時間アルゴリズムを得る。

関連論文リスト

Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
本稿では,Arimoto-BlahutアルゴリズムをBregman-Diversergenceシステム上で定義された一般関数に一般化する。このアルゴリズムは古典的および量子速度歪み理論に適用できる。
論文参考訳（メタデータ） (2024-08-10T06:16:24Z)
Polynomial-time Solver of Tridiagonal QUBO, QUDO and Tensor QUDO problems with Tensor Networks [41.94295877935867]
本稿では,三対角四角形非制約二元最適化問題の解法として量子インスピレーション付きテンソルネットワークアルゴリズムを提案する。また、直列鎖内の一方の隣り合う相互作用を伴うより一般的な2次非制約離散最適化問題を解く。
論文参考訳（メタデータ） (2023-09-19T10:45:15Z)
A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning [9.628032156001073]
立方正則化を取り入れた2つのポリシーニュートンアルゴリズムを提案する。どちらのアルゴリズムも確率比法を用いて値関数の勾配とヘシアンを推定する。特に、我々のアルゴリズムのサンプル複雑さが$epsilon$-SOSPを見つけるのに$O(epsilon-3.5)$であり、これは最先端のサンプル複雑性の$O(epsilon-4.5)$よりも改善されている。
論文参考訳（メタデータ） (2023-04-21T13:43:06Z)
Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time [46.31710224483631]
既存の定数係数近似のスケッチ次元における対数的要素について、Nelson and Nguyen (FOCS, 2013) の主な開問題を回避する方法を示す。私たちが使用している重要なテクニックは、不確実性原理と抽出子に基づくIndykの明示的なマッピングです。ランク計算と列の線形独立部分集合の探索という基本的な問題に対して、我々のアルゴリズムはCheung, Kwok, Lau (JACM, 2013)を改良し、それぞれ定数係数と$log(n)$-factorの範囲内で最適である。
論文参考訳（メタデータ） (2021-07-16T19:34:10Z)
Algorithmic Solution for Systems of Linear Equations, in $\mathcal{O}(mn)$ time [0.0]
方程式の線形系の探索解を超高速に求める新しいアルゴリズムを提案する。実行時間は最先端のメソッドと比較して非常に短い。この論文はアルゴリズム収束の理論的証明も含んでいる。
論文参考訳（メタデータ） (2021-04-26T13:40:31Z)
Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文参考訳（メタデータ） (2021-03-03T22:42:15Z)
Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文参考訳（メタデータ） (2020-07-01T18:43:32Z)
Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms [21.904012114713428]
第一のFが滑らかで第二のFが非滑らかで近似可能な3つの凸函数の和を考える。このテンプレート問題には、画像処理や機械学習など、多くの応用がある。この問題に対して PDDY と呼ぶ新しい原始双対アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-04-03T10:48:01Z)
Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文参考訳（メタデータ） (2020-02-21T17:45:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。