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

Recovering a low-rank tensor from incomplete information is a recurringproblem in signal processing and machine learning. The most popular convexrelaxation of this problem minimizes the sum of the nuclear norms of theunfoldings of the tensor. We show that this approach can be substantiallysuboptimal: reliably recovering a $K$-way tensor of length $n$ and Tucker rank$r$ from Gaussian measurements requires $\Omega(r n^{K-1})$ observations. Incontrast, a certain (intractable) nonconvex formulation needs only $O(r^K +nrK)$ observations. We introduce a very simple, new convex relaxation, whichpartially bridges this gap. Our new formulation succeeds with $O(r^{\lfloor K/2\rfloor}n^{\lceil K/2 \rceil})$ observations. While these results pertain toGaussian measurements, simulations strongly suggest that the new norm alsooutperforms the sum of nuclear norms for tensor completion from a random subsetof entries.  Our lower bound for the sum-of-nuclear-norms model follows from a new resulton recovering signals with multiple sparse structures (e.g. sparse, low rank),which perhaps surprisingly demonstrates the significant suboptimality of thecommonly used recovery approach via minimizing the sum of individual sparsityinducing norms (e.g. $l_1$, nuclear norm). Our new formulation for low-ranktensor recovery however opens the possibility in reducing the sample complexityby exploiting several structures jointly.

Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery