An iteration that walks out of the set

The model this essay fits is the one the first two essays of this field are about: a sum of r rank-one terms, whose least r is the tensor’s rank.

Fix every factor but one and the model is linear in what is left, so each of the d subproblems is an ordinary least-squares solve — the object this collection has had from the beginning. Sweep round the modes until nothing moves. Every step is the exact minimiser of its own subproblem, so the objective can only fall, and the method has been the default for four decades.

What it does not have is a limit.

One sweep #

The arithmetic is worth writing out, because the whole of the essay’s numerical caveat is in one line of it.

For mode k, the model’s unfolding is $A_k(\odot_{i \neq k} A_i)^{\mathsf T}$, where ⊙ is the Khatri–Rao product — the column-wise Kronecker product of the other factor matrices, which is nᵈ⁻¹ × r. The least-squares solution for Aₖ is therefore

$$A_k \;=\; M_k \, \mathrm{KR} \, \bigl(\circledast_{i \neq k} A_i^{\mathsf T} A_i\bigr)^{-1}$$

where Mₖ is the tensor’s mode-k unfolding and ⊛ is the entrywise product of the small Gram matrices.

The inverse there is of an r × r matrix, and it is formed through the normal equations of that system rather than through a decomposition of the tall Khatri–Rao matrix. That is the road this collection has a whole essay warning about, and it is taken here deliberately: the matrix being squared is r × r with r at most five, and the alternative is a decomposition of an nᵈ⁻¹ × r matrix at every step of every sweep.

The consequence is stated rather than hidden. A ridge of the machine epsilon times the trace is added, and what it is for is precisely the case this essay is about — a swamp is a run in which that matrix becomes singular by design, and without the ridge the run would end with a division rather than with a measurement.

The objective can only fall #

The first measurement is the reassuring one and it is worth having because it establishes what the failure is not.

A rank-three fit to a tensor built from random rank-three factors stops itself after fifty-eight sweeps: the error runs from 0.487 to 9.7·10⁻¹⁵ and every sweep is at least as good as the one before it, which the assertion checks sweep by sweep rather than end to end. There is nothing wrong with the method’s monotonicity, and there is nothing wrong with its arithmetic.

The largest rank-one term over the same run does not move at all: 12.202 at sweep twenty and 12.202 at sweep two hundred, to five figures — and it is still 12.202 at forty thousand, because the run finished at fifty-eight and there is nothing left for it to do.

The law the swamp obeys #

The other run does not finish, and what it does instead has a closed form that the slider is enough to find.

At 200, 1,000, 5,000, 20,000 and 40,000 sweeps the swamp’s error reads 0.00616, 0.00469, 0.00266, 0.00141 and 0.00101 and its largest term reads 4.918, 5.618, 7.42, 10.15 and 11.99. Two hundred times the work buys a factor of 6.1 in the error and costs a factor of 2.44 in the size of the things being subtracted.

Multiply the two and the product is a constant. error × term² reads 0.149, 0.148, 0.146, 0.145 and 0.145 across the five, and the fitted slope of one against the other reads −2.07, −2.06, −2.04, −2.03 and −2.02 — converging on exactly −2 as the run lengthens.

That is the border-rank sequence’s law, arrived at by an optimiser that was never told about it. The explicit sequence of the essay two before this one has a residual of √3/n against terms of size n, so its product is a constant too. Alternating least squares, started at random and given no structure at all, walks along that same curve — which is the strongest available statement that the plateau is a boundary rather than slow convergence. A method converging slowly to a point inside the set would show the error falling with the terms bounded; this one shows an exact trade, at the exponent the geometry fixes.

And a reader watching only the error would see none of it. The error column falls monotonically at every length, from 0.00616 to 0.00101, which is exactly what a slowly converging run looks like. The term column is what says the run is leaving rather than arriving, and it is not a quantity any stopping rule computes.

And it can fall for ever #

The same code, at rank two, on the tensor whose rank is three and whose distance to the rank-two set is zero.

Over twenty thousand sweeps the error goes from 0.614 to 1.4·10⁻³ and the largest rank-one term goes from 3.98 to 10.15. Neither has finished. The error is still falling at the last sweep and the term is still growing, and a run of two hundred thousand would produce the same picture with both axes extended.

That is a swamp, and it is not a numerical accident, a bad starting point or a precision problem. It is the geometry of the previous essay arriving as a plateau in an iteration count: the sequence of iterates is a sequence of rank-two tensors approaching a rank-three limit, and there is nothing in the set for it to converge to.

The exchange rate, which is the number #

The product of the error and the largest term is the quantity the border-rank essay finds constant at √3 on the sequence Aₙ that defines the non-closedness. It is not constant here, and how it fails to be is the useful part.

