  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.
