A tensor that cannot be decomposed

This field’s first essay puts a number on how much a problem amplifies a perturbation, and every essay since has used it in one identity:

forward error ⪅ condition number × backward error

What has always been meant by the problem is a solve. A matrix and a right-hand side go in, a vector comes out, and the condition number is a property of the matrix. This essay is about the same identity applied to an object that is not a solve, and about a case where every quantity in it is known in closed form.

What is being conditioned #

A decomposition is a map. Its input is an object and its output is a set of factors, and the question is how far the factors move when the object does.

That is a different question from the one this field usually asks, and the difference is not cosmetic. The condition number of the tensor — however defined — is a property of the object. The condition number of the decomposition is a property of the map from the object to the parameters, and the two can be as far apart as anything.

The clearest way to see that they must be different is to note that the second depends on the rank being asked for and the first does not. The same tensor decomposed at rank two and at rank three has two different maps to condition, and only one object.

The sequence, which has an answer at every stop #

The tensors used here are the ones the tensor field’s third essay is built on:

Aₙ = n·(e₁ + e₂/n)⊗³ − n·e₁⊗³

Every one of them is a difference of two rank-one terms, so every one of them has rank at most two, and both terms are written down. There is no question of existence anywhere on this page: the answer is on the paper.

What the sequence does is approach a tensor of rank three, so its two terms become nearly collinear and nearly cancel. That is a statement about the factors, not about the tensor — the norms of the Aₙ are all within a few per cent of one another — and it is exactly the situation in which a decomposition’s conditioning and its object’s part company.

Why the tensor’s own conditioning is the wrong thing #

The natural first move is to ask what the tensor’s condition number is and to expect the answer to explain everything. It does not, and the reason is worth being precise about because it is the refusal at the bottom of this page.

Every Aₙ has a norm within a few per cent of √3 and a smallest unfolding singular value within a factor of two of one across the whole sequence. Whatever quantity is chosen to stand for “the conditioning of this tensor” — the ratio of its unfolding spectra’s extremes, the ratio of its largest and smallest entry, the sensitivity of its norm to a perturbation of its entries — none of them moves by more than a small factor while the difficulty rises by three orders of magnitude.

The reason is that the difficulty is not in the object; it is in the question. Asking for a rank-two decomposition of Aₙ is asking for two vectors per mode whose outer products cancel to leave something much smaller than either, and the sensitivity of that request is a property of the request. Asking for a rank-three decomposition of the same tensor is a different request with a small condition number.

This collection has met that distinction once before, in the essay about the object a question names against the object worth computing. Here it takes its sharpest available form: one object, two questions, and a conditioning that differs by 10³ between them.

The closed form #

Each sweep of an alternating fit solves an r × r system whose matrix is the entrywise product of the other modes’ Gram matrices. That matrix, not the tensor, is what becomes singular.

For Aₙ the exact factors are known, so the matrix can be evaluated on them rather than on whatever an iteration returned. With v = (1, 1/n) the factor matrix is [[1, 1], [1/n, 0]] in every mode, its Gram is [[1 + 1/n², 1], [1, 1]], and the entrywise product of two of them is

V = [[(1 + 1/n²)², 1], [1, 1]]

whose condition number has a closed form in n and whose asymptote is 2n².

Measured, it runs 9.57, 33.1, 129.0, 513.0, 2049.0 and 8193.0 at n = 2, 4, 8, 16, 32 and 64, and the fitted slope of log κ against log n is 1.96. The marks on the hero figure are the measured values and the dashed line is the closed form; they agree to eight digits.

Carried out along the slider the closed form is not an asymptote, it is the answer.

At n = 8, 32, 128, 512 and 1,024 the measured κ reads 129.031, 2,049, 32,769, 5.2·10⁵ and 2.1·10⁶ against 2n² + 1 of 129, 2,049, 32,769, 524,289 and 2,097,153. The “asymptote” of 2n² is a plus-one away from being exact at every size drawn, and the 1.96 fitted above is a fit to a formula that has a constant in it rather than to a power law.

And the two errors on the figure behave in ways the identity predicts and the essay’s summary does not. Starting from the exact factors, the error after three hundred sweeps reads 5.61·10⁻¹³, 8.85·10⁻¹², 1.41·10⁻¹⁰, 2.29·10⁻⁹ and 9.16·10⁻⁹ over the same five sizes. Divided by κ·u those are 39, 39, 39, 40 and 40 — the identity holding as an equality with a constant of forty, across five orders of magnitude of conditioning, on a decomposition rather than on a solve.

Starting from a random point, the error reads 0.0103, 0.0117, 0.0118, 0.0118 and 0.0118. It does not grow. It rises once between n = 8 and n = 32 and is then the same number to three figures over a factor of thirty-two in the size and a factor of a thousand in κ.