Both products fall, so the product on its own does not separate the two runs. What does is what the error costs in term size. Over twenty thousand sweeps the swamp’s size grows 2.16× to buy a factor of 4.8 in the error. Over fifty-eight sweeps the benign run’s size grows 1.00× — 12.15 to 12.20 — to buy a factor of 8.9·10¹¹.

Written as an elasticity, log(size growth) over log(error fall):

canonical Aₙ sequence: 1.00. The ALS swamp: 0.49. A converging fit: 0.0001.

Three regimes and one number, and the number needs no reference answer, no knowledge of the tensor’s rank, and nothing beyond two quantities the trace already records.

And the iteration takes a much better path than the construction #

One reason the elasticity works where the product does not is worth naming, because it is the same reason a ratio beats a difference elsewhere on this site. The product error × size is a quantity with units in it: it scales with the tensor’s own norm, so its value says nothing until it is compared against something, and the two runs here start at 2.445 and 5.410 for reasons that have nothing to do with either being a swamp. The elasticity is a ratio of two logarithms of ratios, so every scale divides out — which is why the same threshold reads correctly on both runs without either being normalised.

The middle regime deserves its own sentence, because it is a fact about the algorithm rather than about the geometry.

At an error of 1.41·10⁻³ the canonical sequence Aₙ needs terms of √3/1.41·10⁻³ ≈ 1,230. The iteration reaches the same error with terms of 10.15 — a hundred and twenty times smaller. So the sequence that defines the infimum is not the sequence an optimiser follows to it, and it is a far more expensive route: it pays an elasticity of one where alternating least squares pays a half.

That is worth having because the canonical sequence is what everybody’s intuition about swamps is built from. Reasoning from it over-predicts the term growth by two orders of magnitude, which makes the swamp sound like an immediate arithmetic catastrophe when what it actually is, on this run, is a slow and entirely well-conditioned crawl.

It also corrects a stopping rule. Stop when the residual falls below the largest term times the unit roundoff is exact on the canonical sequence, where it fires at terms of 10⁸ and a residual of 10⁻⁸. Here the same test is twelve orders from firing after twenty thousand sweeps, because the terms are growing a hundred times more slowly than that rule assumes. The arithmetic floor is a real bound and it is not a swamp detector; it says when the numbers have stopped meaning anything, and this run’s numbers mean something for a very long time while meaning nothing useful.

The elasticity is the detector. It is available at every sweep, it separates the three regimes by an order of magnitude each, and a run whose terms are buying accuracy at an exponent near a half is in a swamp whatever its residual is doing.

The measurement that separates the two readings #

A long plateau at a small residual looks the same as slow convergence, and the objective alone cannot tell them apart. What can is the size of the terms.

The trace records, per sweep, the magnitude of each rank-one term — the product of its columns’ norms — rather than the largest column norm. That distinction matters: a single factor’s norm can be held at one by rescaling the others, without changing the model at all, so a plot of column norms can be made to show anything. The product is invariant under that rescaling and is the quantity that has to diverge.

Fitted over two hundred points, the relation between them is

$$\text{error} \;\propto\; (\text{term size})^{-2.03}$$

which is not the relation the explicit sequence of the previous essay gives. That sequence has error √3/n against a term size of n, so a product that is constant. The path an alternating fit takes is better — at a term size of 10.15 the explicit sequence’s error would be 0.17 and this fit’s is 0.0014 — and it is still walking out of the set rather than converging inside it.

Both statements are useful. The first says the diagnostic is real: a run whose terms are growing in proportion to its residual’s fall is not converging. The second says the rate is a property of the path rather than of the geometry, so quoting the explicit sequence’s constant as a prediction would be wrong.

What a practitioner sees #

It is worth being concrete about what the failure looks like from outside, because none of the usual stopping rules catch it.

A relative change test stops early and reports success. The error changes by less than 10⁻⁶ between sweeps for tens of thousands of sweeps, so any rule of the form stop when the objective stops moving fires almost immediately, at a residual that looks respectable.

A residual test reports success too. The fit reproduces the data to a fraction of a per cent, which on real data is well inside the noise.

The factors are the output, and they are the artefact. The returned terms have magnitude 10.15 against data of magnitude 1.7, and they cancel. Reading them as components — which is the entire reason for preferring this model to a matrix factorisation — reads the cancellation as structure.

So the diagnostic has to be the term size, it costs one line, and it is the number this page exists to put on a figure.

Why the objective is the wrong thing to watch #

The general point is worth separating from the tensor that occasions it, because it applies to every descent this collection runs.

