2022/01/17 by T. Tony Cai, Cai, T. Tony, Rong Ma +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Methodology (stat.ME) #Single-cell and spatial transcriptomics #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2201.06438
openalex publication_date 2022/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.