That corrects the sentence this essay was written around. A random fit does not get further away as the sequence goes on; it stops about one per cent from the answer and stays there, at every size. The identity says why, and it is the reason the two curves have to be read together: forward error is κ times backward error, and the random fit’s backward error is not at the rounding level — it is at whatever residual three hundred sweeps of alternation happen to reach on a problem whose steps are nearly singular. A quantity that is κ times that is not a statement about κ at all. Only the run started at the answer has a backward error small enough for its conditioning to be the thing being measured, and that run tracks 40·κ·u exactly.

The other quantity that closed form is checked against is the collinearity of the two terms, which is 1/√(1 + 1/n²) exactly and goes to one. So the two descriptions — the terms line up and the step becomes singular — are the same statement with a formula connecting them.

What it costs #

The identity says a forward error is the condition number times a backward error, and both are available here.

The backward error is tiny at every stop: the fit reproduces the tensor to a few parts in a thousand at worst, and to the rounding level where it succeeds.

The forward error is in the factors, and it is everything. A three-hundred-sweep fit from a random start reaches 2.1·10⁻⁴ at n = 2 and 1.2·10⁻² at n = 64 — that is, it gets worse as the sequence goes on, by a factor of 56 over five doublings, while the answer it is looking for stays exactly as available as it was. Whether that is the identity at work is a separate question and is measured two sections below.

The control that makes that a statement about conditioning rather than about the code is the third curve. Started at the answer — which is what an iteration that walks out of the set cannot be given — the same fit stays within 2.3·10⁻⁹ of it at every stop. Not the rounding level — the drift from an exact start is itself about κ times the unit roundoff, which is the identity again — but nine orders below what a random start reaches.

So: a tensor that is exactly rank two, whose rank-two decomposition is written down, and which a standard method cannot recover.

Two curves, and only one of them is the identity #

Both of the lower curves on the hero figure were read through forward = condition number × backward. Carried five doublings further than the essay takes them, they do completely different things.

The exact-start curve is the identity, and the constant is worth having. The last column does not move by more than a fifth while κ crosses four decades — 19.6, 22.8, 19.5, 19.1, 19.4, 18.9, 19.7 — so the drift from an exact start is 19.5 κu, not the κu this essay says. A constant that stable over that range is a property of the sweep rather than a fudge, and an order and a half is worth not losing. The one row that is off it is n = 2, at 198, and that is honest too: κ there is 9.57 against an asymptote of 9, so the sequence has not started.

The random-start curve is not the identity at all. It saturates. 1.17·10⁻² at n = 32 and 1.18·10⁻² at n = 512 — unchanged in the third digit while κ rises by a factor of 256. Divided by κ it falls by more than three orders across the sweep, which is exactly what a quantity that is not proportional to κ looks like.

So the sentence above — it gets worse as the sequence goes on, by a factor of 56 over five doublings — is true of the range it was measured on and stops being true immediately after it. Past n = 32 the fit does not get worse. It has already failed as completely as it can.

The reason is geometric rather than numerical, and it makes the figure say something sharper. The distance between two normalised factorisations is bounded: once a random start has converged to the wrong configuration, there is no further to go. So the conditioning explains why the fit fails and does not price how badly, because past the point of failure there is no price left to pay. What the rising κ is buying, in that regime, is not a larger error — it is a smaller and smaller set of starting points from which the right answer is still reachable, which is a statement about the basin and not about the identity.

There is a practical consequence, and it is the one a reader with a real tensor wants. A saturating error means the usual diagnostic does not work: watching the factor error grow as a problem gets harder is how somebody notices that they are near a boundary, and here it stops growing long before the boundary is reached. At n = 32 and at n = 512 a random-start fit returns the same 1.18·10⁻², so the number on the screen cannot distinguish a problem that is merely difficult from one that is five hundred times worse. What does distinguish them is the step’s condition number, which is computed anyway — it is the Gram product each sweep already inverts — and which rises by 256 across that same range. The quantity to report is the one nobody looks at, and it costs nothing.

Which leaves the figure’s control doing more work than it looked like it was doing. The exact-start curve is not merely nine orders below the random one; it is the only one of the two that the identity describes, and its constant of 19.5 is the measurement that says so. assertTheExactStartObeysTheIdentityAndTheRandomOneSaturates holds both halves — the constancy of the ratio on one curve, the saturation and the κ-independence on the other.

An ill-posed problem is one with an infinite condition number #

The limit is worth taking, because it connects this page to a phrase the regularisation field uses constantly.

As n grows, κ grows like 2n² without bound, and in the limit the tensor is the rank-three object whose distance to the rank-two set is zero and which no rank-two tensor equals. A decomposition of it at rank two does not exist, so the map being conditioned has no value there — and a map whose value does not exist is the limit of maps whose conditioning diverges.

