Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
This work provides improved theoretical guarantees and exact recovery methods for tensor decomposition and completion, particularly for overcomplete and non-orthogonal tensors, which is significant for researchers and practitioners working with high-dimensional data analysis.
This paper demonstrates that semidefinite programs (SDPs) based on degree-4 Sum-of-Squares (SOS) can exactly solve tensor nuclear norm, decomposition, and completion problems for tensors with random asymmetric components. For nuclear norm and decomposition, the SDPs can find the nuclear norm and components of an (n x n x n)-tensor with m <= n^(3/2)/polylog(n) random asymmetric components. For tensor completion, the SDP can exactly recover an (n x n x n)-tensor with m random asymmetric components from n^(3/2)m polylog(n) randomly observed entries, improving the dependence on m for non-orthogonal tensors.
In this paper we show that simple semidefinite programs inspired by degree $4$ SOS can exactly solve the tensor nuclear norm, tensor decomposition, and tensor completion problems on tensors with random asymmetric components. More precisely, for tensor nuclear norm and tensor decomposition, we show that w.h.p. these semidefinite programs can exactly find the nuclear norm and components of an $(n\times n\times n)$-tensor $\mathcal{T}$ with $m\leq n^{3/2}/polylog(n)$ random asymmetric components. Unlike most of the previous algorithms, our algorithm provides a certificate for the decomposition, does not require knowledge about the number of components in the decomposition and does not make any assumptions on the sizes of the coefficients in the decomposition. As a byproduct, we show that w.h.p. the nuclear norm decomposition exactly coincides with the minimum rank decomposition for tensors with $m\leq n^{3/2}/polylog(n)$ random asymmetric components. For tensor completion, we show that w.h.p. the semidefinite program, introduced by Potechin & Steurer (2017) for tensors with orthogonal components, can exactly recover an $(n\times n\times n)$-tensor $\mathcal{T}$ with $m$ random asymmetric components from only $n^{3/2}m polylog(n)$ randomly observed entries. For non-orthogonal tensors, this improves the dependence on $m$ of the number of entries needed for exact recovery over all previously known algorithms and provides the first theoretical guarantees for exact tensor completion in the overcomplete regime.