EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2656. Sphere covering and approximating tensor norms

Invited abstract in session TA-34: New Algorithms for Nonlinear Optimization, stream Advances in large scale nonlinear optimization.

Tuesday, 8:30-10:00
Room: 43 (building: 303A)

Authors (first author is the speaker)

1. Zhening Li
Department of Mathematics, University of Portsmouth

Abstract

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. We bridge this gap by proposing deterministic algorithms with the best bound for both tensor norms. 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. Our results are generalized to the ℓp-sphere covering and approximating spectral and nuclear p-norms.

Keywords

Status: accepted

Back to the list of papers