That is what ill-posed means operationally, and this collection’s regularisation field says the same thing about a different object: a problem whose data does not determine its answer has an infinite condition number, and something outside the data has to choose. Here the something outside the data is the rank — which is a decision here as everywhere — and choosing it one higher makes the problem well posed instantly — a rank-three fit to the limit reaches the rounding level in fifty sweeps.

Where the collinearity comes from #

It is worth separating two things that both make a decomposition ill-conditioned, because only one of them is about the boundary.

Terms that are nearly collinear. Two rank-one terms whose vectors point nearly the same way are nearly the same term, so their coefficients are nearly indeterminate — the same mechanism as two nearly parallel columns in a least-squares design matrix, and this collection has an essay about that.

Terms that are large and cancel. Two terms of magnitude 10 whose sum has magnitude 1.7 mean that the data is a difference of things much larger than itself, which is the arithmetic field’s subject.

On this sequence they are the same phenomenon, because the construction produces both at once. They are separable in general: a decomposition can have well-separated terms of enormous size (no problem), or nearly collinear terms of modest size (a problem). The quantity that catches the second is the Gram product’s condition number, which is why it is what the code reports.

Two routes to the same number #

The conditioning here is checked the way everything else on this site is: by computing it twice.

The closed form comes from the algebra. The exact factors of Aₙ are written down, their Gram matrices are 2 × 2, the entrywise product of two of them is 2 × 2, and its condition number is an expression in n. Evaluating that expression involves no decomposition and no iteration.

The measured value comes from forming the same matrix numerically at the exact factors and taking its condition number with the site’s own decomposition. That involves a decomposition and is subject to rounding.

They agree to eight digits over six doublings, which is what makes the dashed line on the hero figure a check rather than a fit. At n = 1,024 they stop agreeing to eight digits, and the reason is instructive: the closed form is a difference of two numbers that agree to eleven digits, so the formula is the less accurate side of the comparison. That is stated in the assertion’s tolerance rather than hidden in it.

What can be done about it #

Three answers, and the first is the one that generalises.

Report the conditioning. It costs one small condition number per sweep, it is computable from quantities the method already forms, and it turns a silent failure into a reported one. Nothing else on this page requires knowing that the target is on a sequence.

Change the rank. A decomposition that is ill-conditioned at rank r is often well conditioned at r + 1, because the degeneracy is two terms trying to represent something that needs three. That is a rank-selection criterion with a number behind it, unlike the residual, which is flat.

Regularise the factors. Penalising the terms’ magnitudes makes the feasible set bounded and removes the divergence outright. What it does not do is recover the answer: it answers a different question, and the regularisation field’s whole subject is what that substitution costs.

What the identity looks like when both factors are known #

One more thing separates this page from the rest of the field, and it is the reason the sequence is worth a whole essay rather than a paragraph.

Everywhere else on this site, a backward error is a diagnosis. The algorithm runs, and an analyst then measures how far the problem would have to move to make the returned answer exact. The condition number is a separate measurement of the problem, and the identity is checked afterwards.

Here both factors are known in advance. The condition number of the step has a closed form in n, and the backward error of the fit is bounded by the tolerance the sweep is stopped at. So the forward error is predicted before anything runs, and the measurement is whether the prediction holds.

It does, in the direction that matters: the random-start error rises as the sequence goes on, at roughly the rate the conditioning does, while the exact-start error rises at κ times the unit roundoff. Neither is a tight prediction — the identity is an inequality and the constants in it are not one — and both are the right order.

The hierarchy field made the same observation about a compression tolerance, and its sentence is the one worth carrying: decide the digits the answer needs, divide by κ, and compress to that. Here the sentence reads decide the accuracy the factors need, multiply by κ, and that is the accuracy the tensor has to be given — and for the far end of the sequence there is no such accuracy, because κ has outrun the arithmetic.

The refusal #

The claim under test is the one that makes the whole page unnecessary if it is true: that an ill-conditioned decomposition is a decomposition of an ill-conditioned object, so the tensor’s own conditioning is the thing to look at.

The assertion that the step’s condition number stays within half of its starting value along the sequence is fed the two ends. It fails: 9.57 at n = 2 and 8,193 at n = 64, a factor of 856, on a sequence whose members all have nearly the same norm and exactly the same rank.

What that refusal records is that the conditioning here is not inherited. It is a property of the map being asked for — decompose at rank two — and changing the request to rank three makes it vanish without changing the object at all.

The file’s other refusals cover the neighbouring readings. One is fed a swamp run and required to refuse the claim that its terms stay bounded; one is fed the narrow uniqueness case and required to refuse the claim that every CP decomposition is unique; and one is fed a benign run and required to refuse the claim that alternating least squares can go uphill.