論文の概要: Minimizing low-rank models of high-order tensors: Hardness, span, tight
relaxation, and applications
- arxiv url: http://arxiv.org/abs/2210.11413v3
- Date: Thu, 21 Dec 2023 19:41:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-25 19:06:15.406954
- Title: Minimizing low-rank models of high-order tensors: Hardness, span, tight
relaxation, and applications
- Title（参考訳）: 高次テンソルの低階モデル最小化:硬さ、スパン、タイト緩和とその応用
- Authors: Nicholas D. Sidiropoulos, Paris Karakasis, and Aritra Konar
- Abstract要約: この基本テンソル問題は 1 以上のテンソル階数に対して NP-hard であることを示す。
低次ランクの場合、提案された連続的な再構成は低複素度勾配に基づく最適化に有効である。
低密度パリティチェックコードや一般復号パリティチェックコードなど,多くの難題に対する有望な結果を示す。
- 参考スコア（独自算出の注目度）: 26.602371644194143
- 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. We show that this fundamental tensor problem
is NP-hard for any tensor rank higher than one, and polynomial-time solvable in
the rank-one case. We also propose a continuous relaxation and prove that it is
tight for any rank. For low-enough ranks, the proposed continuous reformulation
is amenable to low-complexity gradient-based optimization, and we propose a
suite of gradient-based optimization algorithms drawing from projected gradient
descent, Frank-Wolfe, or explicit parametrization of the relaxed constraints.
We also show that our core results remain valid no matter what kind of polyadic
tensor model is used to represent the tensor of interest, including Tucker,
HOSVD/MLSVD, tensor train, or tensor ring. Next, we consider the class of
problems that can be posed as special instances of the problem of interest. We
show that this class includes the partition problem (and thus all NP-complete
problems via polynomial-time transformation), integer least squares, integer
linear programming, integer quadratic programming, sign retrieval (a special
kind of mixed integer programming / restricted version of phase retrieval), and
maximum likelihood decoding of parity check codes. We demonstrate promising
experimental results on a number of hard problems, including state-of-art
performance in decoding low density parity check codes and general parity check
codes.
- Abstract（参考訳）: 我々は階数分解によって指定された位数 n のテンソルの最小または最大のエントリを見つける問題を考える。
別の方法で述べると、r-次元ベクトルの n 個の集合が与えられ、選択されたベクトルのハダマール積の和が最小化または最大化されるように各集合から1つのベクトルを選択する。
この基本テンソル問題は1以上のテンソル階数に対してNPハードであり、階数1の場合多項式時間で解けることを示す。
また,連続的な緩和を提案し,任意のランクに対して密接であることを証明する。
低収率階数に対して,提案手法は低複雑度勾配に基づく最適化に応用可能であり,投影勾配降下,フランクウルフ,緩和制約の明示的パラメトリゼーションから得られる勾配に基づく最適化アルゴリズムの一組を提案する。
また,タッカー,hosvd/mlsvd,テンソルトレイン,テンソルリングなど,どのような多進テンソルモデルを用いて興味のあるテンソルを表現する場合でも,コアとなる結果が有効であることを示した。
次に,関心問題の特別な例として提示できる問題の種類について考察する。
このクラスは分割問題(および多項式時間変換による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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。