論文の概要: Fast Tensor Completion via Approximate Richardson Iteration

• arxiv url: http://arxiv.org/abs/2502.09534v1
• Date: Thu, 13 Feb 2025 17:50:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-14 13:47:10.617565
• Title: Fast Tensor Completion via Approximate Richardson Iteration
• Title（参考訳）: 近似リチャードソンイテレーションによる高速テンソル完了
• Authors: Mehrdad Ghadiri, Matthew Fahrbach, Yunbum Kook, Ali Jadbabaie,
• Abstract要約: 低ランクテンソル分解(TD)レンズによるテンソル完備化(TC)の研究 多くのTDアルゴリズムは高速な交互最小化法を用いており、各ステップで高度に構造化された線形回帰問題を解く。 我々は,構造化TD回帰アルゴリズムをブラックボックス・サブルーチンとして利用して,TC回帰問題を概ね解くリフト手法を提案する。
• 参考スコア（独自算出の注目度）: 17.17936381695867
• License:
• Abstract: We study tensor completion (TC) through the lens of low-rank tensor decomposition (TD). Many TD algorithms use fast alternating minimization methods, which solve highly structured linear regression problems at each step (e.g., for CP, Tucker, and tensor-train decompositions). However, such algebraic structure is lost in TC regression problems, making direct extensions unclear. To address this, we propose a lifting approach that approximately solves TC regression problems using structured TD regression algorithms as blackbox subroutines, enabling sublinear-time methods. We theoretically analyze the convergence rate of our approximate Richardson iteration based algorithm, and we demonstrate on real-world tensors that its running time can be 100x faster than direct methods for CP completion.
• Abstract（参考訳）: 低ランクテンソル分解 (TD) レンズによるテンソル完備化 (TC) について検討した。 多くのTDアルゴリズムは高速な交互最小化法を用いており、各ステップで高度に構造化された線形回帰問題を解く(CP、タッカー、テンソル-トレイン分解など)。 しかし、そのような代数構造はTC回帰問題で失われ、直接拡張が不明確になる。 そこで本研究では,構造化TD回帰アルゴリズムをブラックボックスサブルーチンとして用いて,TC回帰問題を大まかに解決するリフト手法を提案する。 理論的には、近似リチャードソン反復法に基づくアルゴリズムの収束速度を解析し、実世界のテンソル上では、その実行時間がCP完了の直接法よりも100倍高速であることを示す。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。 汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。 MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
  論文  参考訳（メタデータ） (2024-07-19T08:29:12Z)
• 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)
• Tensor Completion via Integer Optimization [7.813563137863005]
  テンソル完備化問題の主な課題は、計算力と情報理論サンプルの複雑さ率の基本的な緊張である。 過去のアプローチでは、情報理論の速度を達成するか、対応する解を計算するための実用的なアルゴリズムが欠如していた。 本稿では, 線形数のオラクルステップと情報理論速度で証明可能な収束(数値耐性)を両立させることにより, この緊張を解消する新しいテンソル完備化アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2024-02-06T21:44:07Z)
• 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)
• New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition [10.620193291237262]
  これらのアルゴリズムは、ポリアジック分解形態におけるローランクテンソルの因子行列の積空間上の非ユークリッド計量を利用する。 提案された勾配降下アルゴリズムがテンソル完備問題の定常点にグローバルに収束することを証明する。 合成データと実世界のデータの数値計算結果から,提案アルゴリズムは最先端アルゴリズムよりもメモリと時間において効率的であることが示唆された。
  論文  参考訳（メタデータ） (2021-01-26T22:11:06Z)
• DiffPD: Differentiable Projective Dynamics with Contact [65.88720481593118]
  DiffPDは、暗黙の時間積分を持つ効率的な微分可能なソフトボディシミュレータである。 我々はDiffPDの性能を評価し,様々な応用における標準ニュートン法と比較して4～19倍のスピードアップを観測した。
  論文  参考訳（メタデータ） (2021-01-15T00:13:33Z)
• A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs [84.7328507118758]
  構造学習のためのBregman近位勾配法を開発した。 高い非線形反復に対する曲率の影響を計測する。 様々な合成および実集合上で本手法をテストする。
  論文  参考訳（メタデータ） (2020-11-05T11:37:44Z)
• Tensor Completion via Tensor Networks with a Tucker Wrapper [28.83358353043287]
  本論文では,タッカーラッパーを用いたテンソルネットワークを用いて低ランクテンソル完備化(LRTC)を解くことを提案する。 次に、未知の要素を更新するために、2段階の最小二乗法を用いる。 数値シミュレーションにより,提案アルゴリズムは最先端手法に匹敵することを示す。
  論文  参考訳（メタデータ） (2020-10-29T17:54:01Z)
• Grassmannian Optimization for Online Tensor Completion and Tracking with the t-SVD [10.137631021498109]
  t-SVD は三次テンソルに対するよく研究されたブロック項分解の特殊化であることを示す。 非完全ストリーミング2次元データから自由部分加群の変化を追跡するアルゴリズムを提案する。 提案手法は精度は高いが, 実アプリケーション上での最先端のテンソル補完アルゴリズムよりも計算時間の方がはるかに高速である。
  論文  参考訳（メタデータ） (2020-01-30T15:56:14Z)

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

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