Performance Gaps in Multi-view Clustering under the Nested Matrix-Tensor
  Model
Hugo Lebeau Mohamed El Amine Seddik José Henrique de Morais Goulart
We study the estimation of a planted signal hidden in a recently introduced
nested matrix-tensor model, which is an extension of the classical spiked
rank-one tensor model, motivated by multi-view clustering. Prior work has
theoretically examined the performance of a tensor-based approach, which relies
on finding a best rank-one approximation, a problem known to be computationally
hard. A tractable alternative approach consists in computing instead the best
rank-one (matrix) approximation of an unfolding of the observed tensor data,
but its performance was hitherto unknown. We quantify here the performance gap
between these two approaches, in particular by deriving the precise algorithmic
threshold of the unfolding approach and demonstrating that it exhibits a
BBP-type transition behavior. This work is therefore in line with recent
contributions which deepen our understanding of why tensor-based methods
surpass matrix-based methods in handling structured tensor data.