EUVIMEDEUVIMED entdecken
Crossref

Application of the information-percolation method to reconstruction problems on graphs

Yury Polyanskiy, Yihong Wu

Mathematical Statistics and Learning · 2020

DOI: 10.4171/msl/10 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematical Statistics and Learning, 2020. Verfasst von Yury Polyanskiy und 1 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this paper we propose a method of proving impossibility results based on applying strong data-processing inequalities to estimate mutual information between sets of variables forming certain Markov random fields. The end result is that mutual information between two “far away” (as measured by the graph distance) variables is bounded by the probability of the existence of an open path in a bond-percolation problem on the same graph. Furthermore, stronger bounds can be obtained by establishing mutual information comparison results with an erasure model on the same graph, with erasure probabilities given by the contraction coefficients. As applications, we show that our method gives sharp threshold for partially recovering a rank-one perturbation of a random Gaussian matrix (spiked Wigner model), yields the best known upper bound on the noise level for group synchronization (obtained concurrently by Abbe and Boix), and establishes new impossibility result for community detection on the stochastic block model with k communities.

Zitieren

APA

Polyanskiy, Y., & Wu, Y. (2020). Application of the information-percolation method to reconstruction problems on graphs. Mathematical Statistics and Learning. https://doi.org/10.4171/msl/10

Vancouver

Polyanskiy Y, Wu Y. Application of the information-percolation method to reconstruction problems on graphs. Mathematical Statistics and Learning. 2020. doi:10.4171/msl/10

BibTeX
@article{Polyanskiy2020,
  author = {Polyanskiy, Yury and Wu, Yihong},
  title = {Application of the information-percolation method to reconstruction problems on graphs},
  journal = {Mathematical Statistics and Learning},
  year = {2020},
  doi = {10.4171/msl/10}
}
Kostenlos starten →