# Localization in 1D non-parametric latent space models from pairwise affinities

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 46 references that are in the map.
- First posted on arXiv 6 Aug 2021.

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

- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons](https://mlsanity.com/paper/1504.07218/) (2015)
- [Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues](https://mlsanity.com/paper/1510.05610/) (2015)
- [Minimax Rates of Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1507.05313/) (2015)
- [Community Detection and Classification in Hierarchical Stochastic Blockmodels](https://mlsanity.com/paper/1503.02115/) (2015)
- [Network Cross-Validation for Determining the Number of Communities in Network Data](https://mlsanity.com/paper/1411.1715/) (2014)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [Convex Relaxations for Permutation Problems](https://mlsanity.com/paper/1306.4805/) (2013)
- [On estimation and inference in latent structure random graphs](https://mlsanity.com/paper/1806.01401/) (2018)
- [Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning](https://mlsanity.com/paper/1810.09569/) (2018)
- [Reconstruction of Line-Embeddings of Graphons](https://mlsanity.com/paper/2007.06444/) (2020)
- [Exact Minimax Estimation for Phase Synchronization](https://mlsanity.com/paper/2010.04345/) (2020)
- [Reconstructing Latent Orderings by Spectral Clustering](https://mlsanity.com/paper/1807.07122/) (2018)
- [A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models](https://mlsanity.com/paper/1411.1469/) (2014)
- [Learning random points from geometric graphs or orderings](https://mlsanity.com/paper/1809.09879/) (2018)

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

- [Detection-Recovery Gap for Planted Dense Cycles](https://mlsanity.com/paper/2302.06737/) (2023)
- [Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms](https://mlsanity.com/paper/2201.06438/) (2022)
- [Information-Theoretic Thresholds for Planted Dense Cycles](https://mlsanity.com/paper/2402.00305/) (2024)
- [Matching Map Recovery with an Unknown Number of Outliers](https://mlsanity.com/paper/2210.13354/) (2022)
- [Estimating the history of a random recursive tree](https://mlsanity.com/paper/2403.09755/) (2024)
- [Active Seriation: Efficient Ordering Recovery with Statistical Guarantees](https://mlsanity.com/paper/2603.15336/) (2026)
- [Node Regression on Latent Position Random Graphs via Local Averaging](https://mlsanity.com/paper/2410.21987/) (2024)

## Abstract (arXiv)

We consider the problem of estimating latent positions in a one-dimensional torus from pairwise affinities. The observed affinity between a pair of items is modeled as a noisy observation of a function f(x^*i,x^*j) of the latent positions x^*i,x^*j of the two items on the torus. The affinity function f is unknown, and it is only assumed to fulfill some shape constraints ensuring that f(x,y) is large when the distance between x and y is small, and vice-versa. This non-parametric modeling offers a good flexibility to fit data. We introduce an estimation procedure that provably localizes all the latent positions with a maximum error of the order of √log(n)/n, with high-probability. This rate is proven to be minimax optimal. A computationally efficient variant of the procedure is also analyzed under some more restrictive assumptions. Our general results can be instantiated to the problem of statistical seriation, leading to new bounds for the maximum error in the ordering.