Timezone: »

 
Poster
Nonconvex Low-Rank Symmetric Tensor Completion from Noisy Data
Changxiao Cai · Gen Li · H. Vincent Poor · Yuxin Chen

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #122
in Optimization -- Non-Convex Optimization »
We study a completion problem of broad practical interest: the reconstruction of a low-rank symmetric tensor from highly incomplete and randomly corrupted observations of its entries. While a variety of prior work has been dedicated to this problem, prior algorithms either are computationally too expensive for large-scale applications, or come with sub-optimal statistical guarantees. Focusing on ``incoherent'' and well-conditioned tensors of a constant CP rank, we propose a two-stage nonconvex algorithm --- (vanilla) gradient descent following a rough initialization --- that achieves the best of both worlds. Specifically, the proposed nonconvex algorithm faithfully completes the tensor and retrieves all low-rank tensor factors within nearly linear time, while at the same time enjoying near-optimal statistical guarantees (i.e. minimal sample complexity and optimal $\ell_2$ and $\ell_{\infty}$ statistical accuracy). The insights conveyed through our analysis of nonconvex optimization might have implications for other tensor estimation problems.
Keywords: Sparsity and Compressed Sensing · Non-Convex Optimization · Optimization · Algorithms -> Missing Data; Algorithms
[ Paper]  [ Poster] 

Author Information

Changxiao Cai (Princeton University)
Gen Li (Tsinghua University)
H. Vincent Poor (Princeton University)
Yuxin Chen (Princeton University)

More from the Same Authors