Iterative hard thresholding based algorithms for low-rank tensor recovery

International audienceLow-rank tensor recovery (LRTR), i.e., the recovery of tensors having low-rank properties from underdetermined linear measurements, is a very important problem for numerous application areas, like medical/hyperspectral imaging, intelligent transport systems and computer network engineering, among others. This problem can be viewed as an extension of the low-rank matrix recovery (LRMR) problem to higher order arrays. Numerous approaches have been devised to address it. Unlike the matrix setting, however, no convex approach for LRTR is known to be both tractable and efficient (in terms of sampling requirements). Among the non-convex approaches, iterative hard thresholding (IHT) algorithms are particularly appealing due to their simplicity and effectiveness. In the first part of our talk, we will present a brief overview of LRTR methods, and more specifically of existing IHT algorithms. Then, we will introduce a new IHT algorithm which applies sequential per-mode SVD truncation as its thresholding operator, which has lower cost in comparison with the standard truncated HOSVD. Guarantees based on restricted isometry constants will be given for the proposed IHT solution. Although these guarantees lead to suboptimal sampling bounds, our numerical results suggest IHT algorithms have optimal recovery performance (order-wise) for Gaussian measurements. Heuristics for step size selection and for choosing an appropriate model complexity will be discussed. Several simulation results will be presented to illustrate the performance of our approach and compare it with existing ones