A compression of 10¹⁴ that still does not fit

Every compression format is quoted the same way. The object had this many numbers, the representation has that many, and the quotient is the result. For a Tucker representation of a twenty-index array at twenty points a side the quotient is enormous: the array is 1.05·10²⁶ entries, its rank-four core is 1.1·10¹², and the ratio between them is 9.5·10¹³. The sentence that usually follows is that the format which repaired the definition has solved the problem it inherited.

It has not, and the reason is arithmetic rather than analysis. In double precision 1.1·10¹² numbers is 8.8·10¹² bytes, which is nearly nine terabytes. Nothing about a ratio of 9.5·10¹³ changes that, because the ratio is a comparison against an object that was never going to be stored under any circumstances — a comparison with the impossible, which carries no information about whether the answer is possible.

The number that does carry it is absolute rather than relative: the size of what comes back, against the memory that has to hold it. Once the question is asked that way, the storage counts the figure draws can be inverted. Instead of asking how many numbers a representation of d indices takes, fix a budget and ask for the largest d whose representation stays under it. Every curve then becomes a ceiling — a number of indices rather than a number of numbers — and the ceilings turn out to be small, far apart, and ordered in the opposite direction from the ratios.

A ratio is a comparison with something that was never going to be stored #

The three lines above are counts, not estimates. The array is n^d because that is what an array is. The core is r^d + d·n·r because the core cannot be made diagonal — if it could, the representation would be d·r vectors and a list of r numbers, and the whole difficulty would disappear. The factors, d·n·r = 1,600 at these settings, are negligible against either of the other terms and never decide anything.

What the ratio measures is therefore the distance between two exponentials, n^d and r^d, and that distance is (n/r)^d. At n = 20 and r = 4 it is 5²⁰, which is 9.5·10¹³, and every digit of it is a statement about the array: how absurdly large the uncompressed object would have been. It says nothing about the core except by subtraction.

The failure mode this produces is not hypothetical and it is not confined to this field. A hierarchical representation of a matrix reports a ratio in exactly the same way, and there is an essay here about a case where one renumbering of the same matrix took the representation from 27,008 numbers to 118,208 — more than the 65,536 entries of the dense matrix it was compressing. The condition number did not move, the norm did not move, and the format still reported a representation. A ratio below one would have caught that instance; a ratio of 9.5·10¹³ catches nothing, because the denominator is so large that almost any numerator divides into it impressively.

So the quantity to state is the numerator alone, in the unit the machine is bought in. Eight bytes is what a double occupies, and the arithmetic from there is not subtle: 10⁶ numbers is eight megabytes, 10⁹ is eight gigabytes, 10¹² is eight terabytes. The rank-four core at twenty indices is the third of those. It is not a compression that worked; it is a compression whose output is a large cluster’s worth of memory, arrived at from an input that had no physical meaning at all.

The same three lines, read the other way round #

The inversion is mechanical. Each curve is a monotone function of d, so for a fixed budget B there is a largest d with the count under B, and that integer is the ceiling. Against 10⁹ numbers — eight gigabytes, one generous machine — the three lines in the figure give six indices for the array itself, fourteen for a rank-four core, and 3,125,001 for the train.

Those three numbers are the essay. Six is what an uncompressed array reaches: a modest 20 × 20 × 20 × 20 × 20 × 20 grid is 6.4·10⁷ entries and a seventh index would be 1.3·10⁹. Fourteen is what the repair buys, and it is a real gain — eight more indices, an object with 1.6·10¹⁸ entries described inside eight gigabytes. And the third number is not a ceiling in any useful sense, because the train’s count is linear in d, so no realistic number of indices exhausts a realistic budget.

The other ranks fill in between. At the same budget the ceilings run 9 at rank eight, 11 at six, 12 at five, 14 at four, 18 at three and 29 at two. Every one of them is computed from the same two expressions the figure draws, and every one is an integer that could have come out differently: they are the largest d for which r^d + 20dr stays under 10⁹, found by counting up rather than by rounding a logarithm, so a ceiling of 14 means that fifteen indices genuinely exceeds the budget and not that a formula said so.

The spread is the first thing worth noticing. Between rank two and rank eight — a factor of four in a parameter nobody chooses freely — the ceiling moves by twenty indices, which is a factor of 20²⁰ in the size of the array being represented. The rank decides more about what is reachable than the machine does, and the next figure is the sharp end of that.

The rank that approximates better reaches fewer indices #

Raising the rank is what a reader does when the truncation is not accurate enough, and it is the right move: the discarded energy in each unfolding falls, and the error of the projection falls with it. The figure above is that move made once, from four to six.

