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:
Abstract: This 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.
Publication Date: 3-Jun-2021
Citation: Cai, 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.2106
DOI: doi:10.1287/opre.2021.2106
ISSN: 0030-364X
EISSN: 1526-5463
Language: en
Type of Material: Journal Article
Journal/Proceeding Title: Operations Research
Version: Final published version. This is an open access article.

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