Optimal estimation and computational limit of low-rank Gaussian mixtures
From MaRDI portal
(Redirected from Publication:6172192)
Abstract: Structural matrix-variate observations routinely arise in diverse fields such as multi-layer 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.
Recommendations
- Optimal estimation of high-dimensional Gaussian location mixtures
- Structured matrix estimation and completion
- Fundamental limits of symmetric low-rank matrix estimation
- Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
- Statistical and computational limits for sparse matrix detection
Cites work
- A Doubly Enhanced EM Algorithm for Model-Based Tensor Clustering
- A non asymptotic penalized criterion for Gaussian mixture model selection
- A tail inequality for suprema of unbounded empirical processes with applications to Markov chains
- CHIME: clustering of high-dimensional Gaussian mixtures with EM algorithm and its optimality
- Common and individual structure of brain networks
- Community detection on mixture multilayer networks via regularized tensor decomposition
- Computationally efficient sparse clustering
- Consistent estimation of a mixing distribution
- Convergence rates of parameter estimation for some weakly identifiable finite mixtures
- Dynamic tensor clustering
- Efficiently learning mixtures of two Gaussians
- Entropies and rates of convergence for maximum likelihood and Bayes estimation for mixtures of normal densities.
- Estimating a network from multiple noisy realizations
- Hellinger-consistency of certain nonparametric maximum likelihood estimators
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- scientific article; zbMATH DE number 6982931 (Why is no real title available?)
- scientific article; zbMATH DE number 1391247 (Why is no real title available?)
- scientific article; zbMATH DE number 1420699 (Why is no real title available?)
- Learning mixtures of arbitrary Gaussians
- Learning mixtures of Gaussians in high dimensions
- Learning Mixtures of Low-Rank Models
- Normal approximation and confidence region of singular subspaces
- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- On strong identifiability and convergence rates of parameter estimation in finite mixtures
- Optimal estimation of Gaussian mixtures via denoised method of moments
- Optimal estimation of high-dimensional Gaussian location mixtures
- Optimal estimation of low rank density matrices
- Optimal rate of convergence for finite mixture models
- Optimality of spectral clustering in the Gaussian mixture model
- Perturbation of linear forms of singular vectors under Gaussian noise
- Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in \(O(\sqrt{n})\) iterations
- Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
- Rates of convergence for the Gaussian mixture sieve.
- Regularized matrix data clustering and its application to image analysis
- Spectral and matrix factorization methods for consistent community detection in multi-layer networks
- Statistical guarantees for the EM algorithm: from population to sample-based analysis
- Statistically optimal and computationally efficient low rank tensor completion from noisy entries
- Tackling Small Eigen-Gaps: Fine-Grained Eigenvector Estimation and Inference Under Heteroscedastic Noise
- Tensor SVD: Statistical and Computational Limits
- The Optimal Hard Threshold for Singular Values is <inline-formula> <tex-math notation="TeX">\(4/\sqrt {3}\) </tex-math></inline-formula>
- The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
- Upper bounds on product and multiplier empirical processes
- Volume Ratio, Sparsity, and Minimaxity Under Unitarily Invariant Norms
- Weak convergence and empirical processes. With applications to statistics
Cited in
(7)- Optimal estimation of high-dimensional Gaussian location mixtures
- Computational lower bounds for graphon estimation via low-degree polynomials
- Computational and statistical thresholds in multi-layer stochastic block models
- Optimal clustering by Lloyd's algorithm for low-rank mixture model
- Tensor-on-tensor regression: Riemannian optimization, over-parameterization, statistical-computational gap and their interplay
- Statistical inference for low-rank tensors: heteroskedasticity, subgaussianity, and applications
- Low rank convex clustering for matrix-valued observations
This page was built for publication: Optimal estimation and computational limit of low-rank Gaussian mixtures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6172192)
