The repair that costs exactly itself

An iteration that walks out of the set describes a run that cannot finish: the target’s nearest rank-two point is not in the rank-two set, so the iterates walk along a curve where the error falls as the inverse square of the terms and neither quantity ever settles. It names the ridge its own subproblems carry — the machine epsilon times the trace — and says what it is for: without it the run would end with a division rather than with a measurement.

That is a ridge chosen to keep an arithmetic from failing. The repair everybody recommends for a swamp is a much larger one, chosen to change the answer, and what it costs has a clean form.

What it buys #

Without a ridge, the border-rank run does what the first essay on this ladder measures: after three thousand sweeps its largest term is at 6.70 and still climbing, its error is at 3.27·10⁻³ and still falling, and it has not converged and will not.

At λ = 10⁻² the same run’s terms are held at 1.61, its error is 7.86·10⁻², and it stops — 798 sweeps rather than the whole budget. At λ = 10⁻¹ the terms are at 1.20 and the run stops at 69.

So the repair does what it is advertised to do and it does it completely. There is no partial mitigation here: a swamp is an unbounded trade between term size and error, a ridge puts a price on term size, and a trade with a price on both sides has an optimum. The run stops because the objective it is now minimising has a minimiser inside the set, which is exactly what the unregularised one does not.

What it costs, and the number is the ridge #

The interesting half is what the same ridge does to a fit that never had a swamp.

On a tensor built from three rank-one terms — the benign case the first essay uses as a control — the relative error the fit reaches reads:

The error is the ridge, to within a factor of two, across nine orders of magnitude. Not proportional with a constant to be fitted, not asymptotically — 9.73 against 10, 9.71 against 10, 9.45 against 10, 9.74 against 10, 9.66 against 10, in the leading digit at every setting.

That is a better answer than a caller has any right to expect and it makes the decision arithmetic rather than experimental. A fit that needs six digits cannot use a ridge above 10⁻⁶; one that needs three can use 10⁻³ and no more. There is nothing to tune and nothing to discover by trying: the price list is the parameter.

And the terms do not move #

The second measurement is the one that says what kind of error it is.

A ridge biases. The question is whether it biases the magnitudes of the fitted terms — in which case the decomposition is still the right decomposition, shrunk — or their directions, in which case the answer is a different answer. The congruence against the planted factors, which is the best over all permutations of the worst over all terms of the product of the columns’ cosines, measures exactly that.

It reads 1.000000 at every λ from 0 to 10⁻², and 0.999798 at 10⁻¹.

So the ridge shrinks the terms and leaves the directions where they were. A caller who wants the components — which is what a decomposition is usually computed for — gets them, at every setting where the error is tolerable at all, and the bias sits entirely in the weights. That is worth contrasting with what the regularisation field measures for a linear problem, where a ridge moves the solution vector itself and the whole question is how much of the data to believe; here the object being regularised is a product of factors, and the shrinkage has somewhere to go that does not move the answer’s shape.

The cost nobody quotes is in sweeps #

The error is not the whole price, and the column that says so is the one a table of errors does not have.

Without a ridge, the benign fit finishes in 55 sweeps. At λ = 10⁻⁶, 10⁻⁴ and 10⁻³ it runs the entire three-thousand-sweep budget without meeting its stopping test. At 10⁻² it stops at 721 and at 10⁻¹ at 95.

That is a factor of fifty-four in work, in the middle of the range where a caller would actually put the parameter. The reason is the stopping test rather than the fit: the run is asked to stop when the error stops changing, the ridge has moved the floor to λ, and the approach to a floor at 10⁻⁴ is slow in a way the approach to a floor at 10⁻¹⁵ is not — the objective is flat near its minimiser and the iterates crawl.

The leftmost point of that figure moving with the budget is the whole of what a ridge changes, said from the other end. An unregularised swamp’s terms are a property of the budget; a regularised run’s are a property of λ. A quantity that depends on how long somebody let the code run is not a measurement of anything, and converting it into one is a better description of what the ridge does than it removes the swamp.

Which ridge, and the one already in the code #

There are two ridges in this arrangement and it is worth separating them, because they are chosen by completely different reasoning.

The arithmetic ridge is the machine epsilon times the trace, and it is there so that a subproblem whose matrix has become singular by design returns a number rather than throwing. It is 10⁻¹⁴ here, it is below the error of any fit anybody wants, and it changes no answer: the benign fit reaches 9.8·10⁻¹⁵ with it, which is the rounding level.

The modelling ridge is 10⁻⁶ or 10⁻³ and it is a statement about how much term growth the caller is willing to pay for accuracy. It changes the answer by its own size, on purpose.

