### Consistency of the Spectral Seriation Algorithm

FieldValue
dc.contributor.authorNatik, Amine
dc.date.accessioned2019-10-01T17:14:09Z
dc.date.available2019-10-01T17:14:09Z
dc.date.issued2019-10-01
dc.identifier.urihttp://hdl.handle.net/10393/39681
dc.identifier.urihttp://dx.doi.org/10.20381/ruor-23924
dc.description.abstractGiven 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 π.
dc.language.isoen
dc.publisherUniversité d'Ottawa / University of Ottawa
dc.subjectseriation
dc.subjectRobinson similarities
dc.titleConsistency of the Spectral Seriation Algorithm
dc.typeThesis
dc.contributor.supervisorSmith, Aaron
thesis.degree.nameMSc
thesis.degree.levelMasters
thesis.degree.disciplineSciences / Science
uottawa.departmentMathématiques et statistique / Mathematics and Statistics
CollectionThèses, 2011 - // Theses, 2011 -