The format that does not notice the dimension

The previous two essays repaired what the definition of tensor rank lost. What they did not repair is the size of the answer.

A Tucker core is r₁ × r₂ × … × r_d, which at equal ranks is r^d numbers. At r = 4 and d = 20 that is 10¹², so the compression scheme’s compressed form outgrows the machine before the tensor does. The difficulty was not removed; it was moved from the object to its core.

Cutting the other way #

The Tucker construction unfolds the tensor across one index at a time: index k on the rows, everything else on the columns, d times. The train construction unfolds it between the indices: the first k on the rows, the rest on the columns, d − 1 times.

Both are reshapes of the same array and both give ordinary matrices with ordinary ranks. The difference is what a rank at each place means.

• A mode rank bounds how many directions one index needs. Truncating it leaves a core with the other d − 1 indices intact, so the core stays d-dimensional.
• A cut rank bounds how much information crosses that point in the index list. Truncating every cut leaves d objects each with three indices — a left rank, its own index, a right rank — and nothing with more.

That is the whole of it. The representation is d three-index cores,

T(i₁, …, i_d) = G₁(i₁) G₂(i₂) … G_d(i_d)

with G_k(i_k) an r_{k−1} × r_k matrix, so every entry of the tensor is a product of d small matrices, the first a row and the last a column. The storage is Σ_k r_{k−1} n_k r_k, which is at most d·n·r² — linear in d.

The construction is d − 1 matrix decompositions #

Nothing new is required to build it. Reshape the tensor so the first index is on the rows; decompose; keep the leading directions; that is the first core, and what remains is a smaller array with one fewer index and a rank index in its place. Repeat.

Each step is a matrix decomposition of a reshape and nothing else, so the format inherits the same properties the previous essay’s did: it exists, it is computed rather than fitted, and it is quasi-optimal — with √(d − 1) in place of √d, for the same reason and with the same proof.

The tolerance is split before the sweep starts. To reach a total relative error of ε the per-cut budget is ε/√(d − 1), so that the errors adding in squares reach ε rather than (d − 1)ε. Every train drawn here meets its stated tolerance, which is the badge on the accuracy figure.

One implementation detail from the previous essay carries over and matters more here. The reshapes become extremely lopsided — at d = 7 and n = 6 the first cut is 6 × 46,656 — so the decomposition is taken of the transpose, which is tall and thin, and the wanted vectors are read off its other factor. The Gram route would have been cheaper still and would have squared the condition number, which is the road this site has an essay about.

A rank that is written down #

Every rank in this field so far has been measured. One family’s is not.

sin(x₁ + x₂ + … + x_d) separates at every cut, by the addition formula: writing a for the sum of the first k variables and b for the sum of the rest,

sin(a + b) = sin(a)·cos(b) + cos(a)·sin(b)

which is two terms. So every cut matrix has rank exactly two, for every d, for every n, and the computed ranks are checked against a 2 that came from algebra rather than from a previous computation.

The storage that follows is also a closed form. Two cores of shape (1, n, 2) and (2, n, 1) at the ends and d − 2 of shape (2, n, 2) between them is 4n(d − 1) numbers, and the code asserts that count exactly rather than asserting that it is small. At n = 6 and d = 7 it is 144 numbers against 279,936 entries.

That is exact-ground-truth applied to a rank, which is a place this collection has not had it before. Every other rank on this site is a decision about a gap, taken at a tolerance; this one is a theorem, and the measurement is whether the arithmetic finds it.

The two lines #

The hero figure is the field’s argument in two curves and neither of them is fitted.

The upper one is n^d, which is a straight line on a logarithmic axis with slope log n. At n = 6 and d = 7 it is 279,936.

The lower one is 4n(d − 1), which is a straight line on a linear axis and therefore a logarithm on this one. Its slope against d is 4n = 24, a constant, and the fitted value agrees to twelve digits because there is nothing to fit.

The ratio at the right-hand end is 1,944, and it multiplies by n with every index added. The two arrays agree to 1.6·10⁻¹⁵.

What is worth noticing about the slopes is the direction they move in. Both lines lift as the grid is refined, and only the upper one steepens — the tensor’s slope against d is log n and the train’s is 4n, which lifts the line without tilting it. So the format is worth more on a finer discretisation of the same problem, which is the opposite of how a fixed-rank approximation usually behaves and is the property that makes it usable on the problems it is used on.

Why a chain rather than a tree #

The construction above cuts the index list at each of d − 1 places, which is one particular way of organising the same idea, and it is worth saying why it is the one that gets used.

The general object is a dimension tree: any binary tree over the index set, with a rank at every node saying how much information crosses it. The Tucker format is the tree of depth one — a root and d leaves. The train is the maximally unbalanced tree — a caterpillar. Everything between them is the hierarchical Tucker format, and it is a real family with real advantages: a balanced tree has depth log d rather than d, so a contraction through it is shallower and parallelises.

