Can I read Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS on EtoBox?

Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS by Kivva, Bohdan; Potechin, Aaron is a scholarly article available to read on EtoBox.

What is Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS about?

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 asymmet

Author

Kivva, Bohdan; Potechin, Aaron

Published

2020

Language

EN