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 4 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_tt‖ ⁄ ‖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^{d−1} 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

Named alongside it

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

Low-rank approximationMultilinear rankTruncated svdTucker decompositionUnfoldingCurse of dimensionalityEckart–YoungOrthogonalityAlternating least squaresCP decompositionExact ground truthKhatri–Rao product

All concepts