The core goes from 1.1·10¹² to 3.66·10¹⁵ — a factor of 3,325, which is (6/4)²⁰ to seven digits, because two extra units of rank cost the same multiple in every one of the twenty indices. The ratio against the array falls from 9.5·10¹³ to 2.87·10¹⁰, and the ceiling falls from fourteen indices to eleven.

Three indices is the price of two units of rank, and it is worth stating in the units of the problem rather than in the units of the format. Three indices at twenty points a side is a factor of 8,000 in the size of the object that can be represented at all. A calculation that needed fourteen variables and was willing to accept a rank-four truncation is now a calculation that needs eleven, and whether that is acceptable is a question about the science and not about the numerical method.

This is the trade the ratio hides completely. Rank six compresses worse by the ratio — 2.87·10¹⁰ against 9.5·10¹³, a thousandfold worse — and it approximates better. Rank two compresses better by the ratio and approximates worse. The ratio is monotone in the rank and so is the accuracy, in opposite directions, so quoting the ratio as a measure of success reports the accuracy with its sign flipped. The same inversion appears in the two-index case, where the error of a best approximation is exactly the next singular value: nobody would quote how much of a matrix was discarded as evidence that the discarding went well.

The largest compression in the figure belongs to the only core that fits #

Push the rank the other way and the reversal becomes explicit rather than implied.

At rank two the core of a twenty-index array is 2²⁰ + 800, which is 1,049,376 numbers: eight megabytes, an object that fits in a cache hierarchy rather than in a machine room. Its compression ratio is 9.99·10¹⁹, the largest in the figure by six orders of magnitude over rank four.

So the ordering is complete and it runs backwards. Of the five ranks the count is drawn at here, exactly one produces a core that fits inside eight gigabytes at twenty indices, and it is the one with the largest ratio. Rank three is 3.49·10⁹, three and a half times over the budget, with a ratio of 3.0·10¹⁶. Rank four is 1.1·10¹² at a ratio of 9.5·10¹³. Ratio and fit are anti-correlated across the whole figure, because both are functions of the same rank and the ratio is (n/r)^d while the size is r^d.

That is the sentence the essay exists for, and it is worth being careful about what it does and does not claim. It does not say that a large ratio is bad. It says the ratio is a monotone re-encoding of the rank, and the rank is already visible, so the ratio adds nothing and inverts the reading. Two formats compared at the same rank on the same array have ratios in the same order as their sizes; the comparison is only ever misleading when the rank moves, which is exactly when a reader reaches for a compression figure to decide something.

There is a cost on the other side, and it is not small. A rank-two truncation keeps two directions per index, and on anything but the smoothest families that is a coarse approximation — the refusal at the foot of this page is a measured instance of how coarse. The ceiling says what fits; it says nothing at all about whether what fits is worth having.

A thousandfold of memory buys five indices #

The natural next question is what a bigger machine does about any of this, and the same inversion answers it exactly. Running the ceilings at three budgets a thousand apart — 10⁶, 10⁹ and 10¹² numbers, which is eight megabytes, eight gigabytes and eight terabytes — gives:

A million times the memory moves the array from four indices to nine and a rank-four core from nine to nineteen. Ten indices, for a factor of 10⁶ in hardware.

The rate is not a coincidence and it is not a property of the machine. A core of r^d numbers has ceiling d ≈ log B / log r, so a thousandfold budget adds 3/log₁₀ r indices, and that quantity depends only on the rank. It predicts 4.98 at rank four against the measured 5 and 5, 6.29 at rank three against 6 and 7, 9.97 at rank two against 10 and 10, and 2.31 for the array itself against 2 and 3. The rank-three row above is the least regular of them, and it is the one where the prediction sits furthest from an integer.

So the machine buys indices logarithmically and the rank sets the exchange rate. A calculation that needs one more variable than the memory allows can be run by finding a thousand times the memory, or by lowering the rank by one, and on this figure those two moves are worth about the same. The second is free and the first is not, which is the whole reason the accuracy question and the storage question cannot be separated in this format.

It is also why the honest planning statement is a ceiling and not a ratio. A ratio invites the thought that the next machine will help; the table says the next machine helps by two or three indices, and the one after that by two or three more.

Fix the indices and the same arithmetic returns a rank #

The inversion can be run along the other axis, and it is the reading a practitioner actually needs, because the number of indices is usually given by the problem and the rank is the only free parameter.

Fix eight gigabytes and twenty points a side, and ask for the largest rank whose core fits. At three indices it is 999; at four, 177; at five, 63; at six, 31; at eight, 13; at ten, 7; at twelve, 5; at sixteen, 3; and at twenty, 2. Past twenty-nine indices there is no rank at all, because rank two is the smallest a truncation can be and still be one.

