論文の概要: New Coresets for Projective Clustering and Applications

• arxiv url: http://arxiv.org/abs/2203.04370v1
• Date: Tue, 8 Mar 2022 19:50:27 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-10 16:20:55.758733
• Title: New Coresets for Projective Clustering and Applications
• Title（参考訳）: プロジェクティブクラスタリングとアプリケーションのための新しいコアセット
• Authors: Murad Tukan and Xuan Wu and Samson Zhou and Vladimir Braverman and Dan Feldman
• Abstract要約: 点集合$P$ in $mathbbRd$ が与えられたとき、ゴールは次元$j$、すなわちアフィン部分空間が与えられた距離測度の下で最もよく適合する$k$フラットを見つけることである。 我々は、コーシー、ヴェルシュ、フーバー、ゲマン・マククリール、テューキー、$L_infty$、フェアレグレッションに対して効率的なコアセット構成を提供することを示した。
• 参考スコア（独自算出の注目度）: 34.82221047030618
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: $(j,k)$-projective clustering is the natural generalization of the family of $k$-clustering and $j$-subspace clustering problems. Given a set of points $P$ in $\mathbb{R}^d$, the goal is to find $k$ flats of dimension $j$, i.e., affine subspaces, that best fit $P$ under a given distance measure. In this paper, we propose the first algorithm that returns an $L_\infty$ coreset of size polynomial in $d$. Moreover, we give the first strong coreset construction for general $M$-estimator regression. Specifically, we show that our construction provides efficient coreset constructions for Cauchy, Welsch, Huber, Geman-McClure, Tukey, $L_1-L_2$, and Fair regression, as well as general concave and power-bounded loss functions. Finally, we provide experimental results based on real-world datasets, showing the efficacy of our approach.
• Abstract（参考訳）: $(j,k)$-プロジェクティブクラスタリングは、$k$-クラスタリングと$j$-サブスペースクラスタリングのファミリーの自然な一般化である。 p$ in $\mathbb{r}^d$ の点が与えられると、目標は、与えられた距離測度の下で最大に p$ に合致する次元 $j$(すなわちアフィン部分空間)の k$ 平面を見つけることである。 本稿では、サイズ多項式の$l_\infty$coresetを$d$で返す最初のアルゴリズムを提案する。 さらに、一般の$M$-推定器回帰に対する最初の強いコアセット構成を与える。 具体的には,cauchy,welsch,huber,geman-mcclure,tukey,$l_1-l_2$,フェアレグレッション,一般的なコンケーブとパワーバウンド損失関数の効率的なコアセット構成を提供することを示す。 最後に,実世界のデータセットに基づく実験結果を提供し,提案手法の有効性を示す。

関連論文リスト

• Clustering to Minimize Cluster-Aware Norm Objectives [0.3481985817302898]
  与えられたデータセットの$P$を$k$クラスタに分割し、$X$の$k$センターを見つける。 中心の$xin X$で表されるクラスタのコストは、x$に割り当てられた点の距離のベクトルの単調で対称なノルム$f$(インナーノルム)である。 目標は、クラスタコストのベクトルのノルム$g$(外部ノルム)を最小化することである。
  論文  参考訳（メタデータ） (2024-10-31T16:33:40Z)
• Multilayer Correlation Clustering [12.492037397168579]
  相関クラスタリング(Bansal et al., FOCS '02)の新たな一般化である多層相関クラスタリングを確立する。 本稿では、共通集合である$V$に対して相関クラスタリング(層と呼ばれる)の一連の入力を与えられる。 目的は、不一致ベクトルの$ell_p$-norm(pgeq 1$)を最小化する$V$のクラスタリングを見つけることである。
  論文  参考訳（メタデータ） (2024-04-25T15:25:30Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• 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)
• Universal Weak Coreset [3.1509756165776635]
  弱コアセットは点の部分集合の対$(J,S)$であり、そこでは点集合の要約として$S$が作用し、ポテンシャル中心の集合として$J$が作用する。 我々は、制約付きクラスタリング設定のために、ユニバーサル弱コアセットと呼ばれるこのフレームワークを開発した。
  論文  参考訳（メタデータ） (2023-05-26T12:51:16Z)
• 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)
• Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering [13.208510864854894]
  ランダム次元削減は高次元問題に対するアルゴリズムを高速化するための多用途ツールである。 本稿では,施設配置問題と単一リンク階層クラスタリング問題という2つのクラスタリング問題への適用について検討する。
  論文  参考訳（メタデータ） (2021-07-05T05:55:26Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• 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)
• Deep Learning Meets Projective Clustering [66.726500395069]
  NLPネットワークを圧縮するための一般的なアプローチは、埋め込み層を行列 $AinmathbbRntimes d$ としてエンコードすることである。 計算幾何学から遠射的クラスタリングに着想を得て、この部分空間を$k$部分空間の集合で置き換えることを提案する。
  論文  参考訳（メタデータ） (2020-10-08T22:47:48Z)

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

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