論文の概要: Repeated Averages on Graphs
- arxiv url: http://arxiv.org/abs/2205.04535v1
- Date: Mon, 9 May 2022 20:18:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-13 20:10:44.958763
- Title: Repeated Averages on Graphs
- Title（参考訳）: グラフ上の繰り返し平均
- Authors: Ramis Movassagh, Mario Szegedy, Guanyang Wang
- Abstract要約: 我々は$frac(1-epsilon)2log2nlog n-O(n)$が$n$ノード上のすべての連結グラフに対する一般的な下界であることを証明する。
また、星、膨張星、ダンベル、サイクルなど、いくつかの重要なグラフの族に対して、$t_epsilon,1$の急激な等級も得られる。
- 参考スコア（独自算出の注目度）: 2.363388546004777
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Sourav Chatterjee, Persi Diaconis, Allan Sly and Lingfu Zhang, prompted by a
question of Ramis Movassagh, renewed the study of a process proposed in the
early 1980s by Jean Bourgain. A state vector $v \in \mathbb R^n$, labeled with
the vertices of a connected graph, $G$, changes in discrete time steps
following the simple rule that at each step a random edge $(i,j)$ is picked and
$v_i$ and $v_j$ are both replaced by their average $(v_i+v_j)/2$. It is easy to
see that the value associated with each vertex converges to $1/n$. The question
was how quickly will $v$ be $\epsilon$-close to uniform in the $L^{1}$ norm in
the case of the complete graph, $K_{n}$, when $v$ is initialized as a standard
basis vector that takes the value 1 on one coordinate, and zeros everywhere
else. They have established a sharp cutoff of $\frac{1}{2\log 2}n\log n +
O(n\sqrt{\log n})$. Our main result is to prove, that
$\frac{(1-\epsilon)}{2\log2}n\log n-O(n)$ is a general lower bound for all
connected graphs on $n$ nodes. We also get sharp magnitude of $t_{\epsilon,1}$
for several important families of graphs, including star, expander, dumbbell,
and cycle. In order to establish our results we make several observations about
the process, such as the worst case initialization is always a standard basis
vector. Our results add to the body of work of Aldous, Aldous and Lanoue,
Quattropani and Sau, Cao, Olshevsky and Tsitsiklis, and others. The renewed
interest is due to an analogy to a question related to the Google's supremacy
circuit. For the proof of our main theorem we employ a concept that we call
'augmented entropy function' which may find independent interest in the
computer science and probability theory communities.
- Abstract（参考訳）: Sourav Chatterjee、Persi Diaconis、Allan Sly、Lingfu ZhangはRamis Movassaghの質問に刺激され、1980年代初頭にJean Bourgainによって提案されたプロセスの研究を再考した。
連結グラフの頂点でラベル付けされた状態ベクトル $v \in \mathbb R^n$, $G$ は、各ステップのランダムエッジ $(i,j)$ が選択され、$v_i$ と $v_j$ がそれぞれ平均 $(v_i+v_j)/2$ に置き換えられるという単純な規則に従って離散時間ステップを変更する。
それぞれの頂点に関連する値が1/n$に収束することが容易にわかる。
問題は、完全グラフの場合の$l^{1}$ノルムにおいて、$v$がいかに早く$\epsilon$-close になるか、$k_{n}$ である。
彼らは $\frac{1}{2\log 2}n\log n + O(n\sqrt{\log n})$ の急切断を確立した。
我々の主な結果は、$\frac{(1-\epsilon)}{2\log2}n\log n-O(n)$が$n$ノード上のすべての連結グラフに対する一般の下界であることを証明することである。
また、star、expander、dambell、cycleといった重要なグラフのファミリーに対して、$t_{\epsilon,1}$という鋭いマグニチュードが得られます。
結果を確立するために、最悪の場合の初期化は常に標準基底ベクトルであるなど、プロセスに関するいくつかの観察を行う。
私たちの結果は、aldous、aldous、lanoue、quattropani、sau、cao、olshevsky、tsitsiklisなどの作品の本体に加えています。
新たな関心は、Googleの超越性回路に関する質問に類似しているためである。
主定理の証明には、「拡張エントロピー関数」と呼ばれる概念を使い、コンピュータ科学と確率論のコミュニティに独立した関心を抱くかもしれない。
関連論文リスト
- Low-degree Security of the Planted Random Subgraph Problem [12.329446579556606]
植付されたランダムな部分グラフを最大$kleq n1 - Omega(1)$まで検出する際の低次硬さを証明した。
我々は,(1) ランダム関数のための通信最適化多元的PSMプロトコル,(2) 共有サイズが$(1 + epsilon)log n$ for any $epsilon > 0$ に対して,最大$r$の任意の最小限の連立関係を再構築し,最大$ell = o(epsilon log n)1/(r-1)$までの未定部分集合に対して秘密保持する,という予想を適用した。
論文 参考訳（メタデータ） (2024-09-24T16:42:00Z) - 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) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳（メタデータ） (2023-03-10T00:11:18Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。
重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
論文 参考訳（メタデータ） (2021-11-02T05:26:10Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。
これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
論文 参考訳（メタデータ） (2021-10-11T05:07:50Z) - Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
グリーンガードとロークリンの有名な高速多重極法における次元$dの指数的依存は改善できないことを示す。
これは高速多重極法について証明された最初の公式な制限である。
論文 参考訳（メタデータ） (2020-11-04T18:35:02Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。