論文の概要: Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling
- arxiv url: http://arxiv.org/abs/2107.10654v1
- Date: Thu, 22 Jul 2021 13:32:47 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-23 15:19:17.145202
- Title: Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling
- Title（参考訳）: リッジレバレッジスコアサンプリングによる高速低ランクテンソル分解
- Authors: Matthew Fahrbach, Mehrdad Ghadiri, Thomas Fu
- Abstract要約: リッジレバレッジスコア (ridge leverage scores) と呼ばれるランダム化数値線形代数のタッカー分解とツールの利用について検討する。
近似リッジレバレッジスコアを用いて、任意のリッジ回帰問題に対してスケッチされたインスタンスを構築する方法を示す。
本研究では, 合成データと実世界のデータの両方に対して, 大規模かつ低ランクのタッカー分解に対する近似リッジ回帰アルゴリズムの有効性を示す。
- 参考スコア（独自算出の注目度）: 5.740578698172382
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Low-rank tensor decomposition generalizes low-rank matrix approximation and
is a powerful technique for discovering low-dimensional structure in
high-dimensional data. In this paper, we study Tucker decompositions and use
tools from randomized numerical linear algebra called ridge leverage scores to
accelerate the core tensor update step in the widely-used alternating least
squares (ALS) algorithm. Updating the core tensor, a severe bottleneck in ALS,
is a highly-structured ridge regression problem where the design matrix is a
Kronecker product of the factor matrices. We show how to use approximate ridge
leverage scores to construct a sketched instance for any ridge regression
problem such that the solution vector for the sketched problem is a
$(1+\varepsilon)$-approximation to the original instance. Moreover, we show
that classical leverage scores suffice as an approximation, which then allows
us to exploit the Kronecker structure and update the core tensor in time that
depends predominantly on the rank and the sketching parameters (i.e., sublinear
in the size of the input tensor). We also give upper bounds for ridge leverage
scores as rows are removed from the design matrix (e.g., if the tensor has
missing entries), and we demonstrate the effectiveness of our approximate ridge
regressioni algorithm for large, low-rank Tucker decompositions on both
synthetic and real-world data.
- Abstract（参考訳）: 低ランクテンソル分解は低ランク行列近似を一般化し、高次元データにおいて低次元構造を発見するための強力な技術である。
本稿では,タッカー分解とリッジレバレッジスコアと呼ばれるランダム化された数値線形代数のツールを用いて,多用な交互最小二乗アルゴリズムのコアテンソル更新ステップを高速化する。
ALSの深刻なボトルネックであるコアテンソルの更新は、設計行列が係数行列のクロネッカー積である高度に構造化されたリッジ回帰問題である。
近似リッジレバレッジ・スコアを用いて任意のリッジ回帰問題に対するスケッチ付きインスタンスを構築する方法を示し,その解ベクトルが元のインスタンスに対して$(1+\varepsilon)$-approximationであることを示す。
さらに,古典レバレッジのスコアが近似として十分であることを示し,それによってクロネッカー構造を活用し,ランクやスケッチパラメータ(入力テンソルのサイズにおける部分線型)に依存する時間内のコアテンソルを更新できることを示した。
また、行が設計行列から除去されるときのリッジレバレッジスコアの上限(例えば、テンソルがエントリを欠いている場合)を与え、合成データと実世界のデータの両方において、大小のタッカー分解に対する近似リッジ回帰アルゴリズムの有効性を実証する。
関連論文リスト
- Highly Adaptive Ridge [84.38107748875144]
直交可積分な部分微分を持つ右連続函数のクラスにおいて,$n-2/3$自由次元L2収束率を達成する回帰法を提案する。
Harは、飽和ゼロオーダーテンソル積スプライン基底展開に基づいて、特定のデータ適応型カーネルで正確にカーネルリッジレグレッションを行う。
我々は、特に小さなデータセットに対する最先端アルゴリズムよりも経験的性能が優れていることを示す。
論文 参考訳（メタデータ） (2024-10-03T17:06:06Z) - On Learning Gaussian Multi-index Models with Gradient Flow [57.170617397894404]
高次元ガウスデータに対する多次元回帰問題の勾配流について検討する。
低階射影をパラメトリする部分空間よりも、非パラメトリックモデルで低次元リンク関数を無限に高速に学習する2時間スケールのアルゴリズムを考える。
論文 参考訳（メタデータ） (2023-10-30T17:55:28Z) - Noise-Augmented $\ell_0$ Regularization of Tensor Regression with Tucker
Decomposition [13.38920246791158]
テンソル予測器を用いた低ランク分解に基づく回帰法はテンソル予測器の構造情報を利用する。
テンソル回帰のパラメータを正規化するNA$$CT$2$という手法を提案する。
論文 参考訳（メタデータ） (2023-02-19T02:40:35Z) - Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。
この問題は楕円分布のペナルティ化された最大推定値として表される。
楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
論文 参考訳（メタデータ） (2022-10-21T13:19:45Z) - Graph Polynomial Convolution Models for Node Classification of
Non-Homophilous Graphs [52.52570805621925]
本研究では,高階グラフ畳み込みからの効率的な学習と,ノード分類のための隣接行列から直接学習する。
得られたモデルが新しいグラフと残留スケーリングパラメータをもたらすことを示す。
提案手法は,非親和性パラメータのノード分類における精度の向上を実証する。
論文 参考訳（メタデータ） (2022-09-12T04:46:55Z) - Subquadratic Kronecker Regression with Applications to Tensor
Decomposition [4.391912559062643]
我々はKronecker回帰を$(varepsilon-N)$-approximationに解くための最初の準四進時間アルゴリズムを提案する。
本手法は, スコアサンプリングと反復法を組み合わせた手法である。
合成データと実世界の画像テンソル上でのKronecker回帰アルゴリズムの高速化と精度を示す。
論文 参考訳（メタデータ） (2022-09-11T14:24:19Z) - Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。
6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2022-05-21T01:47:17Z) - Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm
Regularization [44.54772242784423]
低ランク学習行列に対する効率的な非正規化アルゴリズムを開発した。
提案アルゴリズムは、高価な折り畳み/折り畳み問題を回避することができる。
実験の結果,提案アルゴリズムは既存の状態よりも効率的で空間が広いことがわかった。
論文 参考訳（メタデータ） (2022-05-06T07:47:10Z) - Solving weakly supervised regression problem using low-rank manifold
regularization [77.34726150561087]
我々は弱い教師付き回帰問題を解く。
weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。
数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
論文 参考訳（メタデータ） (2021-04-13T23:21:01Z) - Low-Rank and Sparse Enhanced Tucker Decomposition for Tensor Completion [3.498620439731324]
テンソル完備化のために,低ランクかつスパースに拡張されたタッカー分解モデルを導入する。
我々のモデルはスパースコアテンソルを促進するためにスパース正規化項を持ち、テンソルデータ圧縮に有用である。
テンソルに出現する潜在的な周期性と固有相関特性を利用するので,本モデルでは様々な種類の実世界のデータセットを扱うことが可能である。
論文 参考訳（メタデータ） (2020-10-01T12:45:39Z) - Sparse and Low-Rank High-Order Tensor Regression via Parallel Proximal
Method [6.381138694845438]
高次構造を持つ大規模データに対するスパース・ローランク回帰モデルを提案する。
我々のモデルはテンソル係数の空間性と低ランク性を強制する。
我々のモデルの予測は、ビデオデータセットに意味のある解釈を示す。
論文 参考訳（メタデータ） (2019-11-29T06:25:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。