报告人：江波教授

报告题目：Complexity and computation for the spectral norm and nuclear norm of order three tensors

摘要：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) and approximation algorithms with improved worst case guarantee for the spectral norm and for the nuclear norm with further help of duality theory and semidefinite optimization. Numerical experiments on simulated data show that our algorithms can compute these tensor norms for small $\ell \le 6$ but large $m, n\ge 50$. To the best of our knowledge, this is the first method that can compute the nuclear norm of general asymmetric tensors.

报告时间：2022年5月24号上午09:30-12:00

报告形式：腾讯会议；会议号：667 716 667

报告人简介：江波，美国明尼苏达大学博士，上海财经大学信息管理与工程学院常聘教授；交叉科学研究院副院长；上海市高校特聘教授(东方学者)、上海市青年拔尖人才。从事运筹优化、收益管理、机器学习等方向的研究。成果发表于运筹优化与机器学习的国际顶级期刊《Operations Research》、《Mathematics of Operations Research》、《Mathematical Programming》、《SIAM Journal on Optimization》、《Journal of Machine Learning Research》。获得了中国运筹学会青年科技奖、上海市自然科学奖二等奖等荣誉。主持多项国家自然科学基金面项目。