# Impossibility of latent inner product recovery via rate distortion

arXiv: https://arxiv.org/abs/2407.11932 · HTML: https://mlsanity.com/paper/2407.11932/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 32 references that are in the map.
- First posted on arXiv 16 Jul 2024.

## Builds on (most cited first, 10 of 10)

- [A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion](https://mlsanity.com/paper/1309.6013/) (2013)
- [Testing for high-dimensional geometry in random graphs](https://mlsanity.com/paper/1411.5713/) (2014)
- [1-bit Matrix Completion: PAC-Bayesian Analysis of a Variational Approximation](https://mlsanity.com/paper/1604.04191/) (2016)
- [Latent Distance Estimation for Random Geometric Graphs](https://mlsanity.com/paper/1909.06841/) (2019)
- [Phase Transitions for Detecting Latent Geometry in Random Graphs](https://mlsanity.com/paper/1910.14167/) (2019)
- [1-Bit Matrix Completion under Exact Low-Rank Constraint](https://mlsanity.com/paper/1502.06689/) (2015)
- [Spectral clustering in the Gaussian mixture block model](https://mlsanity.com/paper/2305.00979/) (2023)
- [Concentration properties of fractional posterior in 1-bit matrix completion](https://mlsanity.com/paper/2404.08969/) (2024)
- [Community detection and percolation of information in a geometric setting](https://mlsanity.com/paper/2006.15574/) (2020)
- [Information and dimensionality of anisotropic random geometric graphs](https://mlsanity.com/paper/1609.02490/) (2016)

## Built on by (most cited first, 1 of 1)

- [Recovery of latent inner products from an anisotropic Gaussian random geometric graph](https://mlsanity.com/paper/2607.23723/) (2026)

## Abstract (arXiv)

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.