Random Matrices and Tensors for Large-Dimensional Statistical Learning
par
Salle 112
Bat Braconnier La Doua
This presentation will have two parts. The first part introduces an extension of spectral clustering on data streams. Assuming observations are made in an online fashion, we show how spectral clustering can be performed on the fly with a fixed amount of available memory. Studying this problem amounts to the spectral analysis of a particular Gram matrix in the high-dimensional regime, which we perform using tools from Random Matrix Theory. Based on our results, we describe the optimal memory policy and the corresponding clustering performance.
The second part of the presentation tackles the estimation of a planted low-rank signal in a large-dimensional tensor. This problem reveals a statistical-to-computational gap: a regime in which the maximum likelihood estimator is efficient, yet no polynomial-time algorithm can compute it. We study the performance of a procedure based on unfoldings, which is known to achieve the best algorithmic threshold, thereby revealing insights into the computational barrier.