Motivated by applications in archeology for relative dating of objects, or in 2D-tomography for angular synchronization, we consider the problem of statistical seriation where one seeks to reorder a noisy disordered matrix of pairwise affinities. This problem can be recast in the powerful latent space terminology where the affinity between a pair of items is modeled as a noisy observation of a function f(x_i,x_j) of the latent points x_i, x_j of the two items in a one-dimensional space. This reformulation naturally leads to the problem of estimating the latent positions in the latent space. Under non-parametric assumptions on the affinity function f, we introduce a procedure that provably localizes all the latent positions with a maximum error of the order of the square root of log(n)/n. This rate is proven to be minimax optimal. Different computationally efficient procedures are also analyzed, under different set of assumptions. Our general results can be instantiated to the original problem of statistical seriation, leading to new bounds for the maximum error in the ordering.
