論文の概要: Provable Tensor-Train Format Tensor Completion by Riemannian Optimization

• arxiv url: http://arxiv.org/abs/2108.12163v1
• Date: Fri, 27 Aug 2021 08:13:58 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-30 17:50:12.904379
• Title: Provable Tensor-Train Format Tensor Completion by Riemannian Optimization
• Title（参考訳）: リーマン最適化による確率的テンソル・トレインフォーマットのテンソル補完
• Authors: Jian-Feng Cai, Jingyang Li, Dong Xia
• Abstract要約: TT形式テンソル完備化のためのRGradアルゴリズムの収束に関する最初の理論的保証を提供する。 また, 逐次2次モーメント法(Sequence second-order moment method)と呼ばれる新しい手法を提案する。
• 参考スコア（独自算出の注目度）: 22.166436026482984
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The tensor train (TT) format enjoys appealing advantages in handling structural high-order tensors. The recent decade has witnessed the wide applications of TT-format tensors from diverse disciplines, among which tensor completion has drawn considerable attention. Numerous fast algorithms, including the Riemannian gradient descent (RGrad) algorithm, have been proposed for the TT-format tensor completion. However, the theoretical guarantees of these algorithms are largely missing or sub-optimal, partly due to the complicated and recursive algebraic operations in TT-format decomposition. Moreover, existing results established for the tensors of other formats, for example, Tucker and CP, are inapplicable because the algorithms treating TT-format tensors are substantially different and more involved. In this paper, we provide, to our best knowledge, the first theoretical guarantees of the convergence of RGrad algorithm for TT-format tensor completion, under a nearly optimal sample size condition. The RGrad algorithm converges linearly with a constant contraction rate that is free of tensor condition number without the necessity of re-conditioning. We also propose a novel approach, referred to as the sequential second-order moment method, to attain a warm initialization under a similar sample size requirement. As a byproduct, our result even significantly refines the prior investigation of RGrad algorithm for matrix completion. Numerical experiments confirm our theoretical discovery and showcase the computational speedup gained by the TT-format decomposition.
• Abstract（参考訳）: テンソルトレイン(TT)フォーマットは、構造上の高次テンソルを扱う上で魅力的な利点がある。 近年の10年間、様々な分野からTT形式テンソルが広く応用されているのを目撃してきた。 リーマン勾配降下 (rgrad) アルゴリズムを含む多くの高速アルゴリズムがtt形式テンソル完全化のために提案されている。 しかし、これらのアルゴリズムの理論的保証は、TT形式分解における複雑で再帰的な代数演算のために、ほとんど欠落または準最適である。 さらに、TT形式テンソルを扱うアルゴリズムが実質的に異なるため、TuckerやCPといった他のフォーマットのテンソルに対して確立された既存の結果は適用できない。 本稿では, TT形式テンソル完備化のためのRGradアルゴリズムの収束に関する理論的な最初の保証を, ほぼ最適なサンプルサイズ条件下で提供する。 RGradアルゴリズムは、リコンディショニングを必要とせずにテンソル条件数のない一定の収縮率で線形収束する。 また,同様のサンプルサイズ条件下で温かい初期化を実現するために,逐次2次モーメント法と呼ばれる新しい手法を提案する。 副産物として, 行列完全化のためのRGradアルゴリズムの先行研究を改良した。 数値実験により理論的な発見を確認し,tt形式分解による計算速度向上を示す。

関連論文リスト

• Fast and Provable Tensor-Train Format Tensor Completion via Precondtioned Riemannian Gradient Descent [4.376623639964006]
  本稿では, テンソルトレイン(TT)フォーマットに基づく低ランクテンソル完成問題について検討する。 本稿では,TTランクの低いテンソル補完を解き,その線形収束を確立するために,事前条件付き勾配降下アルゴリズム(PRGD)を提案する。 ハイパースペクトル画像補完や量子状態トモグラフィなどの実用的な応用では、PRGDアルゴリズムは繰り返し回数を大幅に削減し、計算時間を劇的に短縮する。
  論文  参考訳（メタデータ） (2025-01-23T05:03:50Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decomposition [27.29463801531576]
  TTに基づくToT回帰モデルの理論的およびアルゴリズム的側面について検討する。 制約付き誤差境界に対する解を効率的に見つけるための2つのアルゴリズムを提案する。 我々はIHTとRGDの両方の線形収束速度を確立する。
  論文  参考訳（メタデータ） (2024-06-10T03:51:38Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Truncated tensor Schatten p-norm based approach for spatiotemporal traffic data imputation with complicated missing patterns [77.34726150561087]
  本研究は, モード駆動繊維による3症例の欠失を含む, 4症例の欠失パターンについて紹介する。 本モデルでは, 目的関数の非性にもかかわらず, 乗算器の交互データ演算法を統合することにより, 最適解を導出する。
  論文  参考訳（メタデータ） (2022-05-19T08:37:56Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition [10.620193291237262]
  これらのアルゴリズムは、ポリアジック分解形態におけるローランクテンソルの因子行列の積空間上の非ユークリッド計量を利用する。 提案された勾配降下アルゴリズムがテンソル完備問題の定常点にグローバルに収束することを証明する。 合成データと実世界のデータの数値計算結果から,提案アルゴリズムは最先端アルゴリズムよりもメモリと時間において効率的であることが示唆された。
  論文  参考訳（メタデータ） (2021-01-26T22:11:06Z)
• Optimal High-order Tensor SVD via Tensor-Train Orthogonal Iteration [10.034394572576922]
  雑音の多い高次テンソル観測から低テンソルトレインのランク構造を推定する新しいアルゴリズムを提案する。 提案したTTOIの利点は、高次マルコフ過程の推定と次元削減への応用を通して説明される。
  論文  参考訳（メタデータ） (2020-10-06T05:18:24Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Geometric All-Way Boolean Tensor Decomposition [14.065968221500246]
  幾何的視点からテンソルのランク-1 基底を逐次同定する GETF を提案する。 合成データと実世界のデータの両方の実験により、GETFは復元精度、潜伏構造の抽出性能を大幅に向上し、他の最先端手法よりも桁違いに高速であることが示された。
  論文  参考訳（メタデータ） (2020-07-31T03:29:44Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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