The figure above is the twelfth row of that list drawn: rank five is the largest rank a twelve-index core can afford at this budget, and its curve crosses 10⁹ between twelve and thirteen indices, which is the same fact seen the other way round.

Read down the list, the collapse is fast and it is concentrated. Between three and six indices the available rank falls from 999 to 31, which is a range in which the format is essentially unconstrained — any rank a truncation would plausibly want is affordable. Between eight and sixteen it falls from 13 to 3, which is the range where the choice of rank stops being a choice about accuracy and becomes a choice about whether the representation exists. Past sixteen there is nothing left to decide.

That collapse is the reason a Tucker representation is a two-index-to-five-index format in practice and not a d-index one, and it is a sharper statement than the crossing of the core and train counts at fixed rank, which the train essay locates between four and five indices. A crossing says which of two formats is smaller. This says at what point one of them stops admitting a rank worth having.

The other format’s ceiling is not a ceiling #

The train row of the table is the outlier and it deserves its own reading, because a number like 3,125,001 is not a ceiling that anybody will ever meet.

The figure is a different family and a different size from the counting figure, and it is here for one property: the lower line is straight on a linear axis. Its slope against d is 16.0, measured, which is 4n exactly for this family, and the representation is not an approximation — the error against the full array is 8.25·10⁻¹⁶, which is rounding.

A linear count inverts to a linear ceiling. Multiplying the budget by a thousand multiplies the train’s reachable d by a thousand — 3,126 to 3,125,001 to 3,125,000,001 — where the same thousandfold added five indices to the rank-four core. The two formats do not differ in how far they get; they differ in what kind of quantity the answer is. One returns a number of indices that grows like a logarithm of the memory, the other a number that grows like the memory itself.

That is the difference between moving a ceiling and removing one, and it is the honest way to state what the second repair did. The first repair fixed the definition and left the size exponential in d; the second changed which quantity the size is exponential in, and there is nothing left that grows that way. The same distinction turns up wherever a format is chosen: a hierarchical solve has a crossover measured in unknowns rather than in indices, because the object it compresses has two indices however large it gets, and a sparse factorisation has a size decided by an ordering rather than by a rank.

What the ceiling does not say #

Three things are outside this measurement and each of them can make the picture worse rather than better.

The ceiling is about storage, not about arithmetic. A representation that fits is not the same as a representation that can be operated on, and the gap is large: applying a Kronecker-sum operator multiplies the ranks by d and adding two representations adds theirs, so a solver in a compressed format produces something it cannot store and has to truncate every step. The essay on an iterate that must be made smaller is about what that costs, and its subject is a train, where the storage question here is answered most comfortably.

The ceiling assumes an equal rank in every mode. The multilinear rank is a tuple, and r^d is the count when every entry is the same. A core with ranks 8, 8, 2, 2, 2 is 2,048 rather than 8⁵, so a tensor whose modes genuinely differ in complexity reaches further than the table says. What the table gives is the count at the worst mode’s rank, which is what the ε/√d truncation rule tends to produce on a family with no distinguished direction.

And the array in the denominator is usually not a real array. Nobody allocates 1.05·10²⁶ entries; the object exists as a rule for computing entries, and the compression is applied to that rule. The ratio’s denominator is a hypothetical, which is the deepest reason it decides nothing — and the same observation is the whole content of the essay on an index that is a pair, where an n⁴-entry matrix is described by 2n² numbers exactly because assembling it was the error rather than the difficulty.

The refusal #

The claim under test is the one this page is named after: that a compression ratio is a measure of success, so a format that hands back a small fraction of the numbers has kept the object.

The counterexample is the smallest available. The rank-(2,2,2) higher-order SVD of an 8 × 8 × 8 array of independent normal entries is 2³ + 3·8·2 = 56 numbers against 512 — a compression of 9.14, which by the standard of this page is a modest one. Its relative error is 0.9581. The assertion that such a truncation is exact is fed that decomposition and refuses it.

The two halves of that measurement belong together. A ratio of 9.14 is reported by the format whether the array is smooth or noise, because the ratio is a function of the ranks and the sizes and never looks at an entry. The error is 0.9581 for the noise and a rounding for the family the format is for. So the statistic that is always available is the one that says nothing, and the statistic that says everything requires the comparison the compression was meant to avoid — which is why the ratio survives as the quoted number long after it has stopped meaning anything.

The rule that follows is one line and costs nothing. Report the size of what came back, in bytes, beside the error it came back with. Both are absolute, both are comparable against a machine and a tolerance rather than against a hypothetical array, and neither can be made to look good by making the uncompressed object larger. A representation that reduced a definition with no minimiser in it to a projection worth computing deserves to be reported by numbers that could have come out badly.