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

We consider convex relaxations for recovering low-rank tensors based onconstrained minimization over a ball induced by the tensor nuclear norm,recently introduced in \cite{tensor_tSVD}. We build on a recent line of resultsthat considered convex relaxations for the recovery of low-rank matrices andestablished that under a strict complementarity condition (SC), both theconvergence rate and per-iteration runtime of standard gradient methods mayimprove dramatically. We develop the appropriate strict complementaritycondition for the tensor nuclear norm ball and obtain the following mainresults under this condition: 1. When the objective to minimize is of the form$f(\mX)=g(\mA\mX)+\langle{\mC,\mX}\rangle$ , where $g$ is strongly convex and$\mA$ is a linear map (e.g., least squares), a quadratic growth bound holds,which implies linear convergence rates for standard projected gradient methods,despite the fact that $f$ need not be strongly convex. 2. For a smoothobjective function, when initialized in certain proximity of an optimalsolution which satisfies SC, standard projected gradient methods only requireSVD computations (for projecting onto the tensor nuclear norm ball) of rankthat matches the tubal rank of the optimal solution. In particular, when thetubal rank is constant, this implies nearly linear (in the size of the tensor)runtime per iteration, as opposed to super linear without further assumptions.3. For a nonsmooth objective function which admits a popular smoothsaddle-point formulation, we derive similar results to the latter for the wellknown extragradient method. An additional contribution which may be ofindependent interest, is the rigorous extension of many basic results regardingtensors of arbitrary order, which were previously obtained only for third-ordertensors.

Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the Tensor Nuclear Norm Under Strict Complementarity