論文の概要: Finding the smallest or largest element of a tensor from its low-rank
factors
- arxiv url: http://arxiv.org/abs/2210.11413v1
- Date: Sun, 16 Oct 2022 11:53:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-21 16:15:36.864434
- Title: Finding the smallest or largest element of a tensor from its low-rank
factors
- Title（参考訳）: 低ランク因子からテンソルの最小または最大の要素を見つける
- Authors: Nicholas D. Sidiropoulos, Paris Karakasis, and Aritra Konar
- Abstract要約: 階数分解によって指定される位数$N$のテンソルの最小または最大エントリーを求める問題を考える。
この離散最適化問題は、任意のテンソルランクが 1 より高い場合、NP-hardであることを示す。
- 参考スコア（独自算出の注目度）: 39.1560911775102
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of finding the smallest or largest entry of a tensor
of order $N$ that is specified via its rank decomposition. Stated in a
different way, we are given $N$ sets of $R$-dimensional vectors and we wish to
select one vector from each set such that the sum of the Hadamard product of
the selected vectors is minimized or maximized. This is a fundamental tensor
problem with numerous applications in embedding similarity search, recommender
systems, graph mining, multivariate probability, and statistics. We show that
this discrete optimization problem is NP-hard for any tensor rank higher than
one, but also provide an equivalent continuous problem reformulation which is
amenable to disciplined non-convex optimization. We propose a suite of
gradient-based approximation algorithms whose performance in preliminary
experiments appears to be promising.
- Abstract（参考訳）: 我々は、ランク分解によって指定された位数$n$のテンソルの最小または最大のエントリを見つける問題を考える。
異なる方法で述べると、$R$-次元ベクトルの$N$集合が与えられ、選択されたベクトルのアダマール積の和が最小化または最大化されるように、各集合から1つのベクトルを選択したい。
これは、類似性探索、レコメンダシステム、グラフマイニング、多変量確率、統計学などの多くの応用における基本的なテンソル問題である。
この離散最適化問題は1以上のテンソル階数に対してNPハードであることが示されるが、非凸最適化の規律に適合する等価な連続問題修正も提供する。
本稿では,予備実験における性能が期待できる勾配に基づく近似アルゴリズムの組を提案する。
関連論文リスト
- Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。
我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。
また、異なるアンサンブルを区別する新しい問題も分析できます。
論文 参考訳（メタデータ） (2024-04-29T14:33:24Z) - Decomposition of linear tensor transformations [0.0]
本研究の目的は, 正確なテンソル分解のための数学的枠組みを開発することである。
論文では3つの異なる問題を導出する。
論文 参考訳（メタデータ） (2023-09-14T16:14:38Z) - Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳（メタデータ） (2023-08-17T21:15:04Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Nonnegative Low-Rank Tensor Completion via Dual Formulation with
Applications to Image and Video Completion [2.1227526213206542]
テンソル完備化問題に対する最近のアプローチは、しばしばデータの非負の構造を見落としている。
非負の低ランクテンソルを学習する問題を考察し、双対性理論を用いてそのようなテンソルの新たな分解法を提案する。
提案アルゴリズムは,カラー画像のインペイント,ビデオ補完,ハイパースペクトル画像補完など,様々なタスクにまたがって検証を行う。
論文 参考訳（メタデータ） (2023-05-13T17:51:00Z) - 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) - Smooth tensor estimation with unknown permutations [14.391648046717073]
任意の指数置換を含む滑らかなテンソルモデルの族を開発する。
ブロックワイズ群における制約付き最小二乗推定器がミニマックス誤差境界を達成することを示す。
また,効率の良いボルダカウントアルゴリズムも提案する。
論文 参考訳（メタデータ） (2021-11-08T17:53:48Z) - Nonnegative Tensor Completion via Integer Optimization [5.932152752097064]
我々は,本アルゴリズムが情報理論速度を達成しつつ,線形(数値耐性)なオラクルステップ数に収束することを証明した。
ノルムは0-1ポリトープで定義されるので、これは整数線形計画法を用いてポリトープ上の線形分離問題を解くことができることを意味する。
論文 参考訳（メタデータ） (2021-11-08T15:43:19Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z) - Grassmannian Optimization for Online Tensor Completion and Tracking with
the t-SVD [10.137631021498109]
t-SVD は三次テンソルに対するよく研究されたブロック項分解の特殊化であることを示す。
非完全ストリーミング2次元データから自由部分加群の変化を追跡するアルゴリズムを提案する。
提案手法は精度は高いが, 実アプリケーション上での最先端のテンソル補完アルゴリズムよりも計算時間の方がはるかに高速である。
論文 参考訳（メタデータ） (2020-01-30T15:56:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。