論文の概要: Data-Driven Linear Complexity Low-Rank Approximation of General Kernel
Matrices: A Geometric Approach
- arxiv url: http://arxiv.org/abs/2212.12674v1
- Date: Sat, 24 Dec 2022 07:15:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-27 15:44:50.454428
- Title: Data-Driven Linear Complexity Low-Rank Approximation of General Kernel
Matrices: A Geometric Approach
- Title（参考訳）: 一般核行列のデータ駆動線形複雑性低ランク近似:幾何学的アプローチ
- Authors: Difeng Cai, Edmond Chow, Yuanzhe Xi
- Abstract要約: K_ij = kappa(x_i,y_j)$ ここで $kappa(x,y)$ は核関数であり、$X=x_i_i=1m$ と $Y=y_i_i=1n$ は点の集合である。
本稿では,X$ および$Y$ の点集合が大小であり,十分に分離されていないカーネル行列に対する低ランク近似を求める。
- 参考スコア（独自算出の注目度）: 0.9453554184019107
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A general, {\em rectangular} kernel matrix may be defined as $K_{ij} =
\kappa(x_i,y_j)$ where $\kappa(x,y)$ is a kernel function and where
$X=\{x_i\}_{i=1}^m$ and $Y=\{y_i\}_{i=1}^n$ are two sets of points. In this
paper, we seek a low-rank approximation to a kernel matrix where the sets of
points $X$ and $Y$ are large and are not well-separated (e.g., the points in
$X$ and $Y$ may be ``intermingled''). Such rectangular kernel matrices may
arise, for example, in Gaussian process regression where $X$ corresponds to the
training data and $Y$ corresponds to the test data. In this case, the points
are often high-dimensional. Since the point sets are large, we must exploit the
fact that the matrix arises from a kernel function, and avoid forming the
matrix, and thus ruling out most algebraic techniques. In particular, we seek
methods that can scale linearly, i.e., with computational complexity $O(m)$ or
$O(n)$ for a fixed accuracy or rank. The main idea in this paper is to {\em
geometrically} select appropriate subsets of points to construct a low rank
approximation. An analysis in this paper guides how this selection should be
performed.
- Abstract（参考訳）: 一般に、カーネル行列は $k_{ij} = \kappa(x_i,y_j)$ ここで $\kappa(x,y)$ はカーネル関数であり、$x=\{x_i\}_{i=1}^m$ と $y=\{y_i\}_{i=1}^n$ は2つの点の集合である。
本稿では、X$ と $Y$ の集合が大きめで、十分に分離されていないカーネル行列に対する低ランク近似を求める(例えば、$X$ と $Y$ の点が 'intermingled'' である)。
このような長方形のカーネル行列は、例えばガウスのプロセス回帰において、$X$はトレーニングデータに対応し、$Y$はテストデータに対応する。
この場合、点はしばしば高次元である。
点集合は大きいので、行列が核関数から生じるという事実を活用し、行列の形成を避け、したがってほとんどの代数的手法を除外しなければならない。
特に、計算複雑性$Oで線形にスケールできる方法を模索する。
(m)$または$O
(n) 一定の精度またはランクに対して。
この論文の主なアイデアは、低位近似を構成する点の適切な部分集合を幾何学的に選択することである。
本稿では,この選択をいかに行うべきかを考察する。
関連論文リスト
- 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) - A General Algorithm for Solving Rank-one Matrix Sensing [15.543065204102714]
マトリックスセンシングの目標は、一連の測定に基づいて、mathbbRn×n$の行列$A_starを復元することである。
本稿では、このランク-$kの仮定を緩和し、より一般的な行列センシング問題を解く。
論文 参考訳（メタデータ） (2023-03-22T04:07:26Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Scalable First-Order Bayesian Optimization via Structured Automatic
Differentiation [4.061135251278187]
広い範囲のカーネルが構造化行列を生じさせ、勾配観測のための正確な$mathcalO(n2d)$Matrix-vector multiplyとヘッセン観測のための$mathcalO(n2d2)$を可能にした。
提案手法は,ほぼすべての標準カーネルに適用され,ニューラルネットワーク,放射基底関数ネットワーク,スペクトル混合カーネルなどの複雑なカーネルに自動的に拡張される。
論文 参考訳（メタデータ） (2022-06-16T17:59:48Z) - Spectrum of inner-product kernel matrices in the polynomial regime and
multiple descent phenomenon in kernel ridge regression [3.997680012976965]
カーネル行列はその次数-$ell$近似によってよく近似される。
行列のスペクトルが分布に収束することを示す。
論文 参考訳（メタデータ） (2022-04-21T22:20:52Z) - Leverage Score Sampling for Tensor Product Matrices in Input Sparsity
Time [54.65688986250061]
我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。
我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
論文 参考訳（メタデータ） (2022-02-09T15:26:03Z) - 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) - 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) - Faster Kernel Matrix Algebra via Density Estimation [46.253698241653254]
正半定核行列 $K の基本特性を $n$ 点に対応する n$ で計算するための高速アルゴリズムについて研究する。
論文 参考訳（メタデータ） (2021-02-16T18:25:47Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。