l p-Sphere Covering and Approximating Nuclear p-Norm

• 成果类型: Article; Early Access
• 署名作者: Guan, Jiewen; He, Simai; Jiang, Bo; Li, Zhening
• 署名单位: Shanghai University of Finance & Economics; Shanghai Jiao Tong University; Shanghai University of Finance & Economics; Shanghai University of Finance & Economics; University of Portsmouth
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.0216
• 发表日期: 2024
• 关键词: polynomial optimization; decompositions; EQUATIONS

摘要

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 & ell; 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 the & ell; p-sphere with adjustable parameters for different levels of approximations and cardinalities, providing an independent toolbox for decision making on & ell; p-spheres. Using the idea in robust optimization and second-order cone programming, we obtain the first polynomial-time algorithm with an Q(1)-approximation bound for the computation of the matrix nuclear p-norm when p is an element of ( 2, infinity) is a rational, paving a way for applications in modeling with the matrix nuclear p-norm. These two new results enable us to propose various polynomialtime 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-norms. Effective performance of the proposed algorithms for the tensor nuclear p-norm is shown by numerical implementations. We believe the ideas of & ell; p-sphere covering with its applications in approximating nuclear p-norm would be useful for tackling optimization problems on other sets, such as the binary hypercube with its applications in graph theory and neural networks and the nonnegative sphere with its applications in copositive programming and nonnegative matrix factorization.