One term too many

A matrix fitted with more components than it has is not a problem. The extra singular values come back at the rounding level, the extra components are numerical noise, and dropping them is what a decomposition made only of SVDs does on purpose at every mode. The rank is a number the decomposition reports, and asking for too many of them costs arithmetic and nothing else.

For three indices none of that holds, and the reason is the one this field keeps returning to: the set of rank-r tensors is not closed, so there is nothing forcing an unneeded term to be small.

At the exact rank the fitted terms are distinct: the largest cosine between two of them is 0.515, which is what three random directions in six dimensions look like. With one term too many it is 0.99927. With two, 0.99986.

The residual says nothing #

The first thing to establish is that no quantity a fit reports would tell a caller any of this.

The exact-rank fit reaches a relative error of 2.1·10⁻¹⁴ in 55 sweeps. The four-term fit reaches 1.0·10⁻¹³ in 76. That is five times larger in a quantity that is at the rounding level either way, on a run that took twenty more sweeps.

A caller comparing the two would conclude that four terms fit about as well as three, which is true, and that therefore the model with four is at least as good, which does not follow at all. The fit is excellent because a rank-four model contains every rank-three model — the extra term can be set to zero — so the error can only improve. What the error cannot report is how the improvement was obtained, and it was obtained by adding a term and subtracting a nearly identical one.

The extra term is not small #

The second thing a reader would expect is that the unneeded term comes back negligible, so that a caller could drop it and be left with the right answer.

The weights do not fall away. The ratio of the largest to the smallest is 4.7 at four terms, against 2.8 at three — so the extra term is the same order of magnitude as the ones the tensor actually has, and there is no gap anywhere in the list to cut at.

That is the difference from a matrix in one line. A truncated SVD’s weights are the singular values, they are ordered, they are a property of the matrix, and a gap in them is the rank decision this collection has a whole anchor about. A CP fit’s weights are a property of the rank that was asked for: change it and every weight changes, there is no nesting, and the list at rank four is not the list at rank three with something appended.

What the extra term actually did #

The cosine is the whole explanation and it is worth following.

Two of the four fitted terms are nearly the same rank-one tensor, with weights of similar size and opposite effect. Their sum is a small residual correction — the model needed a little of something the three terms could not supply — and the way the fit supplied it was by taking a large step in one direction and a nearly equal step back.

That is exactly the mechanism of a swamp, arriving from a different direction. In an iteration that walks out of the set the terms grow without bound because the target has no rank-two point near it; here they are held in check because the target does have a rank-three point, and the cancelling pair is the fit’s way of spending a degree of freedom it did not need. The terms are large, nearly parallel and nearly cancelling in both cases, and the difference is whether the process terminates.

Which is why the diagnosis for one is the diagnosis for the other. The collinearity of the fitted factors is a quantity every run already has — r(r−1)/2 cosines per mode, a few dozen multiplications — and it separates the two cases here by 0.515 against 0.99927 while the error separates them by nothing.

The size of the tensor does not dilute it #

A reader’s next thought is that this might be a small-sample effect: a 6 × 6 × 6 tensor has 216 entries and four rank-one terms have sixty-four parameters, so the fit might simply have room to misbehave.

The collinearity of the extra pair does not fall with the size of the tensor. More entries to fit and the same number of terms does not make the unneeded term smaller or more distinct, because the unneeded term is not fitting noise — there is no noise; the tensor is exact — it is exploiting a freedom the model has and the data does not remove, which is a rank that is not a property of the tensor seen from the fitting end.

Six starting points, six answers #

The variability across starting points is worth its own measurement, because it says what kind of object the returned decomposition is.

At the exact rank the six runs return the same decomposition. Not the same numbers — the terms come back in different orders, with the weight distributed differently between the factors — but the same three rank-one tensors. The congruence between any two of the six is 1.0000, and the congruence of each against the planted factors the tensor was built from is 1.000000, six times over. That is what a factorisation that is unique for once says to expect: six starting points, one answer, and the answer is the tensor’s.

