English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The spectral $p$-norm and nuclear $p$-norm of matrices and tensors appear invarious applications albeit both are NP-hard to compute. The former sets afoundation of $\ell_p$-sphere constrained polynomial optimization problems andthe latter has been found in many rank minimization problems in machinelearning. We study approximation algorithms of the tensor nuclear $p$-norm withan aim to establish the approximation bound matching the best one of its dualnorm, the tensor spectral $p$-norm. Driven by the application of spherecovering to approximate both tensor spectral and nuclear norms ($p=2$), wepropose several types of hitting sets that approximately represent$\ell_p$-sphere with adjustable parameters for different levels ofapproximations and cardinalities, providing an independent toolbox for decisionmaking on $\ell_p$-spheres. Using the idea in robust optimization andsecond-order cone programming, we obtain the first polynomial-time algorithmwith an $\Omega(1)$-approximation bound for the computation of the matrixnuclear $p$-norm when $p\in(2,\infty)$ is a rational, paving a way forapplications in modeling with the matrix nuclear $p$-norm. These two newresults enable us to propose various polynomial-time approximation algorithmsfor the computation of the tensor nuclear $p$-norm using tensor partitions,convex optimization and duality theory, attaining the same approximation boundto the best one of the tensor spectral $p$-norm. We believe the ideas of$\ell_p$-sphere covering with its applications in approximating nuclear$p$-norm would be useful to tackle optimization problems on other sets such asthe binary hypercube with its applications in graph theory and neural networks,the nonnegative sphere with its applications in copositive programming andnonnegative matrix factorization.

$\ell_p$-sphere covering and approximating nuclear $p$-norm