论文标题
噪声无序矩阵的矩阵重新排序：最佳和计算有效算法
Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms
论文作者
论文摘要
由单细胞生物学和宏基因组学中的应用激发，我们研究了基于嘈杂的单调toeplitz矩阵模型的矩阵重新排序的问题。我们在决策理论框架中建立了该问题的基本统计限制，并证明受约束的最小二乘估计器可实现最佳速率。但是，由于其计算复杂性，我们分析了流行的多项式算法，光谱序列，并表明其是次优的。为了解决这个问题，我们提出了一种新型的多项式自适应分选算法，并保证了性能提高。对两个实际单细胞RNA测序数据集的仿真和分析证明了我们的算法优于现有方法。
Motivated by applications in single-cell biology and metagenomics, we investigate the problem of matrix reordering based on a noisy disordered monotone Toeplitz matrix model. We establish the fundamental statistical limit for this problem in a decision-theoretic framework and demonstrate that a constrained least squares estimator achieves the optimal rate. However, due to its computational complexity, we analyze a popular polynomial-time algorithm, spectral seriation, and show that it is suboptimal. To address this, we propose a novel polynomial-time adaptive sorting algorithm with guaranteed performance improvement. Simulations and analyses of two real single-cell RNA sequencing datasets demonstrate the superiority of our algorithm over existing methods.
