Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Higher-order SVD — where it appears

The decomposition obtained by projecting a tensor onto the leading left singular subspace of each of its unfoldings. It exists, costs one matrix decomposition per index, and its truncation is within the square root of the number of indices of the best possible.

Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.

Also named here as multilinear rank, tucker decomposition — the same set of essays touches all of them, so they are one junction rather than several.

024681010⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹rank kept in every moderelative errordashes above: √(Σ tail²), the upper bounddashes below: max tail, a floor under the bestsolid: what the projection returnssmooth: pinned to the upper boundrank 10 error1.1·10⁻¹¹its upper bound1.1·10⁻¹¹the lower bound6.3·10⁻¹²error ⁄ bound1error ⁄ lower1.7inside the boundand sitting on it

A decomposition made only of SVDs

Everything the definition of tensor rank loses comes back if the SVD's algorithm is carried across instead of its definition — take the leading left singular subspace of every unfolding and project onto all of them. It exists, it costs d matrix decompositions, and its error is within √d of the best there is.

tensor · Multilinear rank smooth97.7%hilbert94.5%wave26.6%noise0.4%share of the core's energy on its 6 superdiagonal entrieskeeping only them: 0.152 against 7.94·10⁻⁶keeping only them: 0.235 against 1.77·10⁻⁶keeping only them: 0.857 against 1.34·10⁻¹⁵keeping only them: 0.998 against 0.842orthogonal, and not diagonalsmooth on-diagonal0.98hilbert on-diagonal0.94wave on-diagonal0.27noise on-diagonal0.0044worst slice pair3.5·10⁻¹⁶the slices are orthogonalthe core is not diagonal

The orthogonality that cannot be diagonal

A matrix decomposition hands over orthonormal factors and a diagonal middle at once. For three indices the two come apart, and there is no arrangement that has both — so the question stops being which decomposition to use and becomes which of the two properties the computation needs.

tensor · Multilinear rank 123456710¹10²10³10⁴10⁵number of indicesnumbersentries: 6^dstored: 4n(d − 1)exponential against linearentries at d = 64.7·10⁴numbers stored120ratio389slope against d24‖T − Tₜₜ‖ ⁄ ‖T‖1.4·10⁻¹⁵one line is n^dthe other is a constant per index

The format that does not notice the dimension

A Tucker core is r^d numbers, so the format that repaired the definition still cannot go past five indices. Cutting between the indices rather than across them gives d − 1 ranks instead of d, storage linear in the number of indices, and a family whose ranks are two everywhere by an addition formula.

tensor · Tensor train 12345678910¹10³10⁵10⁷number of indicesrandom numbers drawna dense Gaussian sketchdashes: the tensor's own entriesa Khatri–Rao sketcha random matrix nobody can afforddense at d = 81.5·10⁸structured4032the tensor's entries1.7·10⁷dense ⁄ structured3.7·10⁴crossing at d2the sketch outgrows its tensorand the structured one does not

Sketching what is never unfolded

A range finder multiplies its matrix by a few random vectors. For a mode-k unfolding those vectors have nᵈ⁻¹ entries, so the random object is the size of the tensor divided by n — and by six indices it is larger than the tensor it is sketching.

randomised · Sketching 15913172110¹10⁶10¹¹10¹⁶10²¹10²⁶number of indicesnumbers storedthe tensor: n^dthe core: r^d + dnrthe train: (d − 2)nr² + 2nrthe curse, movedentries at d = 2010²⁶core1.1·10¹²train5920core ⁄ train1.9·10⁸entries ⁄ core9.5·10¹³the definition is repairedthe size is not

A compression of 10¹⁴ that still does not fit

A Tucker core of a twenty-index array at rank four is 1.1·10¹² numbers against the tensor's 1.05·10²⁶ — a compression by a factor of 9.5·10¹³ that is still nearly nine terabytes. The ratio is not the verdict. The verdict is a ceiling, and the ceiling is a number of indices.

tensor · Multilinear rank

Named alongside it

The objects these essays reach for when they reach for this one.

Low-rank approximationMultilinear rankTucker decompositionTruncated SVDUnfoldingCurse of dimensionalityEckart–YoungOrthogonalityTensor trainAlternating least-squaresCP decompositionExact ground truth

All concepts