  This paper investigates the computational and statistical limits in
clustering matrix-valued observations. We propose a low-rank mixture model
(LrMM), adapted from the classical Gaussian mixture model (GMM) to treat
matrix-valued observations, which assumes low-rankness for population center
matrices. A computationally efficient clustering method is designed by
integrating Lloyd's algorithm and low-rank approximation. Once
well-initialized, the algorithm converges fast and achieves an exponential-type
clustering error rate that is minimax optimal. Meanwhile, we show that a
tensor-based spectral method delivers a good initial clustering. Comparable to
GMM, the minimax optimal clustering error rate is decided by the separation
strength, i.e., the minimal distance between population center matrices. By
exploiting low-rankness, the proposed algorithm is blessed with a weaker
requirement on the separation strength. Unlike GMM, however, the computational
difficulty of LrMM is characterized by the signal strength, i.e., the smallest
non-zero singular values of population center matrices. Evidence is provided
showing that no polynomial-time algorithm is consistent if the signal strength
is not strong enough, even though the separation strength is strong. Intriguing
differences between estimation and clustering under LrMM are discussed. The
merits of low-rank Lloyd's algorithm are confirmed by comprehensive simulation
experiments. Finally, our method outperforms others in the literature on
real-world datasets.
