論文の概要: A (simple) classical algorithm for estimating Betti numbers

• arxiv url: http://arxiv.org/abs/2211.09618v1
• Date: Thu, 17 Nov 2022 16:10:47 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-19 06:50:43.469470
• Title: A (simple) classical algorithm for estimating Betti numbers
• Title（参考訳）: ベッチ数推定のための(単純)古典的アルゴリズム
• Authors: Simon Apers, Sayantan Sen, D\'aniel Szab\'o
• Abstract要約: 我々は、$k$-th正規化ベッチ数を$n$要素上の単純複素数として推定する単純なアルゴリズムを記述する。 一般の単純複素数に対して、我々のアルゴリズムの実行時間は$nO(frac1gammalogfrac1varepsilon)$で、スペクトルギャップを測る$gamma$である。 傾斜複体の場合、我々のアルゴリズムの実行時間は$(n/lambda_max)O(frac1gammalogfrac1vareps)に改善される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We describe a simple algorithm for estimating the $k$-th normalized Betti number of a simplicial complex over $n$ elements using the path integral Monte Carlo method. For a general simplicial complex, the running time of our algorithm is $n^{O(\frac{1}{\gamma}\log\frac{1}{\varepsilon})}$ with $\gamma$ measuring the spectral gap of the combinatorial Laplacian and $\varepsilon \in (0,1)$ the additive precision. In the case of a clique complex, the running time of our algorithm improves to $(n/\lambda_{\max})^{O(\frac{1}{\gamma}\log\frac{1}{\varepsilon})}$ with $\lambda_{\max} \geq k$ the maximum eigenvalue of the combinatorial Laplacian. Our algorithm provides a classical benchmark for a line of quantum algorithms for estimating Betti numbers, and it matches their running time on clique complexes when the spectral gap is constant and $k \in \Omega(n)$ or $\lambda_{\max} \in \Omega(n)$.
• Abstract（参考訳）: 経路積分モンテカルロ法を用いて、$k$-th正規化ベッチ数を$n$要素上の単純複素数として推定する簡単なアルゴリズムを記述する。 一般の単純複素数に対して、我々のアルゴリズムの実行時間は$n^{O(\frac{1}{\gamma}\log\frac{1}{\varepsilon})}$と$\gamma$は組合せラプラシアンのスペクトルギャップを測り、$\varepsilon \in (0,1)$は加法精度である。 斜交複素体の場合、我々のアルゴリズムの実行時間は$(n/\lambda_{\max})^{O(\frac{1}{\gamma}\log\frac{1}{\varepsilon})}$ with $\lambda_{\max} \geq k$ the maximum eigenvalue of the combinatorial Laplacian。 我々のアルゴリズムはベッチ数を推定する量子アルゴリズムの行に対して古典的なベンチマークを提供し、スペクトルギャップが一定で、$k \in \Omega(n)$ または $\lambda_{\max} \in \Omega(n)$ の場合には、それらのランニングタイムをクリッドコンプレックス上で一致させる。

関連論文リスト

• Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
  潜在変数モデル学習の課題について検討する。 このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。 一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
  論文  参考訳（メタデータ） (2024-11-23T23:13:24Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems [11.929584800629673]
  線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。 我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
  論文  参考訳（メタデータ） (2023-07-13T08:46:19Z)
• Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
  我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。 私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
  論文  参考訳（メタデータ） (2023-06-05T12:22:46Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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