A factorisation that is unique for once

Every essay in this field so far has been about something a tensor does worse than a matrix. The best approximation need not exist; the rank depends on the field; two typical ranks occur where a matrix has one; there is no decomposition that is orthogonal and diagonal at once; and an iteration over the natural model can walk out of the set it is searching.

This one is about the exception, and it is the reason the model is used at all.

What a matrix does not have #

A rank-r factorisation of a matrix is M = XYᵀ with X and Y having r columns. For any invertible r × r matrix P,

XYᵀ = (XP)(YP⁻ᵀ)ᵀ

which is another rank-r factorisation of the same matrix. So the factorisations form an r²-dimensional family, and no column of X means anything on its own: it can be replaced by any vector in the column space of X by a suitable choice of P.

This is not a defect and it is not usually noticed, because the decompositions anyone actually uses pin down the freedom with an extra requirement. The SVD asks for orthonormal columns and a decreasing diagonal, which leaves only sign flips and rotations within equal singular values. A QR asks for triangularity. A Cholesky asks for positive diagonal entries. The one tensor decomposition made only of SVDs inherits the same device and the same limitation. In each case the decomposition is unique because a constraint was added; the factorisation was never unique.

The consequence is the one this collection’s spectra field states: the columns of a truncated SVD are a basis for a subspace, and reading them as components is reading a choice of basis as a fact about the data.

What a tensor has #

For three indices the situation reverses, and the reason is a counting argument that fails for matrices.

A rank-r CP model is Σⱼ λⱼ aⱼ ⊗ bⱼ ⊗ cⱼ. The obvious freedoms are permuting the r terms and rescaling the three vectors of a term so their product is unchanged — and those are unavoidable, because they do not change the tensor. Kruskal’s theorem says that under a condition on the factors, they are the only freedoms.

The condition is stated in terms of the k-rank of each factor matrix: the largest k such that every k of its columns are linearly independent. Writing k_A, k_B, k_C for the three,

k_A + k_B + k_C ≥ 2r + 2

is sufficient for uniqueness up to permutation and scaling.

Why the analogue fails for matrices is worth one line. Two factors give k_A + k_B ≥ 2r + 2, and a k-rank is at most r, so the left side is at most 2r. The condition cannot be met with two factors, ever. It becomes satisfiable at three, which is exactly where the extra index buys something.

Measuring it #

A theorem about uniqueness is a statement about a set of solutions, and the way to measure it is to find several of them and ask how much they agree.

Six fits, from six random starting points, on each of three targets. Every run is checked to have reached its target — the worst residual across all of them is at the rounding level — so all of them are successful factorisations and the question is only whether they are the same one.

Agreement is scored by a congruence: match the terms of one factorisation to the terms of the other over all permutations, take the product of the cosines between corresponding columns in each mode, and report the worst term under the best permutation. It is 1 when the two differ only by permuting and scaling, and near 0 when they are different factorisations of the same object.

The first row is the whole point: six independent fits, six independent starting points, and one answer. The second is the boundary — the same rank, the same code, and no agreement about anything. The third is the comparison, and it is the row that says the first is remarkable.

Two of those three numbers are not the same kind of number #

Across 3, 4, 6, 8 and 10 starting points the three bars read 1.0000, 1.0000, 1.0000, 1.0000, 1.0000 for the case Kruskal’s condition holds, 0.1450, 0.1026, 0.0207, 0.0207, 0.0207 for the case it fails, and 0.1089, 0.1089, 0.1089, 0.0432, 0.0432 for the matrix. One column is a constant and two are staircases that only ever go down, which is what an order statistic looks like.

The caption below observes that the lower two bars fall when more starting points are used and the top one does not. That is right, and it means the three entries of the table cannot be read against each other as they stand. Swept over the number of starting points:

The unique case is flat at 1.000000 over a hundred and ninety pairs. Not “high”, not “close to one”: the same six digits however many times the question is asked. That is what a theorem looks like when it is measured, and it is stronger than the single row in the table above says.

