Long Random Matrices and Tensor Unfolding
This provides theoretical guarantees for tensor unfolding algorithms in signal processing and machine learning, though it appears incremental as it extends existing matrix perturbation theory to tensor contexts.
The paper analyzes singular values and vectors of low-rank perturbations in large rectangular random matrices with polynomial growth dimensions, proving a BBP-type phase transition at a critical signal-to-noise ratio. It applies this to tensor unfolding for asymmetric rank-one spiked tensors, deriving an exact threshold for signal detection that is independent of the unfolding procedure.
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.