Nonconvex Low-Rank Tensor Completion from Noisy Data

By Changxiao Cai, Gen Li, H. Vincent Poor, Yuxin Chen. 2019

95 citations recorded by the source corpus.

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.

Subfields: Computational Mathematics, Computational Mechanics, Computer Vision and Pattern Recognition, Optimization & Training, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

1. Noam Razin
2. Lester W. Mackey
3. Nadav Cohen
4. Michael W. Mahoney

In Computational Mechanics

1. Noam Razin
2. Mikhail Khodak
3. Lester W. Mackey
4. Nicoló Fusi
5. Nadav Cohen
6. Neil A. Tenenholtz
7. Michael W. Mahoney

In Computer Vision and Pattern Recognition

1. Noam Razin
2. Mikhail Khodak
3. Lester W. Mackey
4. Nicoló Fusi
5. Nadav Cohen
6. Neil A. Tenenholtz
7. Radu Timofte

In Optimization & Training

1. Noam Razin
2. Mikhail Khodak
3. Lester W. Mackey
4. Nicoló Fusi
5. Nadav Cohen
6. Neil A. Tenenholtz
7. Wei Hu

In Mathematical Optimization

1. Noam Razin
2. Lester W. Mackey
3. Nadav Cohen

Citations in the corpus

• Initialization and Regularization of Factorized Neural Layers (2021, background): “Outside deep learning, spectral methods have also been shown to yield better initializations for certain matrix and tensor problems (Keshavan et al., 2010; Chi et al., 2019; Cai et al., 2019).”
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms (2020, background): “[14] Changxiao Cai, Gen Li, H Vincent Poor, and Yuxin Chen.”