31. Spectral and nuclear norms of order three tensors: Complexity and computation
Invited abstract in session TD-5: Nonsmooth optimization algorithms, stream Nonsmooth and nonconvex optimization algorithms.
Thursday, 14:10 - 15:50Room: M:N
Authors (first author is the speaker)
| 1. | Zhening Li
|
| Department of Mathematics, University of Portsmouth |
Abstract
The recent decade has witnessed a surge of research in modeling and computing from twoway data (matrices) to multiway data (tensors). However, there is a drastic phase transition for most tensor optimization and computation problems when the order of a tensor increases from two 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 work aims to study the kind of question for the spectral norm and the nuclear norm. Although computing the spectral norm for a general ℓ×m×n tensor is NP-hard, we show that it can be computed in polynomial time if ℓ is fixed. In another word, the best rank-one approximation of a general ℓ×m×n tensor can be computed in polynomial time for fixed ℓ. This is the same for the nuclear norm. While these polynomial-time methods are not currently implementable in practice, we propose fully polynomial-time approximation schemes (FPTAS) for the spectral norm based on polytope approximation and for the nuclear norm with further help of duality theory and semidefinite optimization. Numerical experiments show that our FPTAS can compute these tensor norms for small ℓ but large m and n. To the best of our knowledge, this is the first method that can exactly compute the nuclear norm of general asymmetric tensors. Both our polynomial-time algorithms and FPTAS can be extended to higher-order tensors as well.
Keywords
- Complexity and efficiency of optimization algorithms
- Conic and semidefinite optimization
Status: accepted
Back to the list of papers