An iterate that must be made smaller

Every solver in this field produces a sequence of vectors. When the vector is stored densely that is a detail; when it is stored in a compressed format it is the whole problem, because the format is not closed under the operations the method performs.

What the arithmetic does to the ranks #

Two operations, and both of them grow the representation.

Applying the operator. The d-dimensional model problem is a Kronecker sum, so applying it is d mode products summed. Each mode product leaves the ranks alone and the sum of d of them multiplies them by at most d. So Ax has ranks up to d times x’s.

Adding two iterates. A conjugate gradient step is x ← x + αp and p ← r + βp, and adding two representations concatenates their factors: the ranks add, which is what a train’s storage is made of.

Put the two together and one step takes ranks r to something like (d + 1)r. After five steps that is 1,000r on the three-dimensional problem, and the representation is larger than the tensor it is representing.

So a solver in this format has no choice: every step is followed by a truncation back to something affordable — the rank that has to be guessed in another field’s words, and the whole essay is about what that costs.

The measurement the format cannot make #

The interesting number is what the step wanted, and a code in this format has thrown it away by the time anyone could ask.

So the arithmetic here is dense, deliberately. The iterate is carried as a full array, its true cut ranks are read at every step, and the truncation is applied by a round trip through the compressed format. That is not how a real solver works and it is the only way to see the quantity the truncation exists to control.

On the three-dimensional problem at ten points a side with a constant right-hand side, the un-truncated step asks for five at every step from the third onwards. A budget of three gives three. The truncation is therefore not an occasional tidy-up; it is happening at every step of every run, and the distance between the two residual curves on the hero figure is what it costs.

What the budget is worth #

The ladder is the measurement, and it has to be run twice because the answer depends on something other than the truncation.

With a constant right-hand side, the floors are

0.118, 0.0107, 3.6·10⁻⁴, 5.4·10⁻⁶, 1.1·10⁻¹³

at budgets of one, two, three, four and six. About two decades a column, and then the floor disappears — because the solution of this problem is a train of rank five, and once the budget reaches five the truncation has stopped removing anything.

The figure walks the same ladder, and its second column is the one the summary leaves out.

At budgets of 1, 2, 3, 4, 5, 6 and 8 the residual reads 0.119, 0.0112, 3.85·10⁻⁴, 6.32·10⁻⁶, 1.61·10⁻¹⁴, 1.61·10⁻¹⁴ and 1.61·10⁻¹⁴ and the storage reads 30, 80, 150, 240, 350, 350 and 350 numbers out of a dense thousand.

Over-budgeting is free, which is not how a budget usually behaves. At 6 and at 8 the storage is 350, exactly as it was at 5: the iterate never grows to fill the allowance, because there is nothing left in it to keep. So the cost of setting the budget too high is zero and the cost of setting it one too low is a factor of 4·10⁸ in the residual — an asymmetry sharper than any other knob in this collection, and one a reader can act on without knowing the answer’s rank.

The three numbers a caller can see are the residual, the storage and the budget, and past rank five only the third of them moves. That is worth saying because it is what makes the over-budgeting safe in practice rather than merely in this measurement: a code that sets its budget generously does not have to know it guessed high, because nothing in what it spends or in what it returns records the guess.

With independent normal entries in the right-hand side, the same ladder on the same operator gives

0.969, 0.925, 0.874, 0.801, 0.656, 0.470

at budgets of one to eight out of a possible ten. Eight columns of a ten-column answer buy a factor of two — which is the nothing-to-compress control arriving in a solver.

So a floor is not a property of the truncation. It is a property of the answer, and the same budget is free on one problem and useless on the next. What it is not is the distance from the answer to the set, and the next section is by how much.

The floor is worse than the distance to the set #

The natural account of the floor is that the truncation projects onto the rank-k set, so where the iteration stops is where the answer’s own tail begins. That is a statement about the answer, and it is checkable: solve the same system exactly by fast diagonalisation, take the cut-1 unfolding’s singular values, and read the relative tail beyond rank k.

On the constant right-hand side, whose answer is a train of rank five: the floor at a budget of one is 1.18·10⁻¹ against a tail of 1.39·10⁻², a factor of 8.5. At two, 1.06·10⁻² against 4.79·10⁻⁴ — 22.1. At three, 3.57·10⁻⁴ against 1.04·10⁻⁵ — 34.2. At four, 5.30·10⁻⁶ against 1.03·10⁻⁷ — 51.2.

On the random right-hand side: 1.17, 1.30, 1.52 and 1.97 at budgets of one, two, four and eight.

