論文の概要: Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits

• arxiv url: http://arxiv.org/abs/2005.10743v4
• Date: Mon, 2 Oct 2023 18:27:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-05 11:31:02.696678
• Title: Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits
• Title（参考訳）: 植物構造をもつテンソルクラスタリング:統計的最適性と計算限界
• Authors: Yuetian Luo and Anru R. Zhang
• Abstract要約: 我々は2つのクラスタリングモデル、定数高階クラスタリング(CHC)とランク1高階クラスタリング(ROHC)に焦点を当てる。 我々は,CHCとROHCの検出/回復が統計的に可能である信号対雑音比の境界を同定する。 信号対雑音比がしきい値以上である場合に、信頼性の高い検出と回復を実現するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 9.427635404752936
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: This paper studies the statistical and computational limits of high-order clustering with planted structures. We focus on two clustering models, constant high-order clustering (CHC) and rank-one higher-order clustering (ROHC), and study the methods and theory for testing whether a cluster exists (detection) and identifying the support of cluster (recovery). Specifically, we identify the sharp boundaries of signal-to-noise ratio for which CHC and ROHC detection/recovery are statistically possible. We also develop the tight computational thresholds: when the signal-to-noise ratio is below these thresholds, we prove that polynomial-time algorithms cannot solve these problems under the computational hardness conjectures of hypergraphic planted clique (HPC) detection and hypergraphic planted dense subgraph (HPDS) recovery. We also propose polynomial-time tensor algorithms that achieve reliable detection and recovery when the signal-to-noise ratio is above these thresholds. Both sparsity and tensor structures yield the computational barriers in high-order tensor clustering. The interplay between them results in significant differences between high-order tensor clustering and matrix clustering in literature in aspects of statistical and computational phase transition diagrams, algorithmic approaches, hardness conjecture, and proof techniques. To our best knowledge, we are the first to give a thorough characterization of the statistical and computational trade-off for such a double computational-barrier problem. Finally, we provide evidence for the computational hardness conjectures of HPC detection (via low-degree polynomial and Metropolis methods) and HPDS recovery (via low-degree polynomial method).
• Abstract（参考訳）: 本稿では,植込み構造を用いた高次クラスタリングの統計的および計算的限界について検討する。 我々は,2つのクラスタリングモデル,constant high-order clustering(chc)とrank-one higher-order clustering(rohc)に注目し,クラスタの存在(検出)とクラスタのサポートの同定(回復)の方法と理論について検討した。 具体的には,CHCとROHCの検出/回復が統計的に可能である信号対雑音比の鋭い境界を同定する。 信号-雑音比がこれらのしきい値以下である場合、多項式時間アルゴリズムは、ハイパーグラフィックプランドclique(HPC)検出とハイパーグラフィックプランド高密度サブグラフ(HPDS)回復の計算硬度予測の下でこれらの問題を解くことができないことを証明している。 また,信号対雑音比がしきい値以上である場合に,信頼性の高い検出と回復を実現する多項式時間テンソルアルゴリズムを提案する。 疎度とテンソル構造の両方が高次テンソルクラスタリングの計算障壁となる。 それらの相互作用は、統計および計算相転移図、アルゴリズムアプローチ、硬さ予想、証明技術といった分野における文献における高階テンソルクラスタリングと行列クラスタリングの間に大きな違いをもたらす。 我々の知る限り、このような二重計算バリア問題に対する統計的および計算的トレードオフの徹底的な評価を最初に行った。 最後に,hpc検出(低次多項式法とメトロポリス法)とhpds回復(低次多項式法)の計算硬さ予想の証拠を提供する。

関連論文リスト

• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• Maximum Likelihood Estimation on Stochastic Blockmodels for Directed Graph Clustering [22.421702511126373]
  我々は、有向ブロックモデルにおいて、基盤となるコミュニティを推定するものとしてクラスタリングを定式化する。 本稿では,2つの効率的かつ解釈可能な有向クラスタリングアルゴリズム,スペクトルクラスタリングアルゴリズム,半定値プログラミングに基づくクラスタリングアルゴリズムを紹介する。
  論文  参考訳（メタデータ） (2024-03-28T15:47:13Z)
• Heteroskedastic Tensor Clustering [20.979358557219953]
  我々は、$mathsfHightext-orderHeteroClustering$$mathsfHHC$という2段階の手法を提案する。 まず、$mathsfThresholdedDeflatedtext-HeteroPCA$と呼ばれる新しいスペクトルアルゴリズムを使ってテンソル部分空間の推定を行い、続いてクラスタノードを取得するためにおよそ$k$-meansを実行する。 我々のアルゴリズムは、SNRが計算限界を超える限り、正確なクラスタリングを確実に達成する。
  論文  参考訳（メタデータ） (2023-11-04T02:50:40Z)
• Multiway Spherical Clustering via Degree-Corrected Tensor Block Models [8.147652597876862]
  推定精度を保証した次数補正ブロックモデルを開発した。 特に,3次以上のテンソルに対してのみ,本質的な統計的-計算的ギャップが生じることを示す。 本手法の有効性を2つのデータアプリケーションを用いて実証した。
  論文  参考訳（メタデータ） (2022-01-19T03:40:22Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Riemannian classification of EEG signals with missing values [67.90148548467762]
  本稿では脳波の分類に欠落したデータを扱うための2つの方法を提案する。 第1のアプローチでは、インプットされたデータと$k$-nearestの隣人アルゴリズムとの共分散を推定し、第2のアプローチでは、期待最大化アルゴリズム内で観測データの可能性を活用することにより、観測データに依存する。 その結果, 提案手法は観測データに基づく分類よりも優れており, 欠落したデータ比が増大しても高い精度を維持することができることがわかった。
  論文  参考訳（メタデータ） (2021-10-19T14:24:50Z)
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit [10.8145995157397]
  高階クラスタリングは、マルチウェイデータセットの異種サブ構造を特定することを目的とする。 非計算と問題の性質は統計学と統計学の両方に重大な課題をもたらす。
  論文  参考訳（メタデータ） (2020-12-18T00:48:27Z)
• (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping [57.316437798033974]
  本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。 我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。 一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
  論文  参考訳（メタデータ） (2020-12-01T13:17:27Z)
• Statistical and computational thresholds for the planted $k$-densest sub-hypergraph problem [13.808053718325635]
  我々は,$d$-uniform ハイパーグラフ上に$k$-densest サブハイパーグラフを植え付けることで回復する問題を考察する。 この根本的な問題は、例えば、コミュニティの検出、平均ケースの複雑さ、神経科学の応用など、様々な文脈に現れる。
  論文  参考訳（メタデータ） (2020-11-23T16:02:12Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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