Iterative hard thresholding for low CP-rank tensor models

R. Grotheer, S. Li, A. Ma, D. Needell, J. Qin

Research output: Contribution to journalArticlepeer-review

Abstract

Recovery of low-rank matrices from a small number of linear measurements is now well-known to be possible under various model assumptions on the measurements. Such results demonstrate robustness and are backed with provable theoretical guarantees. However, extensions to tensor recovery have only recently began to be studied and developed, despite an abundance of practical tensor applications. Recently, a tensor variant of the Iterative Hard Thresholding method was proposed and theoretical results were obtained that exact guarantee recovery of tensors with low Tucker rank. In this paper, we utilize and prove a similar tensor version of the Restricted Isometry Property (RIP) to extend these results for tensors with low CANDECOMP/PARAFAC (CP) rank. In doing so, we leverage recent results on efficient approximations of CP decompositions that remove the need for challenging assumptions in prior works. We complement our theoretical findings with empirical results that showcase the potential of the approach.

Original languageEnglish
Pages (from-to)7452-7468
Number of pages17
JournalLinear and Multilinear Algebra
Volume70
Issue number22
DOIs
StatePublished - 2022

Bibliographical note

Funding Information:
This material is based upon work supported by the National Security Agency [grant number H98230-19-1-0119], The Lyda Hill Foundation, The McGovern Foundation, and Microsoft Research, while the authors were in residence at the Mathematical Sciences Research Institute in Berkeley, California, during the summer of 2019. In addition, Needell was funded by NSF CAREER DMS #1348721, NSF BIGDATA DMS #1740325 and NSF DMS #DMS 2011140. Li was supported by the NSF [grant numbers CCF-1409258, CCF-1704204], and the DARPA Lagrange Program under ONR/SPAWAR contract N660011824020. Qin is supported by the NSF [grant number DMS-1941197].

Publisher Copyright:
© 2021 Informa UK Limited, trading as Taylor & Francis Group.

Keywords

  • CP rank
  • Iterative hard thresholding
  • low-rank tensor recovery
  • restricted isometry property
  • tensors

ASJC Scopus subject areas

  • Algebra and Number Theory

Fingerprint

Dive into the research topics of 'Iterative hard thresholding for low CP-rank tensor models'. Together they form a unique fingerprint.

Cite this