| 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 π. |