A monotone objective proves that an algorithm is behaving. It proves nothing about whether the problem has an answer, and the two are usually conflated because for most problems the second is not in doubt. Least squares on a matrix has an answer; a linear system with a non-singular matrix has an answer; conjugate gradients on a positive definite operator has an answer. In every one of those the objective falling is the whole story.

Here it is half the story, and the missing half is a property of the parameters rather than of the objective. That is a shape this collection has met before under other names. The sequence field measures a Newton iteration whose residual falls onto a plateau that is the linearisation’s own error rather than the answer’s. The iterative field measures a conjugate gradient run whose reported residual goes below the unit roundoff while the true residual does not. In both, a quantity that looks like progress is measuring something other than the distance to the answer.

The rule that comes out of all three is the same: report the size of the thing being returned beside the size of what is left over. It costs one line, it is scale-free once the terms are measured as products, and it is the only number on this page that distinguishes the two runs.

The near-boundary case, which is the common one #

A target exactly on the boundary is a measure-zero event. What happens near it is the practical version and it is worse in one respect and better in another.

Near the boundary the best rank-two approximation exists — the set is closed except at the boundary itself, and a target at distance δ from a rank-three tensor with δ > 0 has a nearest rank-two point. So the iteration converges. What it converges at is a rate that degrades as the target approaches the boundary, and to factors whose size grows as the distance shrinks.

The error field’s essay on the conditioning of a decomposition measures exactly that: the condition number of the map from tensor to factors, along a sequence approaching the boundary, is 2n² + 1 — so a target ten times closer has a decomposition a hundred times more sensitive. And the practical consequence measured there is severe: every tensor on that sequence is exactly rank two, with its two terms written down in closed form, and a three-hundred-sweep fit from a random start does not find them.

The seed, and what it decides #

Every run above starts from random factors, so the natural next question is how much of the answer is the starting point.

On a target with a rank-r answer, every seed reaches it and every seed reaches the same factors — which is the next essay’s subject and is the one direction in which a tensor is better behaved than a matrix. On a target without one, the seeds do not agree about anything except that the residual falls, because there is no answer for them to agree about.

That is a cleaner separation than the randomised field’s, where the seed moves an answer that exists. Here it decides which member of a non-convergent family the run happens to be walking along, and the spread between seeds is not an error bar on an estimate — it is the absence of a thing to estimate.

Where the model is still the right one #

None of this is an argument against the model, and it is worth saying so plainly because the previous sections read as one.

The reason to fit a sum of rank-one terms rather than a subspace format is that the terms mean something. A chemical spectrum measured at several excitation wavelengths and several times is a mixture of components, and a rank-r fit is supposed to return the components. A subspace format returns a basis for the space they span, which is not the same information and is not what was asked.

And the model delivers that, under a condition that is checkable and generically true — which is the next essay. What this page establishes is the other side of the same coin: the delivery is conditional, the condition can fail, and when it fails the failure is silent under every stopping rule anyone normally uses.

The pair is the honest description. A CP fit is the only decomposition in this field whose output is interpretable, and the only one that can return an artefact while reporting success.

What to do instead #

Three answers, and this collection has essays about two of them.

Fit a different rank. The target has rank three; a rank-three fit reaches 10⁻¹⁵ in fifty sweeps and its terms do not move. If the rank is what is being estimated, a swamp is evidence that the rank is wrong, and the term size is the evidence.

Fit a different model. The multilinear rank and the train ranks are ranks of matrices; their sets are closed; and a projection onto them exists, is computable, and is quasi-optimal. Three essays of this field are about that trade, and what it gives up is the interpretability of the terms.

Constrain the factors. Requiring non-negativity, or orthogonality in one mode, or bounded norms, makes the feasible set closed and removes the phenomenon outright. What it does not do is make the original question well posed; it answers a different one, and the answer is a projection onto a set the data was not asked about.

The refusal #

The claim under test is the one every stopping rule implicitly makes: that a plateau is slow convergence, and the remedy is patience.

The assertion that the largest term stays within half again of its value at sweep ten is fed the twenty-thousand-sweep trace of the border-rank run. It fails, at a growth of 2.16.

The refusal is worth having in this direction rather than the other. It would be easy to assert that the terms do grow, and that assertion would pass on a run that had diverged for any reason at all — including a bug. What is asserted instead is the flattering reading, on the run where it is false, so what the gate is protecting is the diagnostic rather than the phenomenon.

The file’s other two refusals guard the neighbours. One is fed the 2 × 2 × 2 rank-three case and required to refuse the claim that every CP decomposition is unique, which is the next essay’s boundary. The other is fed a benign run and required to refuse the claim that alternating least squares can go uphill, which is what keeps the monotonicity measurement from being read as a claim about the method’s convergence.