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.003 seconds