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ₖ(iₖ) an rₖ₋₁ × rₖ 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 Σₖ rₖ₋₁ nₖ rₖ, 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.

Six and seven dimensions are where the dense comparison stops being drawable, so the lower end of the slider is where the arithmetic can be checked against something:

One extra dimension has added twenty-four numbers to the train and multiplied the dense array by six. That is the whole mechanism, and the next stop is enough to show that twenty-four is a constant rather than a coincidence of four dimensions.

The storage is exactly 4n(d − 1), at all five stops and across two different n. Every rank is 2, so the two end cores hold 2n numbers each and the d − 2 interior cores hold 4n — a total of 4n(d − 1), which matches 48, 72, 96, 120 and 96 to the unit. Linear in the dimension, against a dense array that is nᵈ.

So the format’s advantage compounds rather than accumulating. Its share of the dense count falls 22%, 5.6%, 1.2%, 0.26% — a factor of about four per dimension, which is n/rank² and not a coincidence either. The title’s claim is that the format does not notice the dimension; the sharper version is that the dense array notices it exponentially and the train notices it linearly, so the ratio is where the whole effect lives.

And the same figure carries the case where the format costs more than dense. The random tensor’s ranks reach 6·36·216·36·6 at d = 6 — the maximum available at every cut — and its storage is 95,976 against a dense 46,656, so the train is 2.06 times larger than the array it is representing. At d = 4 it is 2,664 against 1,296, again 2.06 times. The overhead is not small and it is not a rounding on the win: a format with no low rank to exploit is a format that has added bookkeeping to a dense array.

The d = 7 row is drawn at n = 4 rather than 6, because 6⁷ is beyond what the figure can afford to form densely. It is the one row not comparable with the others on the dense column, and the closed form covers it anyway: 4·4·6 = 96.

Whether the rank stays put, which the sine family cannot answer #

The storage is Σₖ rₖ₋₁nₖrₖ, at most d·n·r², and that is linear in d only if r does not grow with d. The sine family cannot settle that: its rank is 2 by the addition formula whatever d is, which is what makes it a good check on the arithmetic and a useless one on the question.

Four families at n = 6 and a tolerance of 10⁻¹⁰, cut ranks written left to right:

a separable product gives [1,1] at d = 3 and [1,1,1,1,1,1] at d = 7 — one term, as a product of one-variable functions must be. sin of the sum gives [2,2] and [2,2,2,2,2,2] — the theorem. The reciprocal 1/(1 + Σi) gives [6,6] at d = 3 and [6,9,10,10,9,6] at d = 7. And noise gives [6,6] and [6,36,216,216,36,6].

The rank does grow on a realistic function. The reciprocal’s largest cut rank runs 6, 9, 9, 10, 10 at d = 3 through 7 — growing, and slowly enough that the storage stays nearly linear, but not constant. So “linear in d” is a statement about one family, and the honest general claim is that the storage is linear in d times a rank that grows like a logarithm rather than like a power. Which is still the difference between running and not running, and is a weaker sentence than the one the sine family alone would support.

And the profile is not flat. 6, 9, 10, 10, 9, 6 — largest at the middle, smallest at the ends, because a middle cut has to carry information about more of the array than an end cut does. So d·n·r² over-counts: the actual storage sums the profile, the end cores are cheap, and the reciprocal train at d = 7 is 2,400 numbers against 279,936 entries.

The control, which stores more than the tensor #

The noise family is the other half of the measurement and it fails in the way this collection has learned to watch for.

Its cut ranks are exactly min(nᵏ, n^(d−k)) — 6, 36, 216, 216, 36, 6 at n = 6 and d = 7 — which is the ceiling. Nothing is compressed, because there is nothing to compress, and that is the right answer.

What it does to the storage is not. The middle core is 216 × 6 × 216 = 279,936 numbers, which is the whole tensor, and the train totals 375,912 — a representation 1.34 times larger than the thing it represents, computed to the stated tolerance, with every rank correctly determined and no fault to report anywhere.

That is exactly the trap a renumbered kernel matrix falls into one field over: 180 per cent of dense storage, an accurate representation, and a code reporting success. Both formats degenerate the same way, and the reason is the same in both — a rank-revealing construction applied to an object with no rank structure returns the ranks honestly and pays the factorisation’s overhead on top of the entries it was supposed to replace.

So the format needs the same defence the partition does. A hierarchical matrix has an admissibility test that refuses a block rather than compressing it badly; a train has nothing of the kind, and the check that would serve is the one arithmetic already available — compare Σₖ rₖ₋₁nₖrₖ against Πnₖ before storing anything, and keep the array if the train is larger. It costs a multiplication per core and it turns a silent 1.34× into a decision.

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.