Skip to main content

Nonconvex Low-Rank Tensor Completion from Noisy Data

Author(s): Cai, Changxiao; Li, Gen; Poor, H Vincent; Chen, Yuxin

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorCai, Changxiao-
dc.contributor.authorLi, Gen-
dc.contributor.authorPoor, H Vincent-
dc.contributor.authorChen, Yuxin-
dc.identifier.citationCai, Changxiao, Li, Gen, Poor, H Vincent, Chen, Yuxin. (2022). Nonconvex Low-Rank Tensor Completion from Noisy Data. Operations Research, 70 (2), 1219 - 1237. doi:10.1287/opre.2021.2106en_US
dc.description.abstractThis paper investigates a problem of broad practical interest, namely, the reconstruction of a large-dimensional low-rank tensor from highly incomplete and randomly corrupted observations of its entries. Although a number of papers have been dedicated to this tensor completion problem, prior algorithms either are computationally too expensive for large-scale applications or come with suboptimal statistical performance. Motivated by this, we propose a fast two-stage nonconvex algorithm—a gradient method following a rough initialization—that achieves the best of both worlds: optimal statistical accuracy and computational efficiency. Specifically, the proposed algorithm provably completes the tensor and retrieves all low-rank factors within nearly linear time, while at the same time enjoying near-optimal statistical guarantees (i.e., minimal sample complexity and optimal estimation accuracy). The insights conveyed through our analysis of nonconvex optimization might have implications for a broader family of tensor reconstruction problems beyond tensor completion.en_US
dc.relation.ispartofOperations Researchen_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleNonconvex Low-Rank Tensor Completion from Noisy Dataen_US
dc.typeJournal Articleen_US

Files in This Item:
File Description SizeFormat 
opre.2021.2106.pdf1.08 MBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.