Consistency of the Spectral Seriation Algorithm

Abstract

Given n arbitrary objects x1, x2, . . . , xn and a similarity matrix P = (pi,j ) 1≤i,j≤n , where pi,j measures the similarity between xi and xj . If the objects can be ordered along a linear chain so that the similarity decreases as the distance increase within this chain, then the goal of the seriation problem is to recover this ordering π given only the similarity matrix. When the data matrix P is completely accurate, the true relative order can be recovered from the spectral seriation algorithm [1]. In most applications, the matrix P is noisy, but the basic spectral seriation algorithm is still very popular. In this thesis, we study the consistency of this algorithm for a wide variety of statistical models, showing both consistency and bounds on the convergence rates. More specifically, we consider a model matrix P satisfying certain assumptions, and construct a noisy matrix Pb where the input (i, j) is a coin flip with probability pi,j . We show that the output πˆ of the spectral seriation algorithm for the random matrix is very close to the true ordering π.