The floor is above the tail at every budget on both problems. The truncated iteration does not reach the best rank-k approximation of the answer; it reaches something between eight and fifty-one times worse on the low-rank problem, and up to twice as bad on the other.

Why, and why it gets worse with the budget #

One qualification, because two of the constant family’s rows are excluded above and the reason matters. Its answer is a train of rank five, so at a budget of six the tail beyond it is 7.8·10⁻¹⁷ and the floor is 1.5·10⁻¹³ — both at the rounding level, and their ratio of two thousand is a ratio of two noises rather than a measurement. The comparison is only meaningful while the tail is above the arithmetic, which on that problem is budgets one to four.

That boundary is worth naming rather than hiding, because it is where the essay’s headline claim becomes unfalsifiable in the good direction: once the budget reaches the answer’s own rank the truncation removes nothing, the floor is the iteration’s own convergence, and there is no penalty left to measure. Everything above is about the regime before that, which is the regime a real problem is always in — nobody knows the answer’s rank in advance, and if they did they would not need the sweep.

The truncation is applied to the iterate at every step, not once to the answer at the end. So the iterate never leaves the rank-k set, and what the method is doing is descending inside a non-convex set rather than descending freely and projecting at the end. Where a projection lands and where a constrained trajectory stops are different points, and nothing makes the second the first.

That is the same geometry the alternating least-squares essay measures, costing something different. There an optimiser confined to a set that does not contain its own limit points walks off to infinity; here one confined to a set that does contain its limit points simply stops early, in a place the set’s nearest point is not.

And the factor grows with the budget — 8.5, 22.1, 34.2, 51.2 on one problem and 1.17, 1.30, 1.52, 1.97 on the other, monotonically in both. That is the opposite of what a projection account predicts, under which the two quantities would differ by a fixed constant at worst, and it is the number worth having before sizing a budget: a larger budget buys a lower floor and a worse fraction of what that budget could have bought.

So the honest form of the field’s headline is narrower. A budget of k does not buy the best rank-k answer. It buys whatever a conjugate gradient can reach without ever leaving the rank-k set, which on these problems is one to two orders worse — and the gap between those two things is not a property of the answer, it is a property of having truncated at every step rather than once.

The step, in detail #

It is worth writing out what one step actually does to the representation, because the growth is not a vague statement about complexity.

Start with x of rank r. Then:

• Ap has rank at most d·r_p, because the operator is a sum of d terms each of which preserves ranks.
• αp has rank r_p, since scaling does not change a factorisation.
• x + αp has rank at most r + r_p.
• b − Ax has rank at most r_b + d·r.
• r + βp has rank at most (r_b + d·r) + r_p.

Every one of those is an upper bound and every one of them is attained generically, which the measured before column on the hero figure confirms: the un-truncated cut ranks climb to the ceiling the reshape itself imposes within three steps.

The truncation applied afterwards is the format’s own, so it costs d − 1 decompositions of reshapes of the iterate. On a problem where the iterate is genuinely low rank those decompositions are of small matrices and the cost is negligible; on a problem where it is not, the truncation is the dominant expense and it is buying nothing, which is the second ladder above.

Why that is not what the neighbouring fields found #

This collection has two other essays about a truncation inside an iteration, and both of them find a floor. Putting the three together is the point of this one.

The hierarchy field performs a Cholesky entirely inside a compressed format, with the number of truncations a count rather than a parameter — ninety-eight of them at the deepest level — and finds the residual below the representation’s own error at every depth. Its conclusion is that the leaf size can be chosen from the machine, because there is no accuracy term in the trade.

The residual-gap essay finds a conjugate gradient run whose reported residual falls below the unit roundoff while its true residual does not, and traces the gap to the size of the iterates rather than to any single rounding.

Both of those are about a truncation whose error accumulates or fails to. This page is about a truncation whose error may be zero — and the condition for that is not a property of the truncation at all. That is a genuinely different finding, and it is the one a practitioner needs, because it says the question to ask about a rank budget is not how much accuracy does it cost but is the answer in the set.

What the orthogonality costs #

The method here is conjugate gradients, and truncating inside it breaks the thing the method is built on.

A short recurrence works because each new direction is automatically orthogonal to every previous one, which is a consequence of exact arithmetic and of the iterates lying in the Krylov subspace. Projecting each iterate onto a low-rank set takes it out of that subspace, so the conjugacy is lost immediately and completely — not gradually, as it is in finite precision.

Nothing here repairs it. The residual is recomputed from the iterate at every step rather than updated by the recurrence, so the number plotted is a true residual of a real vector, and the method’s own bookkeeping is left to be as wrong as the truncation makes it. That is the honest arrangement: a plot of the recurrence’s own residual would show something much better than the truth, which is exactly the defect the residual-gap essay is about.

