IEEE Trans Inf Theory. 2024 Jan;70(1):509-531. doi: 10.1109/tit.2023.3305538. Epub 2023 Aug 15.
ABSTRACT
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.
PMID:39036782 | PMC:PMC11257605 | DOI:10.1109/tit.2023.3305538
