論文の概要: Approximate Low-Rank Decomposition for Real Symmetric Tensors
- arxiv url: http://arxiv.org/abs/2207.12529v1
- Date: Mon, 25 Jul 2022 20:56:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-27 13:34:21.617089
- Title: Approximate Low-Rank Decomposition for Real Symmetric Tensors
- Title（参考訳）: 実対称テンソルの近似低ランク分解
- Authors: Alperen A. Erg\"ur, Jesus Rebollo Bueno, Petros Valettas
- Abstract要約: 本稿では,アルゴリズムの観点からの対称テンソル分解に対する$varepsilon$-roomの摂動耐性の影響について検討する。
近似対称テンソルランク推定のための2つの異なる理論境界と3つのアルゴリズムを提供する。
すべてのアルゴリズムは厳密な複雑性推定を持ち、その結果、$varepsilon$-room of tolerance を持つ対称テンソルランクの2つの主要な定理が得られる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the effect of an $\varepsilon$-room of perturbation tolerance
on symmetric tensor decomposition from an algorithmic perspective. More
precisely, we prove theorems and design algorithms for the following problem:
Suppose a real symmetric $d$-tensor $f$, a norm $||.||$ on the space of
symmetric $d$-tensors, and $\varepsilon >0$ error tolerance with respect to
$||.||$ are given. What is the smallest symmetric tensor rank in the
$\varepsilon$-neighborhood of $f$? In other words, what is the symmetric tensor
rank of $f$ after a clever $\varepsilon$-perturbation? We provide two different
theoretical bounds and three algorithms for approximate symmetric tensor rank
estimation. Our first result is a randomized energy increment algorithm for the
case of $L_p$-norms. Our second result is a simple sampling-based algorithm,
inspired by some techniques in geometric functional analysis, that works for
any norm. We also provide a supplementary algorithm in the case of the
Hilbert-Schmidt norm. All our algorithms come with rigorous complexity
estimates, which in turn yield our two main theorems on symmetric tensor rank
with $\varepsilon$-room of tolerance. We also report on our experiments with a
preliminary implementation of the energy increment algorithm.
- Abstract（参考訳）: アルゴリズム的観点から,摂動許容値の$\varepsilon$-roomが対称テンソル分解に及ぼす影響について検討した。
より正確には、次の問題に対して定理と設計アルゴリズムを証明する: 実対称$d$-tensor $f$, a norm $|| とする。
対称な$d$-テンソルの空間上の||$と、$||に関して$\varepsilon >0$エラー耐性を持つ。
||$が与えられる。
最小の対称テンソルランクは、$f$の$\varepsilon$-neighborhoodである。
言い換えれば、賢い$\varepsilon$-perturbationの後、対称テンソルランクは$f$とは何ですか?
近似対称テンソルランク推定のための2つの異なる理論境界と3つのアルゴリズムを提供する。
最初の結果は、$L_p$-normsの場合のランダム化エネルギー増分アルゴリズムである。
第2の結果は単純なサンプリングに基づくアルゴリズムで,幾何関数解析の手法に触発されて,任意のノルムに対して動作する。
また、ヒルベルト・シュミットノルムの場合の補アルゴリズムも提供する。
すべてのアルゴリズムは厳密な複雑性推定を持ち、従って、$\varepsilon$-room of tolerance を持つ対称テンソルランクの2つの主要な定理が得られる。
また,エネルギー増量アルゴリズムの予備実装による実験についても報告する。
関連論文リスト
- Overcomplete Tensor Decomposition via Koszul-Young Flattenings [63.01248796170617]
最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。
次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
論文 参考訳（メタデータ） (2024-11-21T17:41:09Z) - Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。
PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
論文 参考訳（メタデータ） (2024-10-10T06:15:42Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing:
The Curses of Symmetry and Initialization [46.55524654398093]
過パラメータ化が降下の収束挙動をどのように変化させるかを示す。
目的は、ほぼ等方的線形測定から未知の低ランクの地上構造行列を復元することである。
本稿では,GDの一段階だけを修飾し,$alpha$に依存しない収束率を求める手法を提案する。
論文 参考訳（メタデータ） (2023-10-03T03:34:22Z) - Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
任意のアルゴリズムが$Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector productを必要とし、Krylov法で得られる上限値と正確に一致することを示す。
我々の下位境界はOpen Question 1WooWoo14で、Spectral LRAのアルゴリズムの進歩の欠如の証拠を提供している。
論文 参考訳（メタデータ） (2023-04-06T16:15:19Z) - Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models:
Sharp Minimax Rates [1.0309387309011746]
スパースな代替品に対する信号検出問題を、既知のスパシティ$s$に対して検討する。
ミニマックス分離半径$epsilon*$の上の上限と下限を見つけ、それらが常に一致することを証明する。
以上の結果から,epsilon*$の挙動に関する新たな位相遷移が,Sigma$の疎度レベル,$Lt$メトリック,およびヘテロスセダサシティプロファイル(herescedasticity profile)に現れる。
論文 参考訳（メタデータ） (2022-11-15T23:53:39Z) - Monogamy of entanglement between cones [68.8204255655161]
モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。
我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
論文 参考訳（メタデータ） (2022-06-23T16:23:59Z) - Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。
偏光理論への我々の結果の即時適用について述べる。
論文 参考訳（メタデータ） (2022-05-30T18:01:34Z) - Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。
密度行列 $rho$ は可観測物の期待値から決定できると仮定される。
アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
論文 参考訳（メタデータ） (2021-12-14T16:29:53Z) - Extremal elements of a sublattice of the majorization lattice and
approximate majorization [0.0]
一般に、極値確率ベクトルは、閉じた球に対して$mathcalBp_epsilon(x)$に対して1pinfty$で存在しないことを示す。
また、ボールの半径と中心の点から、これらの極端要素を明示的に特徴づける。
論文 参考訳（メタデータ） (2020-01-23T19:09:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。