論文の概要: Rapid Grassmannian Averaging with Chebyshev Polynomials

• arxiv url: http://arxiv.org/abs/2410.08956v1
• Date: Fri, 11 Oct 2024 16:25:06 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-30 20:56:20.165004
• Title: Rapid Grassmannian Averaging with Chebyshev Polynomials
• Title（参考訳）: Chebyshev polynomials による急速グラスマン平均値の検討
• Authors: Brighton Ancelin, Alex Saad-Falcon, Kason Ancelin, Justin Romberg,
• Abstract要約: 我々は、グラスマン多様体上の点の集合を集中的および分散的設定の両方で効率的に平均化する新しいアルゴリズムを提案する。 提案アルゴリズムであるRapid Grassmannian Averaging (RGrAv) とDecentralized Rapid Grassmannian Averaging (DRGrAv) は,この問題のスペクトル構造を利用して高速に平均を計算することでこの問題を克服する。 我々は,最適性の理論的保証と,我々のアルゴリズムが最小時間で高精度な解を提供することで最先端の手法より優れていることを示す数値実験を提供する。
• 参考スコア（独自算出の注目度）: 8.394689129416067
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose new algorithms to efficiently average a collection of points on a Grassmannian manifold in both the centralized and decentralized settings. Grassmannian points are used ubiquitously in machine learning, computer vision, and signal processing to represent data through (often low-dimensional) subspaces. While averaging these points is crucial to many tasks (especially in the decentralized setting), existing methods unfortunately remain computationally expensive due to the non-Euclidean geometry of the manifold. Our proposed algorithms, Rapid Grassmannian Averaging (RGrAv) and Decentralized Rapid Grassmannian Averaging (DRGrAv), overcome this challenge by leveraging the spectral structure of the problem to rapidly compute an average using only small matrix multiplications and QR factorizations. We provide a theoretical guarantee of optimality and present numerical experiments which demonstrate that our algorithms outperform state-of-the-art methods in providing high accuracy solutions in minimal time. Additional experiments showcase the versatility of our algorithms to tasks such as K-means clustering on video motion data, establishing RGrAv and DRGrAv as powerful tools for generic Grassmannian averaging.
• Abstract（参考訳）: 我々は、グラスマン多様体上の点の集合を集中的および分散的設定の両方で効率的に平均化する新しいアルゴリズムを提案する。 グラスマン点は機械学習、コンピュータビジョン、信号処理でユビキタスに使われ、(しばしば低次元の)部分空間を通してデータを表現している。 これらの点を平均化することは、多くのタスク(特に非集中的な環境では)にとって重要であるが、既存の手法は、多様体の非ユークリッド幾何学のため、残念ながら計算的に高価である。 提案アルゴリズムであるRapid Grassmannian Averaging (RGrAv) とDecentralized Rapid Grassmannian Averaging (DRGrAv) は、この問題のスペクトル構造を利用して、小さな行列乗算とQR因子化のみを用いて、平均を高速に計算する。 我々は,最適性の理論的保証と,我々のアルゴリズムが最小時間で高精度な解を提供することで最先端の手法より優れていることを示す数値実験を提供する。 追加実験では,ビデオモーションデータに基づくK平均クラスタリング,RGrAvとDRGrAvを汎用的なグラスマン平均化のための強力なツールとして確立した。

関連論文リスト

• The Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machines [1.738375118265695]
  本稿では,カーネルサポートベクトルマシン(SVM)に特化して設計された革新的な手法を提案する。 イテレーション毎のイテレーションを高速化するだけでなく、従来のSFO技術と比較して収束度も向上する。 実験の結果,提案アルゴリズムはSFO法のスケーラビリティを維持できるだけでなく,潜在的に超越していることが示された。
  論文  参考訳（メタデータ） (2024-07-30T17:03:19Z)
• A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
  サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。 我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-12-17T04:41:07Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming [25.210724274471914]
  K$-meansクラスタリングは、大規模なデータセットのパターンを識別する機械学習手法として広く使用されている。 本稿では,非負の低ランクな$K$-means分解問題を解くNMFライクなアルゴリズムについて考察する。 提案アルゴリズムは,スケーラビリティを維持しつつ,既存の最先端技術と比較して,誤クラスタリングエラーを著しく小さくする。
  論文  参考訳（メタデータ） (2023-05-29T00:39:55Z)
• Fast conformational clustering of extensive molecular dynamics simulation data [19.444636864515726]
  本稿では,長い軌道の高速なコンフォーメーションクラスタリングを実現するために,教師なしのデータ処理ワークフローを提案する。 我々は密度に基づく空間クラスタリングアルゴリズム(HDBSCAN)と2つの次元削減アルゴリズム(cc_analysisとEncodermap)を組み合わせる。 4つのテストシステムの助けを借りて、このクラスタリングワークフローの機能とパフォーマンスを説明します。
  論文  参考訳（メタデータ） (2023-01-11T14:36:43Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping [57.316437798033974]
  本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。 我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。 一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
  論文  参考訳（メタデータ） (2020-12-01T13:17:27Z)
• Kernel k-Means, By All Means: Algorithms and Strong Consistency [21.013169939337583]
  Kernel $k$クラスタリングは、非線形データの教師なし学習のための強力なツールである。 本稿では,最適化された局所解に対処するための一般的な手法を応用した結果を一般化する。 我々のアルゴリズムは、この非線形分離問題をよりよく解くために、Magricalization-minimization (MM) を利用している。
  論文  参考訳（メタデータ） (2020-11-12T16:07:18Z)
• Distributed Optimization, Averaging via ADMM, and Network Topology [0.0]
  センサローカライゼーションの現実問題において,ネットワークトポロジと異なるアルゴリズムの収束率の関係について検討する。 また、ADMMと持ち上げマルコフ連鎖の間の興味深い関係を示すとともに、その収束を明示的に特徴づける。
  論文  参考訳（メタデータ） (2020-09-05T21:44:39Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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