論文の概要: Fast $k$-means clustering in Riemannian manifolds via Fréchet maps: Applications to large-dimensional SPD matrices

• arxiv url: http://arxiv.org/abs/2511.08993v1
• Date: Thu, 13 Nov 2025 01:24:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-13 22:34:54.346514
• Title: Fast $k$-means clustering in Riemannian manifolds via Fréchet maps: Applications to large-dimensional SPD matrices
• Title（参考訳）: フレシェ写像によるリーマン多様体の高速$k$-meansクラスタリング:大次元SPD行列への応用
• Authors: Ji Shi, Nicolas Charon, Andreas Mang, Demetrio Labate, Robert Azencott,
• Abstract要約: 鍵となるイノベーションは、$p$-Fréchet map $Fp : MathcalM to mathbbRell$である。 ユークリッド空間における$Fp$の数学的性質を厳密に解析する。 本手法は, 固有多様体に基づく手法と比較して, 実行時間を最大2桁削減する。
• 参考スコア（独自算出の注目度）: 4.958499383330019
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a novel, efficient framework for clustering data on high-dimensional, non-Euclidean manifolds that overcomes the computational challenges associated with standard intrinsic methods. The key innovation is the use of the $p$-Fréchet map $F^p : \mathcal{M} \to \mathbb{R}^\ell$ -- defined on a generic metric space $\mathcal{M}$ -- which embeds the manifold data into a lower-dimensional Euclidean space $\mathbb{R}^\ell$ using a set of reference points $\{r_i\}_{i=1}^\ell$, $r_i \in \mathcal{M}$. Once embedded, we can efficiently and accurately apply standard Euclidean clustering techniques such as k-means. We rigorously analyze the mathematical properties of $F^p$ in the Euclidean space and the challenging manifold of $n \times n$ symmetric positive definite matrices $\mathit{SPD}(n)$. Extensive numerical experiments using synthetic and real $\mathit{SPD}(n)$ data demonstrate significant performance gains: our method reduces runtime by up to two orders of magnitude compared to intrinsic manifold-based approaches, all while maintaining high clustering accuracy, including scenarios where existing alternative methods struggle or fail.
• Abstract（参考訳）: 本稿では,高次元非ユークリッド多様体上のデータをクラスタリングする,新しい効率的なフレームワークを提案する。 鍵となる革新は、$p$-Fréchet map $F^p : \mathcal{M} \to \mathbb{R}^\ell$ -- 一般計量空間 $\mathcal{M}$ -- を用いて、多様体データを低次元ユークリッド空間 $\mathbb{R}^\ell$ に埋め込み、参照点 $\{r_i\}_{i=1}^\ell$, $r_i \in \mathcal{M}$ を用いることである。 組み込むと、k-meansのような標準的なユークリッドクラスタリング手法を効率よく正確に適用できる。 ユークリッド空間における$F^p$ の数学的性質と、$n \times n$対称正定行列の挑戦多様体 $\mathit{SPD}(n)$ を厳密に解析する。 我々の手法は,既存の代替手法が困難あるいは失敗するシナリオを含む,高いクラスタリング精度を維持しながら,固有の多様体ベースのアプローチと比較して,ランタイムを最大2桁まで削減する。

関連論文リスト

• Learnable Similarity and Dissimilarity Guided Symmetric Non-Negative Matrix Factorization [18.53944578996308]
  学習可能な重み付き$k$-NNグラフを構築し、各$k$-th NNの信頼性を反映する。 識別的類似度行列を得るために,類似度行列の二重構造を持つ相似性行列を導入する。 提案したモデルを解決するために,効率的な代替最適化アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-12-05T11:32:53Z)
• Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
  ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。 本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
  論文  参考訳（メタデータ） (2023-06-26T17:13:31Z)
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
  論文  参考訳（メタデータ） (2023-05-12T08:43:28Z)
• Dictionary Learning for the Almost-Linear Sparsity Regime [0.0]
  辞書学習は、信号処理やデータ科学における応用においてますます重要になっている。 SPORADIC (SPectral ORAcle DICtionary Learning) は、重み付けされた共分散行列の族に対する効率的なスペクトル法である。 高次元において、SPORADICはよく知られた制限等尺性(RIP)を満たす過剰完備(K > M$)辞書を復元できることを示す。 これらの精度保証は、未知のスパースベクトル $mathbfx_i$ の支持と符号が、高い確率で正確に復元され、任意に閉じることができるような「オラクル特性」を持つ。
  論文  参考訳（メタデータ） (2022-10-19T19:35:50Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• 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)
• An Online Riemannian PCA for Stochastic Canonical Correlation Analysis [37.8212762083567]
  投影行列の再パラメータ化を用いた正準相関解析(CCA)のための効率的なアルゴリズム(RSG+)を提案する。 本論文は,その特性の定式化と技術的解析に主眼を置いているが,本実験により,一般的なデータセットに対する経験的挙動が極めて有望であることが確認された。
  論文  参考訳（メタデータ） (2021-06-08T23:38:29Z)
• 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)
• 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)

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

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