Theoretical performance analysis of Tucker Higher Order SVD in extracting structure from multiple signal-plus-noise matrices

The Tucker Higher Order SVD is a popular algorithm for uncovering structure from tensor datacubes. This algorithm has been successfully used in many signal processing, machine learning and data mining applications. In this work, we use recent results from random matrix theory to analyze the performance of the HOSVD algorithm. In particular, we focus on the performance HOSVD on 3-D tensors for extraction of structure from signal-plus-noise tensors. We analyze the missing data setting where the entries of the signal-plus-noise tensor are randomly deleted. Our analysis bring into focus a phase transition phenomenon which separates a regime where the HOSVD can accurately estimate the latent signal matrix from a regime where it cannot. The threshold depends on the signal-to-noise ratio and the fraction of missing entries observed in a manner we make explicit. Finally, we illustrate the predicted performance curves using numerical simulations and illustrate implication of our predictions on an widely used facial recognition dataset.