Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
复制标题
通过 4 度 SOS 实现随机过完备张量的精确核范数、完成和分解
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Aaron Potechin
中科院分区：
文献类型：
--
作者：
Bohdan Kivva;Aaron Potechin
在本文中，我们表明受4次平方和（SOS）启发的简单半定规划能够精确求解具有随机非对称分量的张量的张量核范数、张量分解以及张量补全问题。更确切地说，对于张量核范数和张量分解，我们证明以高概率（w.h.p.）这些半定规划能够精确找到具有$m\leq n^{3/2}/\text{polylog}(n)$个随机非对称分量的$(n\times n\times n)$张量$\mathcal{T}$的核范数和分量。对于张量补全，我们证明以高概率由波特钦（Potechin）和施特勒尔（Steurer）（2017）引入的半定规划能够从仅$n^{3/2}m,\text{polylog}(n)$个随机观测到的元素中精确恢复具有$m$个随机非对称分量的$(n\times n\times n)$张量$\mathcal{T}$。这为过完备情形下的精确张量补全给出了首个理论保证。
这与巴拉克（Barak）和莫伊特拉（Moitra）（2015）针对张量补全以及马（Ma）、施（Shi）和施特勒尔（2016）针对张量分解所给出的这些问题的近似版本的已知最佳结果相匹配。
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 imes n imes n)$-tensor $mathcal{T}$ with $mleq 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) can exactly recover an $(n imes n imes n)$-tensor $mathcal{T}$ with $m$ random asymmetric components from only $n^{3/2}m, polylog(n)$ randomly observed entries. This gives the first theoretical guarantees for exact tensor completion in the overcomplete regime.
This matches the best known results for approximate versions of these problems given by Barak & Moitra (2015) for tensor completion, and Ma, Shi & Steurer (2016) for tensor decomposition.