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 π.
Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/39681 |
Date | 01 October 2019 |
Creators | Natik, Amine |
Contributors | Smith, Aaron |
Publisher | Université d'Ottawa / University of Ottawa |
Source Sets | Université d’Ottawa |
Language | English |
Detected Language | English |
Type | Thesis |
Format | application/pdf |
Page generated in 0.0015 seconds