What a real code does about it is restart, or use a method that does not rely on a short recurrence, or re-orthogonalise against a stored basis — and all three cost storage, which is what the format was for.

What decides whether a right-hand side has a rank #

The two ladders above are extremes and the practical question is which one a given problem resembles.

For the model problem the answer is available in closed form and is worth having. The solution is A⁻¹b, and the inverse of a Kronecker sum is not a Kronecker sum but is within any accuracy of a short sum of them — half a term a decade, which the tensor field measures. So A⁻¹ applied to a rank-one b gives something of low rank, and applied to a full-rank b gives something of full rank.

That is a statement about b and not about A. A right-hand side that is a product of one-variable functions, or a sum of a few such products, gives a low-rank solution; a right-hand side sampled from data gives whatever it gives. And the rank of b is cheap to compute before any solving happens: it is d − 1 decompositions of reshapes.

So the honest workflow is to measure the right-hand side’s ranks first, and to treat a large one as evidence that the format is the wrong one rather than as a reason to raise the budget.

Where this leaves the field’s other methods #

Three of them transfer and one does not.

Stationary methods transfer cleanly. A Jacobi or Gauss–Seidel sweep on a Kronecker sum is a mode product and a scaling, its rank growth is bounded per step, and there is no recurrence to break. The rates are the ones the model problem’s closed-form spectrum gives, unchanged.

Multigrid transfers, and the coarse grids are cheaper in this format than in any other, because restriction and prolongation are mode products. What does not transfer is the argument that the work per unknown is constant, since the ranks may grow as the grid refines.

Preconditioning transfers and is where the format is strongest: a Kronecker-sum preconditioner is applied by the exact solve the tensor field describes, and applying it does not grow ranks at all.

Krylov methods transfer worst, for the reason two sections above. The method whose whole advantage is a short recurrence is the method a projection breaks.

What it would take to do better #

Three things a real code does that this measurement does not, and each of them is a different trade.

Truncate less often. The growth is bounded per step, so a code can afford to let the ranks rise for a few steps and truncate every third one. That reduces the number of decompositions and increases the peak storage, and where the optimum sits is a property of the machine rather than of the mathematics — which is the same shape of answer the cost field gives about block sizes.

Truncate adaptively. A fixed budget is the crudest rule. Cutting each iterate at a tolerance relative to the current residual keeps the truncation error below the iteration error at every step, which is the inexact-Newton argument the sequence field makes about inner tolerances: solve to the accuracy the outer loop can use, and no further.

Restart. Since the conjugacy is lost anyway, a method that does not depend on it — a restarted minimal-residual iteration, or plain steepest descent with an optimal step — loses nothing by the truncation and is easier to reason about. The measurement here uses conjugate gradients precisely because it is the case where the damage is clearest.

None of the three changes the finding. All of them are about how efficiently the budget is spent, and the finding is about whether spending it buys anything at all.

The counting that makes the format worth it anyway #

It is worth ending on the arithmetic that motivates the whole exercise, because two negative measurements in a row misrepresent the situation.

At d = 5 and n = 20 the problem has 3.2 million unknowns, which is a dense vector of 26 megabytes and a matrix that cannot be written down. A train of rank ten stores 5·20·100 = 10,000 numbers — 80 kilobytes — and every operation on it is a handful of small dense multiplications.

The measurement on this page says that the 80 kilobytes buy the answer when the answer is in the format and buy a factor of two when it is not. Both halves are worth having, and the second is worth having because nothing else reports it: a code that ran the second ladder and looked only at its residual would conclude that the problem is hard, when what has happened is that the representation is wrong for it.

The check is cheap and it is available before any solving happens. Decompose the right-hand side, read its cut ranks, and compare them against the budget. A right-hand side that is already at the ceiling has a solution that will be, and no amount of iteration changes that.

The refusal #

The claim under test is the one a rank budget invites: that it is a cost rather than an accuracy — spend more memory, get closer.

The assertion that a budget of eight gets the residual below 10⁻⁶ is fed the random right-hand side, on an operator whose answer has ten columns. It stalls at 0.47 and the assertion fails.

That is the right direction for the refusal. Asserting that the budget does floor the residual would pass on the structured right-hand side and on the unstructured one and would say nothing; asserting that it reaches the answer is the flattering reading, and feeding it the case where it is false is what makes the two ladders a finding rather than an illustration.

The file’s other refusals cover the neighbours. One is fed the sin family and required to refuse the claim that a function of a sum is separable into one term. The other is fed a tensor of independent normal entries and required to refuse the claim that the format compresses it — the counterweight this whole area needs.