# Spectral norm of random tensors

arXiv: https://arxiv.org/abs/1407.1870 · HTML: https://mlsanity.com/paper/1407.1870/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jul 2014.

## Built on by (most cited first, 9 of 9)

- [The Complexity of Sparse Tensor PCA](https://mlsanity.com/paper/2106.06308/) (2021)
- [On the Memory Mechanism of Tensor-Power Recurrent Models](https://mlsanity.com/paper/2103.01521/) (2021)
- [Covariate-assisted Sparse Tensor Completion](https://mlsanity.com/paper/2103.06428/) (2021)
- [Nearly Optimal Attention Coresets](https://mlsanity.com/paper/2605.05602/) (2026)
- [A Random Matrix Approach to Low-Multilinear-Rank Tensor Approximation](https://mlsanity.com/paper/2402.03169/) (2024)
- [TeRA: Vector-based Random Tensor Network for High-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2509.03234/) (2025)
- [Finite-Iteration Local Dynamics and Warm Starts for Alternating Power Iteration in Spiked Tensor PCA](https://mlsanity.com/paper/2606.04065/) (2026)
- [Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions](https://mlsanity.com/paper/2609.06327/) (2026)
- [Sharp spectral norm concentration of sparse random tensors](https://mlsanity.com/paper/2609.20520/) (2026)

## Abstract (arXiv)

We show that the spectral norm of a random n1× n2× cdots × nK tensor (or higher-order array) scales as Oleft(√(sumk=1Knk)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.