Approximating Tensor Norms via Sphere Covering: Bridging the Gap between Primal and Dual
本文提出确定性算法，通过构造球面覆盖来近似计算高阶张量的谱范数和核范数，改进了核范数的近似界，且方法数据无关、易于实现。
The matrix spectral norm and nuclear norm appear in enormous applications. The generalization of these norms to higher-order tensors is becoming increasingly important, but unfortunately they are NP-hard to compute or even approximate. Although the two norms are dual to each other, the best-known approximation bound achieved by polynomial-time algorithms for the tensor nuclear norm is worse than that for the tensor spectral norm. In this paper, we bridge this gap by proposing deterministic algorithms with the best bound for both tensor norms. Our methods not only improve the approximation bound for the nuclear norm but also are data independent and easily implementable compared to existing approximation methods for the tensor spectral norm. The main idea is to construct a selection of unit vectors that can approximately represent the unit sphere, in other words, a collection of spherical caps to cover the sphere. For this purpose, we explicitly construct several collections of spherical caps for sphere covering with adjustable parameters for different levels of approximations and cardinalities. These readily available constructions are of independent interest, as they provide a powerful tool for various decision-making problems on spheres and related problems. We believe the ideas of constructions and the applications to approximate tensor norms can be useful to tackle optimization problems over other sets, such as the binary hypercube.