Impossibility of Latent Inner Product Recovery via Rate Distortion
Cheng Mao, Shenduo Zhang · 2024
In a random geometric graph model or latent space model, the observed graph$A$on$n$vertices with average edge density$p$is assumed to be generated from latent locations$z_{1}, \ldots, z_{n}$in$\mathbb{R}^{d}$associated with the$n$vertices. Given the graph$A$, it is of interest to estimate the inner products$\langle z_{i}, z_{j}\rangle$which represents the geometry of the latent locations. In this note, assuming that the latent locations are Gaussian or spherical points, we show an impossibility result for inner product recovery when$d\asymp nh(p)$where$h(p)$is the binary entropy function. This matches the condition required for positive results on inner product recovery in the literature. The main technical ingredient of this work is a lower bound on the rate-distortion function of the Wishart distribution which is interesting in its own right.