Impossibility of latent inner product recovery via rate distortion

In this largely expository note, we present an impossibility result for inner product recovery in a random geometric graph or latent space model using the rate-distortion theory. More precisely, suppose that we observe a graph A on n vertices with average edge density p generated from Gaussian or spherical latent locations z1, dots, zn ∈ ℝd associated with the n vertices. It is of interest to estimate the inner products langle zi, zj rangle which represent the geometry of the latent points. We prove that it is impossible to recover the inner products if d gtrsim n h(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 proof follows the well-established rate-distortion theory with the main technical ingredient being a lower bound on the rate-distortion function of the Wishart distribution which is interesting in its own right.