Optimal rates of statistical seriation
Optimal rates of statistical seriation
复制标题
DOI：
10.3150/17-bej1000
复制
发表时间：
2019-02-01
期刊：
影响因子：
1.5
通讯作者：
Rigollet, Philippe
中科院分区：
文献类型：
--
作者：
Flammarion, Nicolas;Mao, Cheng;Rigollet, Philippe
给定一个矩阵，序列化问题在于对其行进行排列，使其所有列具有相同的形状，例如，它们是单调递增的。我们提出了一种解决这个问题的统计方法，其中用噪声观察感兴趣的矩阵，并研究相应的矩阵估计的极小极大率。具体来说，当列是单峰或单调时，我们表明最小二乘估计量在对数因子上是最优的，并且适应具有特定自然结构的矩阵。最后，我们在单调情况下提出了一种计算高效的估计器，并从理论上和实验上研究了其性能。我们的工作是形状约束估计和最近涉及排列学习的工作的交叉点，例如图去噪和排序。
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.