At four terms they return six different decompositions. The pairwise congruence between them has a median of 0.193, a minimum of 0.056 and a maximum of 0.615 — so no two of the six runs agree even approximately about what the four rank-one terms are. Every one of them has an error at the rounding level: 2.5·10⁻¹⁴, 3.2·10⁻¹⁴, 3.9·10⁻¹³, 1.2·10⁻¹³, 1.0·10⁻¹³ and 7.1·10⁻¹⁴. Every one has a cancelling pair, with collinearities of 0.9993, 0.9762, 0.9997, 0.9922, 0.9995 and 0.9752.

One tensor, six equally good answers, and they have almost nothing in common. That is what a continuum of solutions looks like from the inside: the iteration lands somewhere on it and where depends entirely on where it started, which is the definition of a parameter that the data does not determine.

That is the practical meaning of an unidentifiable model, and it is the one thing a caller can check without knowing the answer. Run the fit twice from different starts and compare the decompositions. At the right rank the congruence is 1.0000 and past it the median is 0.193 — a separation of a kind no error and no weight provides. It costs a second fit, it needs no threshold, and crucially it does not need the tensor’s own factors to compare against, which the measurements above did have and a caller will not.

The two checks this page ends up recommending are therefore both comparisons rather than readings. The collinearity compares terms within one fit; the congruence compares two fits with each other. Neither is a number that means anything on its own, which is why neither appears in any implementation’s output — an interface returns a decomposition and an error, and both of the quantities that would say whether the decomposition means anything need two of something.

What a matrix does instead, in one paragraph #

The contrast is worth stating precisely rather than as an analogy, because every expectation a reader brings here comes from it.

A rank-k truncated SVD of a matrix is nested: the rank-four truncation is the rank-three truncation plus one more term, the terms are orthogonal, the weights are the singular values in order, and the whole family for every k comes out of one decomposition. Asking for k too large appends a term whose weight is the next singular value, which is genuinely negligible when the matrix is genuinely rank three.

A CP decomposition has none of those properties. It is not nested, the terms are not orthogonal — and cannot be made so while keeping the diagonal — there is no ordering of the weights that is a property of the tensor, and there is no single computation that produces the family. Four of the five things a reader is relying on are absent, and the fifth, that an unneeded term is small, is what this page measures and finds false.

What this means for choosing a rank #

The practical consequence is that the standard way of choosing a rank does not work here, and it is worth saying exactly which step fails.

For a matrix the procedure is: decompose once, look at the spectrum, cut where it falls. One computation, and the rank is read off it.

For three indices there is no spectrum to read. A fit must be run at each rank separately, and the quantity to compare across them is not the error — which improves monotonically and says nothing — and not the weights, which are incommensurable between ranks. What the measurements here say is available:

The collinearity at each rank. It is 0.515, 0.99927 and 0.99986 at three, four and five terms. The jump between the first and the second is the rank — a decision made on a gap, like every rank decision here, but on a gap in a quantity nobody reports.

And the sweeps. 55, 76 and 734 at three, four and five. A fit that suddenly takes ten times as long is a fit whose subproblem has become nearly singular, which is what a cancelling pair does to it — and is the same quantity the test that is a deadline reads for a different purpose one rung below.

Both are free, both are computed by any implementation already, and neither is reported by any that this collection has looked at.

Why the cancelling pair is not a failure of the algorithm #

Worth being clear about, because the natural reading is that alternating least squares has done something wrong.

It has not. It was asked to minimise the error over rank-four models and it found a rank-four model with an error of 10⁻¹³. Every sweep is the exact minimiser of its own subproblem, the objective fell at every one of them, and the answer it returned is a genuine and very good solution of the problem it was set.

The problem was set wrongly. A rank-four model of a rank-three tensor is an overparameterised model, its parameters are not identifiable, and the set of rank-four models achieving an error of 10⁻¹³ is a continuum rather than a point — so asking which one the iteration returns is asking about the starting point rather than about the tensor. The six starting points here return six different decompositions, all excellent, all with a cancelling pair, none of them the tensor’s own.

That is the uniqueness question one rung over. A factorisation that is unique for once establishes that a three-index decomposition is unique up to permutation and scaling when a checkable condition on the factors’ k-ranks holds, and that it holds generically. Overfactoring is the case where it does not hold, by construction: the condition is a statement about r terms in general position, and a fit with a cancelling pair has two terms in the worst possible position relative to each other.

