Statistical Seriation

Tuesday, May 17, 2016 - 10:00am - 10:50am
Keller 3-180
Philippe Rigollet (Massachusetts Institute of Technology)
The seriation problem can be described as follows: given a matrix reorder its rows in such a ways that each column satisfies a shape constraint such as monotonicity or unimodality. It has direct applications in archeology, de novo genome assembly and ranking for example. While the problem has received recent attention from a computational point-of-view, most work has focused on the somewhat unrealistic noiseless case. We introduce a statistical version of the problem and study optimal rates of estimation in both the monotone and unimodal cases. We also present an efficient algorithm and point to a potential computational and statistical tradeoff of this problem.
[Joint with Nicolas Flammarion (ENS Paris) and Cheng Mao (MIT)]