Wedges are all you need: sparser and sparser tensor completion

par Ludovic Stephan (ENSAI)

jeudi 2 avr. 2026, 14:00 → 15:00 Europe/Paris

Fokko du Cloux (ICJ)

Tensor completion, the higher-order analog of matrix completion, is characterized by a statistical-to-computational gap in the number of samples necessary to retrieve information. We show that this is only a consequence of the random sampling scheme: a small modification suffices to bridge the gap between polynomial and non-polynomial algorithms. We also prove that, akin to many inference problems, finding a non-trivial alignment with the signal is the hardest problem, while the refinement sample complexity does not depend on the tensor order.