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

• arxiv url: http://arxiv.org/abs/2510.02540v1
• Date: Thu, 02 Oct 2025 20:15:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-06 16:35:52.163859
• Title: Even Faster Kernel Matrix Linear Algebra via Density Estimation
• Title（参考訳）: 密度推定によるより高速なカーネル行列線形代数
• Authors: Rikhav Shah, Sandeep Silwal, Haike Xu,
• Abstract要約: 我々は、$mathbb Rd$における$n$のデータポイントの集合のカーネル行列を含む線形代数的タスクにカーネル密度推定(KDE)を用いる。 既存のベストアルゴリズムに対する我々の改善は、$varepsilon$への依存を減らし、カーネル行列の全エントリの和を計算する場合、$n$への依存を減らします。
• 参考スコア（独自算出の注目度）: 12.345340809407617
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the use of kernel density estimation (KDE) for linear algebraic tasks involving the kernel matrix of a collection of $n$ data points in $\mathbb R^d$. In particular, we improve upon existing algorithms for computing the following up to $(1+\varepsilon)$ relative error: matrix-vector products, matrix-matrix products, the spectral norm, and sum of all entries. The runtimes of our algorithms depend on the dimension $d$, the number of points $n$, and the target error $\varepsilon$. Importantly, the dependence on $n$ in each case is far lower when accessing the kernel matrix through KDE queries as opposed to reading individual entries. Our improvements over existing best algorithms (particularly those of Backurs, Indyk, Musco, and Wagner '21) for these tasks reduce the polynomial dependence on $\varepsilon$, and additionally decreases the dependence on $n$ in the case of computing the sum of all entries of the kernel matrix. We complement our upper bounds with several lower bounds for related problems, which provide (conditional) quadratic time hardness results and additionally hint at the limits of KDE based approaches for the problems we study.
• Abstract（参考訳）: 本稿では、$n$のデータポイントの集合のカーネル行列を含む線形代数的問題に対するカーネル密度推定(KDE)の利用について研究する。 特に, 行列ベクトル積, 行列行列積, スペクトルノルム, 全エントリの和について, 1+\varepsilon)=相対誤差で計算するアルゴリズムを改良する。 アルゴリズムのランタイムは次元$d$、点数$n$、ターゲットエラー$\varepsilon$に依存します。 重要なのは、個々のエントリを読むのではなく、KDEクエリを通してカーネルマトリックスにアクセスする場合、各ケースの$n$への依存ははるかに低いことである。 これらのタスクに対する既存の最良のアルゴリズム(特にBackurs、Indyk、Musco、Wagner '21)に対する我々の改善は、$\varepsilon$に対する多項式依存を減少させ、さらに、カーネル行列の全エントリの和を計算する場合、$n$への依存を減少させる。 上界を、関連する問題に対するいくつかの下界で補うことで、(条件付き)2次時間硬度結果を提供し、さらに、我々が研究している問題に対するKDEベースのアプローチの限界を示唆する。

関連論文リスト

• Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions [23.539428616884035]
  非対称ガウス・ケルネル行列に対する行列ベクトル積の高速アルゴリズムについて研究する。 我々のアルゴリズムは、$K$に関する以下のモデリング仮定に依存している: 最悪のケースの成長とは対照的に、$K$のエントリの合計は$n$で線形にスケールする。 我々は、この仮定の下で動作し、制約のない計算を行う最初の準四進時間アルゴリズムを得る。
  論文  参考訳（メタデータ） (2025-07-31T13:29:43Z)
• SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More [37.208622097149714]
  我々は、最大$|M u|$で境界を証明できる新しいアップタイムアルゴリズムの族を与える。 我々の認証アルゴリズムは, Sum-of-Squares階層を必須に活用する。
  論文  参考訳（メタデータ） (2024-12-30T18:59:46Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• 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)
• 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)
• Faster Kernel Matrix Algebra via Density Estimation [46.253698241653254]
  正半定核行列 $K の基本特性を $n$ 点に対応する n$ で計算するための高速アルゴリズムについて研究する。
  論文  参考訳（メタデータ） (2021-02-16T18:25:47Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)

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

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