Seminar| Institute of Mathematical Sciences
Speaker: Bo Jiang, Shanghai University of Finance and Economics
Abstract: The spectral p-norm and nuclear p-norm of matrices and tensors appear in various applications albeit both are NP-hard to compute. The former sets a foundation of l_p-sphere constrained polynomial optimization problems and the latter has been found in many rank minimization problems in machine learning. We study approximation algorithms of the tensor nuclear p-norm with an aim to establish the approximation bound matching the best one of its dual norm, the tensor spectral p-norm. Driven by the application of sphere covering to approximate both tensor spectral and nuclear norms (p = 2), we propose several types of hitting sets that approximately represent `p-sphere with adjustable parameters for different levels of approximations and cardinalities, providing an independent toolbox for decision making on `p-spheres. Using the idea in robust optimization and second-order cone programming, we obtain the first polynomial-time algorithm with an O(1)-approximation bound for the computation of the matrix nuclear p-norm when p ∈ (2,∞) is a rational, paving a way for applications in optimization with the matrix nuclear p-norm. These two new results enable us to propose various polynomial-time approximation algorithms for the computation of the tensor nuclear p-norm using tensor partitions, convex optimization and duality theory, attaining the same approximation bound to the best one of the tensor spectral p-norm