The other two columns are minima over a growing sample, and they behave like it. The narrow tensor’s worst agreement falls from 0.215 to 0.012 across a factor of 190 in the number of pairs, and never rises. So 0.0207 is not a property of that tensor — it is the smallest of fifteen draws, and drawing ninety-one gives 0.0151, and drawing more would give less. The number would keep getting worse for as long as anybody kept measuring.

And the mean does not move at all. 0.215, 0.249, 0.203, 0.254, 0.240, 0.261, 0.259 — no trend across the same range. That is the property: two factorisations of the non-unique tensor, drawn at random, agree about a quarter, and they will agree about a quarter whatever the sample size.

There is a practical reading too, and it is the one a caller of a CP fit wants. Running the fit from several starting points and comparing the answers is the only diagnostic available for whether the factors mean anything — no residual can say it, since every one of these runs reaches the rounding level. The table says what to compute from those runs: the mean pairwise congruence, which converges to a property after a handful of pairs, rather than the worst, which drifts downward for as long as the loop runs. Six starting points is enough for the mean and is never enough for the minimum.

So the comparable table has 1.0000 against 0.25 rather than against 0.0207, and the contrast is not weakened by the change — it is a factor of four rather than a factor of fifty, and it is a factor that means the same thing at both ends. The fifty was partly the sample.

This collection keeps arriving at the same shape from different fields: a maximum or a minimum over a sample, quoted where a property was meant. It is worth naming here because the failure is a generous one in the usual direction — the minimum makes the argument look stronger — and the argument does not need the help. assertTheWorstAgreementIsAnOrderStatistic holds the flatness of the unique case over 190 pairs, the monotone fall of both minima, and the flatness of the mean.

What the score is, in detail #

The congruence deserves a paragraph of its own, because a badly built agreement score would make this page say whatever it was asked to.

Three things have to be quotiented out and no more. Permutation of the terms: two factorisations that list the same terms in a different order are the same factorisation, so the score maximises over all r! orderings. Scaling within a term: the three vectors of a rank-one term can be rescaled so their product is unchanged, so every column is normalised before comparison. Sign: a cosine is taken in absolute value, because flipping two of a term’s three vectors leaves the term alone.

What is not quotiented out is any mixing between terms. A factorisation whose first term is a combination of another’s first two would score low, and should: that is exactly the freedom a matrix factorisation has and this one is claimed not to.

The score reported is the worst term under the best permutation, not the average. An average would hide the case where three of four terms match and one does not, which is the interesting failure — a fit that recovered most of the structure and invented one component.

Why the narrow case fails #

The 2 × 2 × 2 rank-three case is not a pathology chosen to break the theorem. It is the smallest case in which the condition cannot hold, and it fails for a reason worth stating.

A k-rank is at most the number of columns and at most the number of rows. Here the factor matrices are 2 × 3, so every k-rank is at most 2 and the sum is at most 6, against a required 2·3 + 2 = 8. The condition fails by two, and it fails for every 2 × 2 × 2 tensor at rank three.

What that means concretely is that the rank-three decompositions of such a tensor form a continuum. Any one of them is as good as any other, the fits find different members of it depending on where they started, and the congruence between two of them is whatever the geometry happens to give.

So unique is not a property of the model. It is a property of the model together with the shape and the rank, and the condition is checkable before any fitting is done.

What generic means here #

The condition holds generically, and that word is doing enough work to be worth unpacking.

For random factor matrices of size n × r with r ≤ n, every k-rank is r with probability one — any r columns of a random n × r matrix are independent. So the condition becomes 3r ≥ 2r + 2, that is r ≥ 2, which holds for every rank above one.

So for a target built from generic factors of a shape wide enough to hold them, uniqueness is the rule rather than the exception, and the cases where it fails are the ones where a mode is too narrow — as in the 2 × 2 × 2 case — or where the factors themselves are degenerate.

That last is not a corner. Two nearly collinear columns in a factor make the k-rank formally r and numerically less, and the numerical version of the theorem degrades with the collinearity. The error field’s essay on the conditioning of a decomposition measures exactly that quantity: the condition number of the step alternating least squares takes is the condition number of the entrywise product of the factors’ Gram matrices, and it diverges as two terms line up.

Why the congruence and not the residual #

One methodological point, because it is the reason this page has a measurement at all.

