論文の概要: Faster Kernel Matrix Algebra via Density Estimation

• arxiv url: http://arxiv.org/abs/2102.08341v1
• Date: Tue, 16 Feb 2021 18:25:47 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-18 07:14:54.382035
• Title: Faster Kernel Matrix Algebra via Density Estimation
• Title（参考訳）: 密度推定による高速カーネル行列代数
• Authors: Arturs Backurs and Piotr Indyk and Cameron Musco and Tal Wagner
• Abstract要約: 正半定核行列 $K の基本特性を $n$ 点に対応する n$ で計算するための高速アルゴリズムについて研究する。
• 参考スコア（独自算出の注目度）: 46.253698241653254
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study fast algorithms for computing fundamental properties of a positive semidefinite kernel matrix $K \in \mathbb{R}^{n \times n}$ corresponding to $n$ points $x_1,\ldots,x_n \in \mathbb{R}^d$. In particular, we consider estimating the sum of kernel matrix entries, along with its top eigenvalue and eigenvector. We show that the sum of matrix entries can be estimated to $1+\epsilon$ relative error in time $sublinear$ in $n$ and linear in $d$ for many popular kernels, including the Gaussian, exponential, and rational quadratic kernels. For these kernels, we also show that the top eigenvalue (and an approximate eigenvector) can be approximated to $1+\epsilon$ relative error in time $subquadratic$ in $n$ and linear in $d$. Our algorithms represent significant advances in the best known runtimes for these problems. They leverage the positive definiteness of the kernel matrix, along with a recent line of work on efficient kernel density estimation.
• Abstract（参考訳）: 正半定核行列 $K \in \mathbb{R}^{n \times n}$ の基本特性を計算するための高速アルゴリズムを $n$ 点 $x_1,\ldots,x_n \in \mathbb{R}^d$ に対応する研究する。 特に、最上位固有値と固有ベクトルとともに、カーネル行列成分の和を推定することを検討する。 行列エントリの合計は、$n$ で $sublinear$ の時における $+\epsilon$ 相対誤差と、ガウス、指数、有理二次カーネルを含む多くの一般的なカーネルに対して $d$ で線形に推定できることを示した。 これらのカーネルについて、トップ固有値(および近似固有ベクトル)は、時間$n$で$subquadratic$、線形で$d$で1+\epsilon$相対誤差に近似できることを示した。 当社のアルゴリズムは、これらの問題に対する最もよく知られたランタイムの大幅な進歩を表します。 それらは、カーネルマトリックスの正定性と、効率的なカーネル密度推定に関する最近の一連の研究を活用する。

関連論文リスト

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Fast Evaluation of Additive Kernels: Feature Arrangement, Fourier Methods, and Kernel Derivatives [0.5735035463793009]
  厳密な誤り解析を伴う非等間隔高速フーリエ変換(NFFT)に基づく手法を提案する。 また,本手法は,カーネルの分化に伴う行列の近似に適していることを示す。 複数のデータセット上で高速な行列ベクトル積を持つ付加的カーネルスキームの性能について述べる。
  論文  参考訳（メタデータ） (2024-04-26T11:50:16Z)
• 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)
• Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation [24.166833799353476]
  カーネルグラフ上では$textitweighted edge sample$、カーネルグラフ上では$textitweighted walk$、行列で$textitweighted sample$からKernel Density Estimationへ効率よく還元する。 当社の削減は、それぞれのアプリケーションにおいて中心的な要素であり、それらが独立した関心事である可能性があると信じています。
  論文  参考訳（メタデータ） (2022-12-01T16:42:56Z)
• Log-Linear-Time Gaussian Processes Using Binary Tree Kernels [26.526204269075766]
  我々は,$O((n+m)log(n+m))$ timeでガウス過程の回帰を可能にする新しいカーネルを提案する。 我々の"バイナリツリー"カーネルは、すべてのデータをバイナリツリーの葉に配置し、カーネルは最も深い共通の祖先の深さにのみ依存します。 大規模なデータセットでは、二分木GPはマタンGPよりも高速で、はるかに高速である。
  論文  参考訳（メタデータ） (2022-10-04T14:30:06Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。 我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
  論文  参考訳（メタデータ） (2022-02-09T15:26:03Z)
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra [6.338178373376447]
  本稿では,量子コンピュータ上の階層行列構造のブロック符号化方式を提案する。 我々の手法は、次元$N$から$O(kappa operatornamepolylog(fracNvarepsilon))$の量子線型系を解くランタイムを改善することができる。
  論文  参考訳（メタデータ） (2022-01-27T05:24:02Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• 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)

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

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