Long Random Matrices and Tensor Unfolding
arXiv:2110.10210
Abstract
In this paper, we consider the singular values and singular vectors of low rank perturbations of large rectangular random matrices, in the regime the matrix is "long": we allow the number of rows (columns) to grow polynomially in the number of columns (rows). We prove there exists a critical signal-to-noise ratio (depending on the dimensions of the matrix), and the extreme singular values and singular vectors exhibit a BBP type phase transition. As a main application, we investigate the tensor unfolding algorithm for the asymmetric rank-one spiked tensor model, and obtain an exact threshold, which is independent of the procedure of tensor unfolding. If the signal-to-noise ratio is above the threshold, tensor unfolding detects the signals; otherwise, it fails to capture the signals.
arXiv comment29 pages, 4 figures
References in corpus (14)
- Tensor Decomposition for Signal Processing and Machine Learning
- Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
- Tensor Regression with Applications in Neuroimaging Data Analysis
- Nonlinear shrinkage estimation of large-dimensional covariance matrices
- Sparse principal component analysis and iterative thresholding
- Sparse PCA: Optimal rates and adaptive estimation
- Limit theorems for sample eigenvalues in a generalized spiked population model
- Asymptotic power of sphericity tests for high-dimensional data
- Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
- How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA
- Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection
- Phase transition in random tensors with multiple independent spikes
- A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
- Power Iteration for Tensor PCA