Fetching the paper…

Reading the bibliography…

2016

Information and dimensionality of anisotropic random geometric graphs

Eldan, Ronen, Mikulincer, Dan

Original
PDF
Post on X

Understand

This paper deals with the problem of detecting non-isotropic high-dimensional geometric structure in random graphs.

Namely, we study a model of a random geometric graph in which vertices correspond to points generated randomly and independently from a non-isotropic $d$-dimensional Gaussian distribution, and two vertices are connected if the distance between them is smaller than some pre-specified threshold.
We derive new notions of dimensionality which depend upon the eigenvalues of the covariance of the Gaussian distribution.
If $\alpha$ denotes the vector of eigenvalues, and $n$ is the number of vertices, then the quantities $\left(\frac{||\alpha||_2}{||\alpha||_3}\right)^6/n^3$ and $\left(\frac{||\alpha||_2}{||\alpha||_4}\right)^4/n^3$ determine upper and lower bounds for the possibility of detection.

Information and dimensionality of anisotropic random geometric graphs · Around

Built on

On the evolution of random graphs
Erdős, P., and Rényi, A · 1960
Earlier work this paper cites.
From characteristic function to distribution function: a simple framework for the theory
Shephard, N. G · 1991
Earlier work this paper cites.
Limit Theorems of Probability Theory
Petrov, V. V · 1995
Earlier work this paper cites.
A lyapunov-type bound in R d R^{d}
Bentkus, V · 2005
Earlier work this paper cites.
Derivations for linear algebra and optimization
Duchi, J · 2007
Earlier work this paper cites.

Similar

Chapter 8: The wishart distribution
Eaton, M. L · 2007
Cited alongside, same era.
Banach-Mazur distances and projections on random subgaussian polytopes
Latala, R., Mankiewicz, P., Oleszkiewicz, K., and Tomczak-Jaegermann, N · 2007
Cited alongside, same era.
Probability: theory and examples
Durrett, R · 2010
Cited alongside, same era.
Elements of information theory
Cover, T. M., and Thomas, J. A · 2012
Cited alongside, same era.
Normal approximations with Malliavin calculus: from Stein’s method to universality
Nourdin, I., and Peccati, G · 2012
Cited alongside, same era.

Then

Topics in random matrix theory
Tao, T · 2012
Later among the works it cites.
Introduction to the non-asymptotic analysis of random matrices
Original
Vershynin, R · 2012
Later among the works it cites.
The analysis of linear partial differential operators I: Distribution theory and Fourier analysis
Hörmander, L · 2015
Later among the works it cites.
Testing for high-dimensional geometry in random graphs
Bubeck, S., Ding, J., Eldan, R., and Rácz, M. Z · 2016
Closest in time.
Entropic CLT and phase transition in high-dimensional Wishart matrices
Bubeck, S., and Ganguly, S · 2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…