Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
From MaRDI portal
Abstract: Principal component analysis (PCA) aims at estimating the direction of maximal variability of a high-dimensional dataset. A natural question is: does this task become easier, and estimation more accurate, when we exploit additional knowledge on the principal vector? We study the case in which the principal vector is known to lie in the positive orthant. Similar constraints arise in a number of applications, ranging from analysis of gene expression data to spike sorting in neural signal processing. In the unconstrained case, the estimation performances of PCA has been precisely characterized using random matrix theory, under a statistical model known as the `spiked model.' It is known that the estimation error undergoes a phase transition as the signal-to-noise ratio crosses a certain threshold. Unfortunately, tools from random matrix theory have no bearing on the constrained problem. Despite this challenge, we develop an analogous characterization in the constrained case, within a one-spike model. In particular: ~We prove that the estimation error undergoes a similar phase transition, albeit at a different threshold in signal-to-noise ratio that we determine exactly; ~We prove that --unlike in the unconstrained case-- estimation error depends on the spike vector, and characterize the least favorable vectors; ~We show that a non-negative principal component can be approximately computed --under the spiked model-- in nearly linear time. This despite the fact that the problem is non-convex and, in general, NP-hard to solve exactly.
Recommendations
- Methodology and theory for nonnegative-score principal component analysis
- The nonnegative matrix factorization: regularization and complexity
- Sparse non Gaussian component analysis by semidefinite programming
- Nonlinear Non-Negative Component Analysis Algorithms
- New asymptotic results in principal component analysis
- Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
- Projection algorithms for nonconvex minimization with application to sparse principal component analysis
- Nonnegative matrix factorization and I-divergence alternating minimization
- Non-negative matrix factorization: Ill-posedness and a geometric algorithm
Cited in
(38)- Notes on computational-to-statistical gaps: predictions using statistical physics
- Optimality and sub-optimality of PCA. I: Spiked random matrix models
- Simple algorithms for optimization on Riemannian manifolds with constraints
- Universality of approximate message passing algorithms
- The distribution of the Lasso: uniform control over sparse balls and adaptive parameter tuning
- Random matrix theory and its applications
- Optimal low-degree hardness of maximum independent set
- Approximate message passing algorithms for rotationally invariant matrices
- Statistical physics and representations in real and artificial neural networks
- Statistical limits of spiked tensor models
- A brief introduction to manifold optimization
- Phase transition in random tensors with multiple independent spikes
- Sparse equisigned PCA: algorithms and performance bounds in the noisy rank-1 setting
- Phase transition in the spiked random tensor with Rademacher prior
- Fundamental limits of weak recovery with applications to phase retrieval
- Estimation of low-rank matrices via approximate message passing
- Nonconvex phase synchronization
- Exact guarantees on the absence of spurious local minima for non-negative rank-1 robust principal component analysis
- scientific article; zbMATH DE number 7370563 (Why is no real title available?)
- A Unifying Tutorial on Approximate Message Passing
- Stochastic difference-of-convex-functions algorithms for nonconvex programming
- Riemannian optimization via Frank-Wolfe methods
- Generalized TAP Free Energy
- Sion’s Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm
- A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds
- Approximate message passing for sparse matrices with application to the equilibria of large ecological Lotka-Volterra systems
- Singular value problems under nonnegativity constraints
- Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
- Cone-constrained singular value problems
- On the TAP equations via the cavity approach in the generic mixed \(p\)-spin models
- An interior proximal gradient method for nonconvex optimization
- Convergence and worst-case complexity of adaptive Riemannian trust-region methods for optimization on manifolds
- Riemannian trust region methods for \(\mathrm{SC}^1\) minimization
- Equilibria of large random Lotka-Volterra systems with vanishing species: a mathematical approach
- Optimal subsampling for principal component analysis
- A leave-one-out approach to approximate message passing
- Computational lower bounds for multi-frequency group synchronization
- Computing the least cone-constrained singular value of matrices
This page was built for publication: Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976981)