Every one of the eighteen runs above reaches its target to the rounding level, so a residual comparison separates none of them. The residual measures whether the model reproduces the data, and every fit does. What is in question is a different property — whether two fits returned the same parameters — and no function of the residual can see it.

That is the same distinction as the orthogonality field’s. Two Gram–Schmidts reconstruct their matrix equally well and differ in ‖QᵀQ − I‖ by fifteen orders of magnitude, and the reconstruction error sees nothing. Here the quantity that has to be reported is a comparison between two runs rather than between a run and its input, which is not a form of measurement this collection has needed before.

The two routes to the same verdict #

The uniqueness claim can be checked two ways and this page uses both, which is the collection’s habit rather than belt and braces.

The condition is arithmetic on the factors: compute each factor matrix’s k-rank, add them, compare against 2r + 2. It costs three small rank computations and it is a prediction — it says what will happen before any fitting is done.

The experiment is six fits from six starting points and a congruence between every pair. It costs eighteen runs and it is a measurement — it says what did happen, without reference to any theorem.

They agree on both targets: the condition holds and the congruence is 1.0000; the condition fails and the congruence is 0.0207. A disagreement in either direction would be informative — a target satisfying the condition whose fits disagreed would mean a bug in the fitting, and a target failing it whose fits agreed would mean the condition is sufficient rather than necessary, which it is.

That last is worth being careful about. Kruskal’s condition is sufficient and not necessary: there are tensors that violate it and whose decomposition is unique anyway. So a failure of the condition predicts nothing on its own, and the reason the narrow case here does have a continuum of factorisations is measured rather than inferred.

What uniqueness is worth #

The practical value is the whole reason the model survives its other problems.

A subspace format — the Tucker core, the train — returns a basis for a space. Two runs of it would return two bases for the same space, and asking which basis vector is which component is a question with no answer. Every essay in this field about those formats has been careful to call them projections rather than decompositions for that reason.

A CP model returns terms, and under Kruskal’s condition the terms are the same terms whoever fits them. That is what allows the columns to be read as chemical species, or as sources in a mixture, or as factors in an experimental design — and it is a property no matrix factorisation has.

The whole of this field is therefore a trade with two sides. The subspace formats have existence, computability and quasi-optimality and return objects that mean nothing individually. The component model has none of the three and returns objects that mean something, when a checkable condition holds. Neither is the better format; they answer different questions.

Where the same question sits elsewhere on this site #

Two other fields ask a version of it and neither gets an answer this clean.

The regularisation field asks which of a family of solutions the data supports, and the answer is that it supports all of them and something outside the data has to choose. That is non-uniqueness of a different kind — not of a factorisation of a fixed object, but of the object itself — and every rule for resolving it is a heuristic scored against a truth that exists only because the problem was constructed.

The spectra field asks when an eigenvector is determined, and the answer is that it is determined to the extent that its eigenvalue is separated: an invariant subspace is well conditioned and the individual vectors inside it are not. That is the closest analogue, because it is also a statement that a set is determined and its basis is not.

Against both, the Kruskal case is unusually favourable: a checkable sufficient condition, generically true, with the conclusion that the parameters themselves are determined. It is the only place in this collection where a decomposition’s factors are the answer rather than a coordinate system for it.

The refusal #

The claim under test is the one the theorem is most often quoted as saying: that a CP decomposition is unique, full stop, and therefore its factors can be read as components.

Six fits are run on the 2 × 2 × 2 rank-three tensor, where the k-ranks sum to six against a required eight. All six reach the tensor to the rounding level. The assertion that every pair agrees to 0.99 is fed the worst pair, which is 0.021, and fails.

What the refusal protects is not the theorem but the conditional. A gate that only checked the wide case would confirm uniqueness on the tensors where it holds and say nothing about the ones where it does not — and the failure mode this field actually has is a practitioner quoting the theorem for a shape it does not cover.

The file’s other refusals cover the neighbours. One is fed a swamp run and required to refuse the claim that its terms stay bounded. The other is fed a benign run and required to refuse the claim that alternating least squares can go uphill, which keeps the monotonicity measurement honest.