論文の概要: Guaranteed Nonconvex Low-Rank Tensor Estimation via Scaled Gradient Descent
- arxiv url: http://arxiv.org/abs/2501.01696v1
- Date: Fri, 03 Jan 2025 08:26:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-06 15:12:06.016180
- Title: Guaranteed Nonconvex Low-Rank Tensor Estimation via Scaled Gradient Descent
- Title(参考訳): スケールドグラディエント線による非凸低ランクテンソル推定
- Authors: Tong Wu,
- Abstract要約: 本稿では,テンソル因子を直接推定するスケールド勾配降下法(ScaledGD)を提案する。
理論上、ScaledGD は基底真理低ランクテンソルの条件数に依存しない定数速度で線形収束を達成する。
虚弱条件下での低ランクテンソル推定の収束速度を加速する上でのScaledGDの有効性を示す数値的な例を提供する。
- 参考スコア(独自算出の注目度): 4.123899820318987
- License:
- Abstract: Tensors, which give a faithful and effective representation to deliver the intrinsic structure of multi-dimensional data, play a crucial role in an increasing number of signal processing and machine learning problems. However, tensor data are often accompanied by arbitrary signal corruptions, including missing entries and sparse noise. A fundamental challenge is to reliably extract the meaningful information from corrupted tensor data in a statistically and computationally efficient manner. This paper develops a scaled gradient descent (ScaledGD) algorithm to directly estimate the tensor factors with tailored spectral initializations under the tensor-tensor product (t-product) and tensor singular value decomposition (t-SVD) framework. In theory, ScaledGD achieves linear convergence at a constant rate that is independent of the condition number of the ground truth low-rank tensor for two canonical problems -- tensor robust principal component analysis and tensor completion -- as long as the level of corruptions is not too large and the sample size is sufficiently large, while maintaining the low per-iteration cost of gradient descent. To the best of our knowledge, ScaledGD is the first algorithm that provably has such properties for low-rank tensor estimation with the t-SVD decomposition. Finally, numerical examples are provided to demonstrate the efficacy of ScaledGD in accelerating the convergence rate of ill-conditioned low-rank tensor estimation in these two applications.
- Abstract(参考訳): 多次元データの本質的な構造を提供するための忠実で効果的な表現を提供するテンソルは、信号処理や機械学習問題の増加において重要な役割を果たす。
しかし、テンソルデータには、欠落したエントリやスパースノイズを含む任意の信号の破損が伴うことが多い。
基本的な課題は、統計的かつ計算的に効率的な方法で、破損したテンソルデータから有意義な情報を確実に抽出することである。
本稿では,テンソル・テンソル積 (t-product) とテンソル特異値分解 (t-SVD) フレームワークに基づいて,スペクトル初期化を調整したテンソル因子を直接推定するスケールド勾配降下法 (ScaledGD) アルゴリズムを開発した。
理論上、ScaledGDは、2つの正準問題(テンソルの頑健な主成分分析とテンソル完備化)に対する基底真理の低ランクテンソルの条件数とは無関係な一定の速度で線形収束を達成する。
我々の知る限りでは、ScaledGD は t-SVD 分解による低ランクテンソル推定のための特性を証明可能な最初のアルゴリズムである。
最後に、これらの2つの応用において、不条件の低ランクテンソル推定の収束速度を加速させるためのScaledGDの有効性を示す数値的な例を示す。
関連論文リスト
- Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent [21.51873526389341]
本稿では,Burer-Monteiro法に類似した因子分解法に基づく効率的かつ効果的な低ツバルテンソル回収法を提案する。
我々は,FGDのノイズフリーおよび雑音条件下での収束を確保するために,厳密な理論的解析を行う。
提案手法は,より高速な計算速度とより小さい収束誤差の観点から,複数のシナリオにおいて優れた性能を示す。
論文 参考訳(メタデータ) (2024-01-22T13:30:11Z) - Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled
Gradient Descent, Even with Overparameterization [48.65416821017865]
この章では、スケールドグラデーション(ScaledGD)と呼ばれる新しいアルゴリズムアプローチを紹介します。
低ランク物体の条件数に依存しない定数速度で直線的に収束する。
様々なタスクに対して、勾配降下の低い摂動コストを維持できる。
論文 参考訳(メタデータ) (2023-10-09T21:16:57Z) - Scalable and Robust Tensor Ring Decomposition for Large-scale Data [12.02023514105999]
本稿では,大規模テンソルデータに欠落したエントリと粗悪な破損を扱えるスケーラブルで堅牢なTR分解アルゴリズムを提案する。
まず, 欠落したエントリを適応的に満たし, 分解過程における外れ値の同定が可能な, 自己重み付き急勾配降下法を開発した。
論文 参考訳(メタデータ) (2023-05-15T22:08:47Z) - Low-Rank Tensor Function Representation for Multi-Dimensional Data
Recovery [52.21846313876592]
低ランクテンソル関数表現(LRTFR)は、無限解像度でメッシュグリッドを超えてデータを連続的に表現することができる。
テンソル関数に対する2つの基本的な概念、すなわちテンソル関数ランクとローランクテンソル関数分解を開発する。
提案手法は,最先端手法と比較して,提案手法の優越性と汎用性を裏付けるものである。
論文 参考訳(メタデータ) (2022-12-01T04:00:38Z) - Error Analysis of Tensor-Train Cross Approximation [88.83467216606778]
我々は, テンソル全体の精度保証を行う。
結果は数値実験により検証され、高次テンソルに対するクロス近似の有用性に重要な意味を持つ可能性がある。
論文 参考訳(メタデータ) (2022-07-09T19:33:59Z) - Fast and Provable Tensor Robust Principal Component Analysis via Scaled
Gradient Descent [30.299284742925852]
本稿では、テンソルロバスト主成分分析(RPCA)に取り組む。
希少な腐敗によって汚染された観測から低ランクのテンソルを回収することを目的としている。
提案アルゴリズムは, 最先端行列やテンソルRPCAアルゴリズムよりも, より優れた, よりスケーラブルな性能を実現する。
論文 参考訳(メタデータ) (2022-06-18T04:01:32Z) - 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) - Noisy Tensor Completion via Low-rank Tensor Ring [41.86521269183527]
テンソル完了は不完全なデータ解析の基本的なツールであり、その目標は部分的な観測から欠落するエントリを予測することである。
既存の手法は、観測されたエントリがノイズフリーであるという明示的あるいは暗黙的な仮定をしばしば示し、欠落したエントリの正確な回復を理論的に保証する。
本稿では,高次・高次観測の劣化処理における既存の作業の非効率性を補完する新しいノイズテンソル補完モデルを提案する。
論文 参考訳(メタデータ) (2022-03-14T14:09:43Z) - Augmented Tensor Decomposition with Stochastic Optimization [46.16865811396394]
実世界のテンソルデータは、通常高次で、数百万から数十億のエントリを持つ大きな次元を持つ。
テンソル全体を従来のアルゴリズムで分解するのは高価である。
本稿では、データ拡張を効果的に取り入れて下流の分類を向上する拡張テンソル分解を提案する。
論文 参考訳(メタデータ) (2021-06-15T06:29:05Z) - Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation
from Incomplete Measurements [30.395874385570007]
基本的な課題は、高度に不完全な測定からテンソルを忠実に回収することである。
タッカー分解におけるテンソル因子を直接回復するアルゴリズムを開発した。
2つの正準問題に対する基底真理テンソルの線形独立率で確実に収束することを示す。
論文 参考訳(メタデータ) (2021-04-29T17:44:49Z) - Uncertainty quantification for nonconvex tensor completion: Confidence
intervals, heteroscedasticity and optimality [92.35257908210316]
本研究では,不完全かつ破損した観測によって与えられる低ランクテンソルを推定する問題について検討する。
改善不可能なレートをell-2$の精度で達成できることが分かりました。
論文 参考訳(メタデータ) (2020-06-15T17:47:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。