What the chain has is that its cores have exactly three indices each, always, which makes every operation in the format a sequence of small dense matrix multiplications with no bookkeeping. That is not a mathematical advantage and it is the reason the chain is what is implemented.

The same trade appears in the hierarchy field, where a partition of a matrix by a binary cluster tree could be balanced or not and the format that gets shipped is the one whose blocks are simplest to enumerate. In both cases the structure that wins is the one whose arithmetic is uniform rather than the one whose depth is smallest.

Where the ranks come from when they are not a theorem #

The sin family is the exception. For everything else the ranks are measured, and the accuracy sweep is what says how they behave.

On a five-index reciprocal array at n = 8, the largest rank runs 3, 5, 7, 8, 10, 11 as the tolerance tightens from 10⁻² to 10⁻¹². The storage runs 264, 680, 1,160, 1,664, 2,208, 2,504 against 32,768 entries. That is under one unit of rank a decade, with no cliff and no regime where a digit costs more than the last one.

The hierarchy field measures 0.554 columns a decade for a kernel block and this essay’s neighbour measures half a Kronecker term a decade for an inverse. Three different objects, three different arguments, and the same shape of answer — because all three are versions of a smooth function of separated arguments is nearly separable, and nearly costs a constant per digit.

What it does not do #

Three limits, and the first is the one that decides whether the format applies at all.

The index order is a choice and it is not free. The cuts are cuts of a list, so permuting the indices changes every rank. A tensor whose first and last indices are strongly coupled and whose middle ones are not will have a large rank at every cut in the middle, and the same tensor renumbered will not. That is the same sentence the sparsity field’s first essay makes about elimination orders and the same sentence the hierarchy field’s makes about clustering — and here as there, the numbering is not something a norm can see.

The ranks multiply along the chain. Applying an operator with train ranks p to a tensor with train ranks r gives ranks pr, and adding two trains adds their ranks. So arithmetic in the format grows the representation and every operation has to be followed by a truncation, which is the next essay in the iterative field.

It is not a decomposition into rank-one terms. Like the Tucker core, the train is a subspace structure rather than a component model. A code that wants interpretable components is in the other half of this field’s trade, and pays the price the alternating-least-squares essay measures.

What the cores actually are #

One more property distinguishes this format from a list of matrices, and it is what makes the arithmetic in it stable.

The cores can be put into a canonical form in which every one of them but a chosen “centre” has orthonormal columns when reshaped appropriately — left-orthogonal to the left of the centre, right-orthogonal to the right of it. In that form the norm of the whole tensor is the norm of the centre core alone, which is d − 1 small decompositions’ worth of work and is what makes a truncation in the middle of a long chain a local operation with a global error bound.

That is the same property the previous essay’s core has, applied along a chain instead of at a point, and it is the reason both formats belong to the half of this field’s trade that keeps orthogonality. A representation whose bases are not orthonormal has no cheap norm, no local truncation with a global bound, and no accounting for what an operation lost.

The measurements on this page do not exercise the canonical form — the arrays here are small enough to compare against densely, which is the honest way to check a format rather than checking it against its own bookkeeping. What the form buys is visible in the essay that iterates: every step there truncates, and a truncation whose cost is not local would be the dominant expense.

The comparison with the core, in one line #

Both formats are projections built out of matrix decompositions, both are quasi-optimal, and the choice between them at fixed rank is a comparison of two counted numbers rather than of two asymptotic classes.

A core is r^d + d·n·r and a train is (d − 2)·n·r² + 2·n·r. At r = 4 and n = 20 that is 576 against 800 at four indices and 1,424 against 1,120 at five, so the crossing is between them. Four indices: the core. Five: the train. Twenty: there is no competition.

The storage figure draws all three lines together — the tensor, the core and the train — over a range of d that covers the crossing, and the crossing is visible rather than argued.

The refusal #

The claim under test is the most natural wrong reading of the family whose ranks are a theorem.

sin of a sum is not a product of functions of the individual variables, and the reason the family is useful is precisely that it is not: a product would have rank one at every cut, and a format that could only represent products would be a format for separable functions, which is a much smaller class than the one this is for.

So the assertion that every train rank of the sin family is one is fed the computed ranks. They are all two, and it fails at the first cut.

The second refusal in the same file is the counterweight the whole field needs. A tensor with independent normal entries has full train ranks, so the format saves nothing on it — and the claim that it compresses to a quarter of its entries is fed a 6 × 6 × 6 array of noise and required to fail. The third is about the iteration: a rank budget on a problem whose answer has no rank buys almost nothing, and the flattering reading that a truncated solve converges has to be refused on the right-hand side where it does not.

At other settings #