Confusing the two is easy because they are the same line of code, and the measurement above says what separates them: a ridge below the error the fit would otherwise reach is arithmetic, and one above it is modelling. The first is free and the second costs exactly itself, and there is no intermediate regime — the error tracks λ from 10⁻¹⁰ upwards, which is to say from just above the arithmetic floor.

The price list is conditional, and the condition is the problem #

Everything above is measured on a well-conditioned fit and on a boundary, and a caller reaching for a ridge is usually in neither of those situations. They have a run that is crawling, and the reason it is crawling is the third case: a genuinely rank-r tensor whose factors are nearly parallel, so the r × r system every sweep inverts is nearly singular. That is precisely the case a ridge is supposed to be for.

The error is not the ridge here. It is tens of times the ridge. At λ = 10⁻⁸ the fit reaches 3.04·10⁻⁶ — three hundred times λ — and at 10⁻⁶, 10⁻⁴ and 10⁻³ the overshoot is 37, 40 and 8. Without any ridge at all the same fit reaches 4.02·10⁻¹² in 3,388 sweeps, which is better than every ridged run by orders of magnitude.

The reason is that the ridge is competing with the conditioning rather than with the arithmetic. On a well-conditioned fit the subproblem’s matrix is far from singular and λ is a clean perturbation of it; on this one the matrix is nearly singular already, so adding λ to its diagonal changes it by a large relative amount and moves the fixed point much further than λ would suggest.

And at the heaviest setting the decomposition changes rather than shrinking: the largest cosine between two fitted terms goes from 0.932 without a ridge to 0.631 at λ = 10⁻², and the run stops after six sweeps. That is not the same answer regularised; it is a different answer, reached quickly, to a problem whose factors were built to be nearly parallel.

So the honest scope of the whole page is narrower than its first half suggests. A ridge costs exactly itself on a fit that did not need one. On a fit that is crawling because its subproblem is nearly singular it costs tens of times itself, converges no faster, and past a point returns a different decomposition — and that is the fit a caller reaches for it on.

What a ridge does not tell a caller #

The repair works and it destroys the diagnosis, which is the practical objection to using it by default.

A swamp is information. It says the model is wrong — that the target has no rank-r point near it, so the rank asked for is not a rank the data has — and the test that is a deadline turns that into a verdict at sweep twenty-one. A ridged run does not swamp, so there is nothing to detect: it converges, returns a decomposition with an error of about λ, and the decomposition is a rank-two approximation to a tensor whose distance to the rank-two set is zero and which no rank-two tensor equals.

The error it reports does not say so either. At λ = 10⁻² the border-rank run’s error is 7.86·10⁻² and the benign run’s is 9.66·10⁻³ — a factor of eight, on problems that differ by whether an answer exists at all. A caller reading only the error would call the first a slightly worse fit.

So the order matters, and it is the recommendation this page ends on. Diagnose first, then ridge. Run unregularised for fifty sweeps, read the elasticity, and only then decide whether the ridge is repairing a badly conditioned fit or hiding a model that is wrong.

Where this leaves the three cases #

The ladder now has three situations a run can be in and a repair that is right for exactly one of them, which is worth setting out as a table because the recommendation is not the one the literature gives.

A boundary — the target has no rank-r point near it. The terms grow from the first sweep, the elasticity crosses within fifty, and a ridge cures it completely at a cost of λ in error. It also hides it, which is the reason to diagnose first: the fit that comes back is a rank-r approximation to a tensor whose distance to the rank-r set is zero and which no rank-r tensor equals, and nothing in the error says so.

A badly conditioned fit — the tensor has a rank-r answer and the subproblems are nearly singular. The terms grow after several hundred sweeps, the elasticity crosses late, and a ridge costs tens of times λ while converging no faster than none at all. What this case wants is a better subproblem: the fit is solved through the normal equations of its Khatri–Rao system deliberately, because the alternative is a decomposition of a tall matrix — $n^{d-1}$ rows by $r$ columns — at every step, and it is exactly the arrangement that squares a condition number. A caller with a genuinely ill-conditioned fit and the budget for it should pay for the decomposition rather than penalise the squared system.

An ordinary fit — nothing is wrong, the terms do not move, and the elasticity never rises. Here a ridge is a pure loss of λ.

The table is the reason the test that is a deadline comes before this page rather than after it. A repair that is correct in one of three situations, harmful in a second and unnecessary in a third is worth having only alongside something that says which situation it is, and the something costs two logarithms a sweep.

