A statistical model for tensor PCA

Abstract

We consider the Principal Component Analysis problem for large tensors of arbitrary order $k$ under a single-spike (or rank-one plus noise) model. On the one hand, we use information theory, and recent results in probability theory, to establish necessary and sufficient conditions under which the principal component can be estimated using unbounded computational resources. It turns out that this is possible as soon as the signal-to-noise ratio $\beta$ becomes larger than $C\sqrt{k\log k}$ (and in particular $\beta$ can remain bounded as the problem dimensions increase). On the other hand, we analyze several polynomial-time estimation algorithms, based on tensor unfolding, power iteration and message passing ideas from graphical models. We show that, unless the signal-to-noise ratio diverges in the system dimensions, none of these approaches succeeds. This is possibly related to a fundamental limitation of computationally tractable estimators for this problem. We discuss various initializations for tensor power iteration, and show that a tractable initialization based on the spectrum of the matricized tensor outperforms significantly baseline methods, statistically and computationally. Finally, we consider the case in which additional side information is available about the unknown signal. We characterize the amount of side information that allows the iterative algorithms to converge to a good estimate.

Neural Information Processing Systems (NIPS) 2014 (slightly expanded: 30 pages, 6 figures)

References in corpus (5)

• Message Passing Algorithms for Compressed Sensing
• A New Convex Relaxation for Tensor Completion
• A Tensor Approach to Learning Mixed Membership Community Models
• The largest eigenvalues of sample covariance matrices for a spiked population: diagonal case
• Non-negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics

Cited by in corpus (33)

• Quantum machine learning: a classical perspective
• Statistical physics of inference: Thresholds and algorithms
• Algorithmic thresholds for tensor PCA
• The Landscape of Empirical Risk for Non-convex Losses
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Computational Barriers to Estimation from Low-Degree Polynomials
• Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
• A New Sampling Technique for Tensors
• How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA
• Operator Norm Inequalities between Tensor Unfoldings on the Partition Lattice
• Subexponential-Time Algorithms for Sparse PCA
• Tensor Decompositions via Two-Mode Higher-Order SVD (HOSVD)
• Field theoretical approach for signal detection in nearly continuous positive spectra II: Tensorial data
• Homotopy Analysis for Tensor PCA
• Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
• Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality
• The Overlap Gap Property in Principal Submatrix Recovery
• Factor Models for High-Dimensional Tensor Time Series
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit
• Statistical Query Lower Bounds for Tensor PCA
• Power Iteration for Tensor PCA
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Phase transition in the spiked random tensor with Rademacher prior
• Group testing and local search: is there a computational-statistical gap?
• Learning Good State and Action Representations via Tensor Decomposition
• Tensor SVD: Statistical and Computational Limits
• Strongly Refuting Random CSPs Below the Spectral Threshold
• Positivity-preserving extensions of sum-of-squares pseudomoments over the hypercube
• Deep Markov Spatio-Temporal Factorization
• Optimal Sparse Singular Value Decomposition for High-dimensional High-order Data
• Algorithms for an Efficient Tensor Biclustering