OPTIMAL ESTIMATION AND COMPUTATIONAL LIMIT OF LOW-RANK GAUSSIAN MIXTURES

• 成果类型: Article
• 署名作者: Lyu, Zhongyuan; Xia, Dong
• 署名单位: Hong Kong University of Science & Technology
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/23-AOS2264
• 发表日期: 2023
• 页码: 646-667
• 关键词: parameter-estimation; community detection; maximum-likelihood; convergence-rates; learning mixtures; em algorithm; perturbation; bounds

摘要

Structural matrix-variate observations routinely arise in diverse fields such as multilayer network analysis and brain image clustering. While data of this type have been extensively investigated with fruitful outcomes being delivered, the fundamental questions like its statistical optimality and computational limit are largely under-explored. In this paper, we propose a low-rank Gaussian mixture model (LrMM) assuming each matrix-valued observation has a planted low-rank structure. Minimax lower bounds for estimating the underlying low-rank matrix are established allowing a whole range of sample sizes and signal strength. Under a minimal condition on signal strength, referred to as the information-theoretical limit or statistical limit, we prove the minimax optimality of a maximum likelihood estimator which, in general, is computationally infeasible. If the signal is stronger than a certain threshold, called the computational limit, we design a computationally fast estimator based on spectral aggregation and demonstrate its minimax optimality. Moreover, when the signal strength is smaller than the computational limit, we provide evidences based on the low-degree likelihood ratio framework to claim that no polynomial-time algorithm can consistently recover the underlying low-rank matrix. Our results reveal multiple phase transitions in the minimax error rates and the statistical-to-computational gap. Numerical experiments confirm our theoretical findings. We further showcase the merit of our spectral aggregation method on the worldwide food trading dataset.