論文の概要: Leverage Score Sampling for Tensor Product Matrices in Input Sparsity
Time
- arxiv url: http://arxiv.org/abs/2202.04515v1
- Date: Wed, 9 Feb 2022 15:26:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-10 16:08:20.776226
- Title: Leverage Score Sampling for Tensor Product Matrices in Input Sparsity
Time
- Title(参考訳): 入力スパーシティ時間におけるテンソル製品行列のレバレッジスコアサンプリング
- Authors: David P. Woodruff, Amir Zandieh
- Abstract要約: 我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。
我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
- 参考スコア(独自算出の注目度): 54.65688986250061
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give an input sparsity time sampling algorithm for spectrally
approximating the Gram matrix corresponding to the $q$-fold column-wise tensor
product of $q$ matrices using a nearly optimal number of samples, improving
upon all previously known methods by poly$(q)$ factors. Furthermore, for the
important special care of the $q$-fold self-tensoring of a dataset, which is
the feature matrix of the degree-$q$ polynomial kernel, the leading term of our
method's runtime is proportional to the size of the dataset and has no
dependence on $q$. Previous techniques either incur a poly$(q)$ factor slowdown
in their runtime or remove the dependence on $q$ at the expense of having
sub-optimal target dimension, and depend quadratically on the number of
data-points in their runtime. Our sampling technique relies on a collection of
$q$ partially correlated random projections which can be simultaneously applied
to a dataset $X$ in total time that only depends on the size of $X$, and at the
same time their $q$-fold Kronecker product acts as a near-isometry for any
fixed vector in the column span of $X^{\otimes q}$. We show that our sampling
methods generalize to other classes of kernels beyond polynomial, such as
Gaussian and Neural Tangent kernels.
- Abstract(参考訳): ほぼ最適なサンプル数を用いて,$q$-foldカラムワイドテンソル積の$q$-foldカラムワイドテンソル積に対応するGram行列をスペクトル近似するための入力空間時間サンプリングアルゴリズムを提案し,ポリ$(q)$因子によるすべての既知手法を改善した。
さらに、次数-$q$多項式カーネルの特徴行列であるデータセットの$q$-foldセルフテンソル化に関する重要な特別な注意として、この方法のランタイムの主項はデータセットのサイズに比例し、$q$に依存しない。
以前のテクニックは、実行時にpoly$(q)$ Factorのスローダウンを発生させたり、最適以下のターゲット次元を持つために$q$への依存を排除したり、実行時のデータポイントの数に2次に依存する。
我々のサンプリング技術は、データセットの$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存しており、これは、$X$のサイズに依存するが、同時に、それらの$q$-fold Kronecker製品は、カラム内の固定ベクトルのほぼ等距離として機能する。
サンプリング手法は,ガウスカーネルやニューラルタンジェントカーネルなど,多項式以外のカーネルに一般化されていることを示す。
関連論文リスト
- Data-Driven Linear Complexity Low-Rank Approximation of General Kernel
Matrices: A Geometric Approach [0.9453554184019107]
K_ij = kappa(x_i,y_j)$ ここで $kappa(x,y)$ はカーネル関数である。
我々は、点の集合 X$ と $Y$ が大きいカーネル行列に対する低ランク近似を求める。
論文 参考訳(メタデータ) (2022-12-24T07:15:00Z) - An Equivalence Principle for the Spectrum of Random Inner-Product Kernel
Matrices with Polynomial Scalings [21.727073594338297]
この研究は、機械学習と統計学の応用によって動機付けられている。
スケーリングシステムにおいて,これらのランダム行列の経験的分布の弱い限界を確立する。
我々の結果は、マルテンコ・パストゥル法と半円法の間の自由加法的畳み込みとして特徴づけられる。
論文 参考訳(メタデータ) (2022-05-12T18:50:21Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳(メタデータ) (2021-10-05T09:33:49Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Two-way kernel matrix puncturing: towards resource-efficient PCA and
spectral clustering [43.50783459690612]
この方法は、データマトリックス$XinmathbbCptimes n$と対応するカーネル(Gram)マトリックス$K$の両方をBernoulliマスクを介してランダムに「切断」する。
我々は、GAN生成した画像データベースを実証的に確認し、データを劇的にパンクし、巨大な計算とストレージのゲインを提供することができることを確認した。
論文 参考訳(メタデータ) (2021-02-24T14:01:58Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-09-30T19:10:32Z) - Sampling from a $k$-DPP without looking at all items [58.30573872035083]
カーネル関数とサブセットサイズ$k$が与えられた場合、我々のゴールは、サブセットによって誘導されるカーネル行列の行列式に比例する確率を持つ$n$アイテムから$k$をサンプリングすることである(つまり$k$-DPP)。
既存の$k$-DPPサンプリングアルゴリズムは、すべての$n$アイテムを複数回パスする高価な前処理ステップを必要とするため、大規模なデータセットでは利用できない。
そこで我々は, 十分大きなデータの均一なサンプルを適応的に構築し, より小さな$k$のアイテムを効率よく生成するアルゴリズムを開発した。
論文 参考訳(メタデータ) (2020-06-30T16:40:44Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳(メタデータ) (2020-06-12T10:21:40Z) - Robust Sub-Gaussian Principal Component Analysis and Width-Independent
Schatten Packing [22.337756118270217]
基本統計量に対する2つの方法を開発した:$epsilon$-corrupted set of $n$ sample from a $d$-linear sub-Gaussian distribution。
最初のロバストなアルゴリズムは反復フィルタリングを時間内に実行し、近似固有ベクトルを返し、単純なフィルタリングアプローチに基づいている。
私たちの2つめは、わずかに悪い近似係数を達成し、軽度のスペクトルギャップ仮定の下でほぼ自明な時間とイテレーションで実行します。
論文 参考訳(メタデータ) (2020-06-12T07:45:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。