Optimal rates of statistical seriation
By Nicolas Flammarion, Cheng Mao, Philippe Rigollet. Bernoulli, 2016
65 citations recorded by the source corpus.
Given a matrix the seriation problem consists in permuting its rows in such way that all its columns have the same shape, for example, they are monotone increasing. We propose a statistical approach to this problem where the matrix of interest is observed with noise and study the corresponding minimax rate of estimation of the matrices. Specifically, when the columns are either unimodal or monotone, we show that the least squares estimator is optimal up to logarithmic factors and adapts to matrices with a certain natural structure. Finally, we propose a computationally efficient estimator in the monotonic case and study its performance both theoretically and experimentally. Our work is at the intersection of shape constrained estimation and recent work that involves permutation learning, such as graph denoising and ranking.
Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition
View Paper: https://www.semanticscholar.org/paper/4dc4c582c9880acfdc4ec4447857b9463e87ad92
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computational Mechanics
- Adityanand Guntuboyina
- Bodhisattva Sen
- Emanuel Ben-David
- Martin Slawski
- Pierre C. Bellec
- Richard J. Samworth
- Yining Chen
- Sabyasachi Chatterjee
In Computer Vision and Pattern Recognition
Citations in the corpus
- Nonparametric Shape-Restricted Regression (2017, background): “Estimation of bivariate coordinate-wise nondecreasing functions has applications and connections to the problem of estimating matrices of pairwise comparison probabilities arising from pairwise comparison data ([32, 123]) and to seriation ([47]).”
- Linear regression with sparsely permuted data (2017, background): “In recent years, computer science and engineering have witnessed a surge of interest in regression analysis of permuted data resulting from problems in multitarget tracking, statistical seriation [26], and unlabeled compressed sensing [53], to mention just a few.”