The one case where the extra term is small #

The counterweight, because never harmless would be too strong.

If the tensor’s own rank-three terms are very well separated and the extra term has nothing to cancel against, it can come back small. That is not what happens on six of six starting points here, and it is worth saying why: the fit is not trying to be interpretable. It is minimising an error that is already at the rounding level after the third term, so the fourth term’s direction is decided by whatever reduces a residual of 10⁻¹⁴, which is numerical noise — and the cheapest way to move an already-tiny residual is a large cancelling pair — the same arithmetic cancellation takes the answer is about, used deliberately by an optimiser, because the pair’s difference can be made arbitrarily small while each half is large.

So the mechanism has a prediction attached: overfactoring should be worse the better the fit at the exact rank, because a smaller residual gives the extra term less real structure to find and more reason to cancel. That is the reverse of the intuition from matrices, where a well-fitting model leaves small singular values, and it is a measurement this page does not make.

The refusals #

The claim worth breaking is the one every reader brings from matrices: asking for more terms than the tensor has is harmless, because the extra ones come back negligible and can be dropped. The assertion that the extra term’s weight falls to the rounding level is fed six starting points at four terms and required to fail on every one — the smallest weight is a fifth of the largest, and there is no gap in the list to cut at.

The second refusal covers the reading that the fit has gone wrong. Fed the errors, the claim that overfactoring costs accuracy has to fail: 1.0·10⁻¹³ at four terms against 2.1·10⁻¹⁴ at three, on a run twenty sweeps longer. The fit is excellent and that is the problem.

And the third is a control on the exact rank, because a page about a fit misbehaving needs the well-behaved case to be genuinely well behaved. The exact-rank fit is fed the claim that its terms are nearly parallel, and has to refuse at 0.515; and fed the claim that its six runs disagree, it has to refuse at a congruence of 1.0000 between every pair.

Where the field’s three failures meet #

This ladder now has three ways a CP fit can be wrong while reporting an excellent error, and they are worth laying side by side because the diagnostics are different and none of them is the residual.

The rank asked for is too small and the target has no point in the set. The terms grow without bound, the error falls forever, and the elasticity read as a deadline catches it at sweep twenty-one.

The rank asked for is right and the problem is conditioned badly. The terms grow late, the fit converges eventually, and a ridge costs tens of times itself without helping.

And the rank asked for is too large, which is this page. The terms do not grow at all, the fit converges quickly, and two of them lie on top of each other.

The three have three different signatures in the same two columns a trace records — growing terms early, growing terms late, and terms that never grow — and a fourth quantity, the collinearity, that separates the third from the first two. All four are free. None is reported.

That is the standing complaint of this collection stated one more time in one more field: the quantity that would say whether an answer means anything is nearly always computable and nearly never computed, because an interface returns what was asked for and the thing worth knowing was not asked for.

Still open: the rank decision as a sweep #

Everything here fits one tensor at three ranks and reads two quantities. The obvious next thing is to make that a procedure and to price it.

A rank sweep that fits at r = 1, 2, 3, … and stops when the collinearity jumps is a decision rule, and it needs three things this page does not supply: a threshold on the jump, a policy for the starting points — since every fit is a different random start and the collinearity varies between them — and a cost, because it runs a fit per rank rather than one decomposition. Against a compression of 10¹⁴ that still does not fit, where the whole question is whether a format is affordable at all, a procedure that costs r fits may be the expensive part of the computation.

The second open question is the prediction above. If the cancelling pair is the fit’s way of moving a residual that is already at the rounding level, then overfactoring a tensor with noise in it should behave differently — the extra term would have real structure to find, and the collinearity would be lower and less diagnostic. That would mean the diagnostic is sharpest exactly where the model error is smallest, which is a convenient place for it to be sharp and is not where a practitioner works.

One line #

An unneeded term in a three-index fit does not come back negligible: it comes back as half of a cancelling pair at cosine 0.9993, with a weight a fifth of the largest, and the residual is as good as the exact rank’s.