Powerful computers and acquisition devices have made it possible to capture and store large real-world multidimensional data. For practical applications, analyzing and organizing these high dimensional arrays (formally called tensors) lead to the well-known curse of dimensionality. Thus, dimensionality reduction is frequently employed to transform a high-dimensional data set by projecting it into a lower dimensional space while retaining most of the information and underlying structure. One of these techniques is Principal Component Analysis (PCA), which has made remarkable progress in a large number of areas thanks to its simplicity and adaptability.
These last years, tools based on tensor contractions (trace invariants) have been developed by theoretical physicists where random tensors have emerged as a generalization of random matrices. In this work, we investigate the algorithmic threshold of tensor PCA and some of its variants using the theoretical physics approach and we show that it leads to new insights and knowledge in tensor PCA.
Joseph Ben Geloun
Fabien Vignes-Tourneret