論文の概要: Low-Dimensional Embeddings for Gaussian Kernels on Manifolds

• arxiv url: http://arxiv.org/abs/2609.15179v1
• Date: Mon, 14 Sep 2026 08:00:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:06.177008
• Title: Low-Dimensional Embeddings for Gaussian Kernels on Manifolds
• Title（参考訳）: 多様体上のガウス核の低次元埋め込み
• Abstract要約: $mathbb RN$, $t=((d/varepsilon2)log(dR/varepsilon))$ の$d$次元ユークリッド球の点に対して、任意のガウス核距離を保存するのに十分であることを示す。 同様の RFF 埋め込みの下では、ガウス核のパワー距離から作られる重み付き Cech と Rips のフィルターは$(pmvarepsilon_star)$-interleaved という意味で持続的ホモロジーが保存される。
• 参考スコア（独自算出の注目度）: 0.42970700836450487
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Gaussian kernel is a widely used similarity measure underlying kernel methods such as kernel PCA and spectral clustering, but computing Gaussian kernel distances for many pairs of points can be expensive. Using Random Fourier Features (RFF), Chen and Phillips [ALT 2017] showed that for points in a $d$-dimensional Euclidean ball in ${\mathbb R}^N$, $t=Ω((d/\varepsilon^2)\log(dR/\varepsilon))$ features suffice to preserve all pairwise Gaussian kernel distances within a $(1\pm\varepsilon)$ factor with high probability. We establish a uniform relative-error embedding theorem for the more general setting of an arbitrary positive-reach submanifold $\mathcal M\subset{\mathbb R}^N$ of intrinsic dimension $d$. We show that $t=O((d/\varepsilon^2)\log(\operatorname{vol}(\mathcal M)^2N^{2d}/(\operatorname{vol}(B_1^d(0))^2\operatorname{rch}(\mathcal M)^{2d}\varepsilon^{2d+1}δ)))$, or approximately $O((d^2/\varepsilon^2)(\log N+\log(1/(\varepsilonδ))))$, RFFs suffice, with probability $1-δ$, to preserve the Gaussian kernel distance between every pair of manifold points up to relative error $\varepsilon$. Thus the bound depends only logarithmically on the ambient dimension and on manifold parameters such as volume and reach, while retaining the $1/\varepsilon^2$ Euclidean rate. We also prove a topological consequence: under the same RFF embedding, persistent homology is preserved in the sense that weighted Cech and Rips filtrations built from Gaussian kernel power distance are $(1\pm\varepsilon_\star)$-interleaved, where $\varepsilon_\star$ accounts for both distance distortion and kernel-weight approximation.
• Abstract（参考訳）: ガウス核は、カーネルPCAやスペクトルクラスタリングなどの基盤となるカーネルメソッドの類似度として広く使われているが、ガウス核距離を多くの点に対して計算することは高価である。 Random Fourier Features (RFF), Chen and Phillips [ALT 2017] を用いて、$$d$-dimensional Euclidean ball in ${\mathbb R}^N$, $t=Ω((d/\varepsilon^2)\log(dR/\varepsilon))$ feature suffice to keep all pairwise Gaussian kernel distances within a $(1\pm\varepsilon)$ factor with high probability。 固有次元 $d$ の任意の正リーハ部分多様体 $\mathcal M\subset{\mathbb R}^N$ のより一般的な設定に対する一様相対誤差埋め込み定理を確立する。 約$t=O((d/\varepsilon^2)\log(\operatorname{vol}(\mathcal M)^2N^{2d}/(\operatorname{vol}(B_1^d(0))^2\operatorname{rch}(\mathcal M)^{2d}\varepsilon^{2d+1}δ))$, or approximately $O((d^2/\varepsilon^2)(\log N+\log(1/(\varepsilonδ)))$, RFFs suffice, with probability $1-δ$。 したがって、境界は周囲次元と体積やリーチといった多様体のパラメータにのみ対数的に依存するが、1/\varepsilon^2$ユークリッドレートは維持される。 同様の RFF 埋め込みの下では、ガウス核のパワー距離から作られる重み付き Cech と Rips のフィルターは$(1\pm\varepsilon_\star)$-interleaved となる。

関連論文リスト

• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。 すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。 単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
  論文  参考訳（メタデータ） (2026-07-22T17:27:20Z)
• New Bounds for Kernel Sums via Fast Spherical Embeddings [12.14121214083427]
  新たに$tilde O(d+varepsilon2+1/varepsilon3)$を証明した。 証明の中心には、Bartal, Recht and Schulman (2011) によって導入された意味での新しい高速球面埋め込み定理があり、埋め込みデータ直径を制限している。
  論文  参考訳（メタデータ） (2026-05-02T05:42:50Z)
• Permanents of matrix ensembles: computation, distribution, and geometry [0.0]
  我々はGPUを使用して、$mathbbC,$mathbbR,$ $mathbbF_p$および$mathbbQ.$以上の永久体の計算を劇的に高速化する。 我々は、一元群における恒久的な測地学について研究する。 恒等式から$n$-サイクル置換行列への測地論について、普遍スケーリング関数 $f(t)=frac1nln|perm((t))|$ は$n$ in とは独立である。
  論文  参考訳（メタデータ） (2026-02-08T22:31:42Z)
• Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior [28.71736321665378]
  一次元のガウス的位置混合に対する非パラメトリック最大度推定器$widehatpi$について検討する。 We provide a algorithm that for small enough $varepsilon>0$ computes a $varepsilon$-approximation of $widehatpi in Wasserstein distance。 また、$k$-atomicと条件付けられた$widehatpi$の分布は、関連する2k-1$次元パラメータ空間上の密度を許容することを示す。
  論文  参考訳（メタデータ） (2025-03-26T03:36:36Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Dimension-Independent Kernel ε-Covers [8.234735564035567]
  カーネル範囲空間は、X の部分集合 mathbbRd$ の集合と、固定されたカーネルによる全てのクエリの空間に関する。 カーネルレンジ空間に対して$varepsilon$-coverという概念を導入する。
  論文  参考訳（メタデータ） (2023-06-28T19:19:33Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Non-asymptotic spectral bounds on the $\varepsilon$-entropy of kernel classes [4.178980693837599]
  この話題は、カーネルベースの手法の現代的な統計理論において重要な方向である。 我々は、我々の境界の多くの結果について議論し、それらが一般のカーネルのバウンドよりもかなり厳密であることを示す。
  論文  参考訳（メタデータ） (2022-04-09T16:45:22Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• 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)
• Kernel Thinning [26.25415159542831]
  カーネルの薄型化は、サンプリングや標準的な薄型化よりも効率的に$mathbbP$を圧縮するための新しい手順である。 我々は、ガウス、マタン、およびB-スプライン核に対する明示的な非漸近的な最大誤差境界を導出する。
  論文  参考訳（メタデータ） (2021-05-12T17:56:42Z)
• 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)

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

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