Impossibility of latent inner product recovery via rate distortion
<|reference_start|>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 $z_1, \dots, z_n \in \mathbb{R}^d$ associated with the $n$ vertices. It is of interest to estimate the inner products $\langle z_i, z_j \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.<|reference_end|>
@article{mao2024impossibility,
    title={Impossibility of latent inner product recovery via rate distortion},
    author={Cheng Mao, Shenduo Zhang},
    journal={arXiv preprint arXiv:2407.11932},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.11932},
    primaryClass={math.ST cs.IT cs.SI math.IT stat.ML stat.TH}
}