What the field’s other ridges are for #

This collection has several regularisations and none of them is doing what this one does, which is worth a paragraph to keep the analogies from being imported wholesale.

When the answer is a choice and choosing without knowing are about an ill-posed linear problem where the data does not determine the answer: λ decides how much of the data to believe, there is a correct value of it, and a rule that finds it is the subject. The regularisation that legalises every order perturbs a saddle-point system so that its factorisation is legal under any ordering, and the perturbation is removable by refining against the unperturbed matrix. A constraint is a weight at infinity is the same move run backwards, with a weight taken to a limit rather than a penalty added.

Here the data determines the answer exactly, nothing is noisy, and the penalty is not removable — a fit refined against the unpenalised objective would walk straight back into the swamp. λ is a statement about the model rather than about the measurement or about the arithmetic, and it is the only one of the four where the parameter has no correct value to find.

The two things this does not measure #

Not a ridge that varies with the sweep. Everything here holds λ fixed for the whole run. The obvious construction is to start large and decrease it — which is what a continuation does everywhere else in this collection, and which would give a run that is bounded early and accurate late. Whether the error still tracks the final λ, or tracks something about the schedule, is unmeasured.

And not a penalty on the right thing. A ridge penalises the squared norm of each factor, which is a proxy for the quantity that actually diverges — the magnitude of the rank-one terms, a product of column norms across the modes. The two are not the same: a term can be held at size one by shrinking one factor and growing another, which a per-factor ridge permits and the swamp exploits. That it works anyway is worth noticing, and a penalty written on the terms rather than on the factors is the comparison this page does not draw.

Why this belongs beside the field’s other regularisation #

The tensor field and the regularisation field are answering different questions with the same line of algebra, and the difference is worth stating because a reader who knows one will import the wrong intuition.

When the answer is a choice regularises an ill-posed linear problem, where the difficulty is that the data does not determine the answer and λ decides how much of the data to believe. There is a correct λ, it depends on the noise, and choosing it is the whole subject.

Here the data determines the answer perfectly — the tensor is exact, there is no noise anywhere in the construction — and the difficulty is that the set the answer is being sought in is not closed. λ does not decide how much of the data to believe; it decides how large a term the fit may use, which is a statement about the model rather than about the measurement.

The consequence is that there is no oracle λ here and no L-curve to find a corner on. The error is monotone in λ, the term size is monotone in λ, and neither has an interior optimum — so the parameter is set by what the caller needs rather than found by a rule, which is the reverse of the position the regularisation field is in.

The refusals #

The claim under test is the flattering one: a ridge removes the swamp, so it is a repair with no cost on problems that do not have one. The first half is true and the second is what the benign column refuses. The assertion that a ridged fit reaches the same error as an unridged one is fed the seven settings and required to fail, at 9.66·10⁻³ against 9.8·10⁻¹⁵.

The second refusal is the other direction and is the reason the repair is worth using. Fed the congruence against the planted factors, the claim that the ridge moves the decomposition has to fail: it is 1.000000 at every λ up to 10⁻², so what the error measures is a shrinkage rather than a different answer.

And the third is a control on the swamp itself, since a page about curing something has to show the thing is there. The unridged border-rank run is fed the claim that its terms stop growing, and has to refuse at every budget drawn — 4.30 at five hundred sweeps, 5.31 at a thousand, 6.14 at two thousand and 6.70 at three.

Still open: a penalty on the terms rather than on the factors #

The gap between what diverges and what is penalised is the loose end here and it is a measurable one.

The quantity that grows without bound in a swamp is the magnitude of a rank-one term, which is a product of one column norm per mode. The ridge penalises each factor’s squared Frobenius norm separately. On a fit whose factors are normalised after every sweep those are nearly the same thing; on one that is not, they are not, and the iteration is free to move weight between modes.

A penalty written directly on the terms is a different subproblem — no longer a ridge, no longer a linear solve — and whether it buys a tighter bound for the same error, or merely a more expensive sweep, is the measurement. The prize would be a repair whose error is smaller than λ for the same bound on the terms, which the mismatch above suggests is available.

The second open question is the schedule. A ridge that decreases with the sweep is the obvious construction, it is what every continuation elsewhere in this collection does, and it has an obvious hazard: the swamp is still there at small λ, so a schedule that decreases too far ends in the same place the unregularised run does, with the terms starting from wherever the schedule left them.

One line #

A ridge converts an unbounded trade into a priced one, and the price on a fit that never needed it is the ridge itself, in the leading digit, at every setting from 10⁻¹⁰ to 10⁻¹.