Pith. sign in

REVIEW 4 cited by

Spectral norm of random tensors

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1407.1870 v1 pith:6AKZCC36 submitted 2014-07-07 math.ST stat.MLstat.TH

Ryota Tomioka , Taiji Suzuki This is my paper · ORCID
classification math.STstat.MLstat.TH
keywords normconvexspectraltensortimesnumberrandomrank
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

We show that the spectral norm of a random $n_1\times n_2\times \cdots \times n_K$ tensor (or higher-order array) scales as $O\left(\sqrt{(\sum_{k=1}^{K}n_k)\log(K)}\right)$ under some sub-Gaussian assumption on the entries. The proof is based on a covering number argument. Since the spectral norm is dual to the tensor nuclear norm (the tightest convex relaxation of the set of rank one tensors), the bound implies that the convex relaxation yields sample complexity that is linear in (the sum of) the number of dimensions, which is much smaller than other recently proposed convex relaxations of tensor rank that use unfolding.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood

    quant-ph 2025-05 conditional novelty 8.0 of 10

    A quantum extension of the low-degree method shows that state designs imply computational hardness for many single-copy quantum measurement strategies, yielding new information-computation gaps.

  2. Relative entropy of entanglement of Haar random states

    quant-ph 2026-08 accept novelty 7.0 of 10

    For a bipartite mixed state obtained by tracing out one subsystem of a tripartite Haar-random pure state, the relative entropy of entanglement equals log(d_A d_B / max(d_A,d_B,d_C)) plus an absolute constant, with hig...

  3. Balanced multi-species spin glasses

    math.PR 2025-07 conditional novelty 7.0 of 10

    A lower bound shows balanced multi-species spin glasses have free energy at least that of a single-species model with variance-matched couplings, and this bound is sharp in several regimes.

  4. Finite-Iteration Local Dynamics and Warm Starts for Alternating Power Iteration in Spiked Tensor PCA

    stat.ML 2026-06 unverdicted novelty 6.0 of 10

    Finite-iteration local theory and generic warm-start conditions for alternating power iteration on asymmetric rank-one spiked tensors, reducing to high-signal regime under multilinear noise events.

Pith tools