论文标题
光谱规范和核标准的复杂性和计算，该顺序的三个张力量具有一个固定尺寸
Complexity and computation for the spectral norm and nuclear norm of order three tensors with one fixed dimension
论文作者
论文摘要
最近的十年见证了从双向数据（矩阵）到多路数据（张量）的建模和计算研究激增。但是，当大多数张量优化问题的张量从两个（矩阵）增加到三个时，大多数张量优化问题都有急剧的相变：大多数张量问题都是NP-HARD，而对于矩阵来说很容易。它触发了一个问题，即过渡的确切发生地点。该论文旨在研究光谱规范和核规范的这类问题。尽管计算一般$ \ ell \ el \ times m \ times n $ tensor的光谱规范是np-hard，但我们证明，如果$ \ ell $固定，则可以在多项式时间内计算它。核定常也是如此。尽管这些多项式时间方法在实践中不可实施，但我们提出了基于球形网格的光谱规范的完全多项式近似方案（FPTA），并在二元理论和半决赛优化的进一步帮助下为核定范围提供了核范围。模拟数据上的数值实验表明，我们的FPTA可以计算小$ \ ell \ le 6 $但大$ m，n \ ge50 $的这些张量规范。据我们所知，这是可以计算一般不对称张量的核定标准的第一种方法。我们的多项式时间算法和FPTA都可以扩展到高阶张量。
The recent decade has witnessed a surge of research in modelling and computing from two-way data (matrices) to multiway data (tensors). However, there is a drastic phase transition for most tensor optimization problems when the order of a tensor increases from two (a matrix) to three: Most tensor problems are NP-hard while that for matrices are easy. It triggers a question on where exactly the transition occurs. The paper aims to study this kind of question for the spectral norm and the nuclear norm. Although computing the spectral norm for a general $\ell\times m\times n$ tensor is NP-hard, we show that it can be computed in polynomial time if $\ell$ is fixed. This is the same for the nuclear norm. While these polynomial-time methods are not implementable in practice, we propose fully polynomial-time approximation schemes (FPTAS) for the spectral norm based on spherical grids and for the nuclear norm with further help of duality theory and semidefinite optimization. Numerical experiments on simulated data show that our FPTAS can compute these tensor norms for small $\ell \le 6$ but large $m, n\ge50$. To the best of our knowledge, this is the first method that can compute the nuclear norm of general asymmetric tensors. Both our polynomial-time algorithms and FPTAS can be extended to higher-order tensors as well.
