論文の概要: Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions

• arxiv url: http://arxiv.org/abs/2104.01101v1
• Date: Fri, 2 Apr 2021 15:55:02 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-05 16:07:55.091187
• Title: Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions
• Title（参考訳）: 低ランクテンソル分解のための高速かつ高精度なランダム化アルゴリズム
• Authors: Linjian Ma and Edgar Solomonik
• Abstract要約: 低ランクタッカーとcpテンソル分解は、データ分析の強力なツールである。 タッカー分解のための高速かつ正確なスケッチALSアルゴリズムを提案する。 さらに、ランダム化されたタッカー圧縮と、タッカーコアテンソルのCP分解を用いて、CP分解を加速するためにも用いられる。
• 参考スコア（独自算出の注目度）: 1.8356693937139124
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Low-rank Tucker and CP tensor decompositions are powerful tools in data analytics. The widely used alternating least squares (ALS) method, which solves a sequence of over-determined least squares subproblems, is inefficient for large and sparse tensors. We propose a fast and accurate sketched ALS algorithm for Tucker decomposition, which solves a sequence of sketched rank-constrained linear least squares subproblems. Theoretical sketch size upper bounds are provided to achieve $O(\epsilon)$-relative error for each subproblem with two sketching techniques, TensorSketch and leverage score sampling. Experimental results show that this new ALS algorithm, combined with a new initialization scheme based on randomized range finder, yields up to $22.0\%$ relative decomposition residual improvement compared to the state-of-the-art sketched randomized algorithm for Tucker decomposition of various synthetic datasets. This Tucker-ALS algorithm is further used to accelerate CP decomposition, by using randomized Tucker compression followed by CP decomposition of the Tucker core tensor. Experimental results show that this algorithm not only converges faster, but also yields more accurate CP decompositions.
• Abstract（参考訳）: 低ランクタッカーとcpテンソル分解は、データ分析の強力なツールである。 過度に決定された最小二乗部分問題(英語版)の列を解く、広く使われる交互最小二乗法(als)は、大きくてスパーステンソルでは非効率である。 本研究では,タッカー分解のための高速かつ高精度なスケッチ付きALSアルゴリズムを提案する。 理論上のスケッチサイズ上限は、各サブプロブレムに対して、tensorsketch と leverage score sampling という2つのスケッチ技法で $o(\epsilon)$-relative error を達成するために提供される。 実験結果から, このアルゴリズムはランダム化レンジファインダに基づく新しい初期化手法と組み合わせて, 様々な合成データセットのタッカー分解のための最先端のスケッチ化ランダム化アルゴリズムと比較して, 22.0\%$の相対分解残差改善が得られることがわかった。 このタッカー-alsアルゴリズムは、ランダム化タッカー圧縮とタッカーコアテンソルのcp分解を用いてcp分解を加速するために用いられる。 実験の結果, このアルゴリズムはより高速に収束するだけでなく, より正確なcp分解をもたらすことがわかった。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Approximately Optimal Core Shapes for Tensor Decompositions [7.1439425093981574]
  我々は,高次特異値への接続による再構成誤差の証明可能な近似保証付きアルゴリズムを提案する。 具体的には、NPハードであることが証明された新しいタッカーパッキング問題を導入し、マトロイドを用いた2次元クナップサック問題への還元に基づく制約時間近似スキームを提案する。
  論文  参考訳（メタデータ） (2023-02-08T05:24:01Z)
• Alternating Mahalanobis Distance Minimization for Stable and Accurate CP Decomposition [4.847980206213335]
  本稿では, テンソルの特異値とベクトルを導出するための新しい定式化を導入する。 このアルゴリズムのサブスウィープは、既知のランクの正確なCPDに対して超線形収束率を達成することができることを示す。 すると、アルゴリズムは各因子に対するマハラノビス距離を最適化するものであり、基底距離は他の因子に依存していると見なす。
  論文  参考訳（メタデータ） (2022-04-14T19:56:36Z)
• A rank-adaptive higher-order orthogonal iteration algorithm for truncated Tucker decomposition [3.4666021409328653]
  ランク適応型HOOIアルゴリズムは精度と効率の両面で有利であることを示す。 HOOIアルゴリズムと古典的交代最小二乗法についてさらなる解析を行い、なぜHOOIアルゴリズムにランク適応性を導入することができるのか、どのように機能するかをさらに理解する。
  論文  参考訳（メタデータ） (2021-10-25T00:46:02Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。 本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。 実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
  論文  参考訳（メタデータ） (2021-09-10T07:01:15Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• NeCPD: An Online Tensor Decomposition with Optimal Stochastic Gradient Descent [1.0953917735844645]
  マルチウェイオンラインデータに基づく$(N)Nにおける非効率的な問題に対して,NeCPDという新しい効率的な分解アルゴリズムを提案する。 さらに,本手法を構造的データセットを用いた実生活モニタリングの分野に適用する。
  論文  参考訳（メタデータ） (2020-03-18T04:44:05Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。