A fit with no answer to find

The rank that stops being typical counted the random n × n × 2 tensors whose real rank is n. Such a tensor is a pencil of two n × n slices, $(A, B)$, and its rank is n exactly when the eigenvalues of $A^{-1}B$ are all real, n + 1 otherwise. The share of rank n was 0.786 at n = 2, 0.500 at 3, 0.264 at 4 and 0.039 at 6, falling like a Gaussian in n: the lower rank is typical in theory and disappears in practice. The essay ended on the version of that result an algorithm meets. On a draw whose pencil has a complex pair, a rank-n fit “cannot converge to an exact decomposition and may not converge at all. How its residual and the size of its terms behave over iterations — whether it looks like the swamps alternating least squares is known for or like a divergence — is measurable on the same draws.”

The two possibilities it names are different failures, and the difference is the whole of this essay. A nearest point that is not there built the first: a tensor at distance zero from the rank-two set that no rank-two tensor equals, approached by rank-two tensors whose terms grow without limit while their error falls. A random rank-(n + 1) tensor is not at distance zero from anything. Whether a fit to one finds a best approximation, wanders, or does something else is not settled by that construction.

The same split at every size #

Three sizes, n = 2, 3 and 4. At each, random pencils are drawn from seeded Gaussian entries and sorted by their eigenvalues; the first eight with a complex pair and the first four with only real eigenvalues are kept. Each is fitted by alternating least squares at rank n, from two random starts, for 8,000 sweeps, recording at every sweep the relative error and the size of the largest rank-one term — the product of its three columns’ norms, the quantity an iteration that walks out of the set found climbing in a swamp.

The real pencils do what the algebra says they can. At n = 2 the fit’s error falls to $1.7 \cdot 10^{-13}$ within a few hundred sweeps and the terms settle at their exact sizes. At n = 3 two of the four real draws need more than 8,000 sweeps — their error is still $10^{-3}$ at the end, the slow convergence a fit that has an answer and cannot stop measured — but none of them has terms that grow.

The complex pencils all do something else, and it is the same something at every size. The error falls for a few hundred sweeps and stops falling: at n = 2 the first draw’s error is 0.1764 at sweep 300, 0.1756 at sweep 1,000 and 0.1752 at sweep 8,000. The largest term does not stop. It is 14.5 at sweep 300, 24.5 at sweep 1,000 and 66.8 at sweep 8,000 — growing like the 0.48th power of the sweep count, and still growing when the run ends.

Two starts, one error #

The first thing worth knowing about a fit with no exact answer is whether its answer depends on where it started. Alternating least squares on a tensor with several local minima can end at a different error from every start; the rank a sweep can vouch for built a rule on how often starts agree.

Here they agree, and to many digits. At n = 2 the two starts’ final errors differ by between $4 \cdot 10^{-7}$ and $6 \cdot 10^{-4}$ of the error on all eight complex draws — on five of them by less than $10^{-5}$. At n = 3 they differ by at most a quarter of a per cent; at n = 4, where the fits are further from settled at 8,000 sweeps, by up to six per cent on one draw and under one per cent on the other seven. Whatever the fits are approaching, they are approaching the same number from different directions.

That number is not an artefact of the iteration, and it can be computed without one.

The error is the distance to a surface #

A sum of n real rank-one terms has a pencil whose eigenvalues are all real — each term contributes one, the ratio of its two third-index coefficients. So every rank-n tensor lies in the region where the pencil’s eigenvalues are real, and so does every limit of rank-n tensors. A tensor whose pencil has a complex pair is outside that region, and the nearest the fit can come to it is the nearest point of the region’s boundary: the surface on which two real eigenvalues have merged into one.

For a 2 × 2 × 2 tensor the surface is a polynomial’s zero set. The determinant of $A + tB$ is a quadratic in t, its discriminant is positive when the two eigenvalues are real and distinct, negative when they are a complex pair and zero when they coincide — it is Cayley’s hyperdeterminant up to sign. The distance from a tensor to that zero set is a constrained minimisation in eight variables, and a Newton iteration on its stationarity conditions solves it to the rounding level without alternating least squares or rank-one terms anywhere in it.

The figure at the top of the page sets the two numbers beside each other. On all eight draws the fit’s error after 8,000 sweeps is above the distance to the surface by between 0.02 and 1.5 per cent, and never below it. The fit is approaching the distance to the boundary, from above, as far as it has got. The error has an answer, and the answer is a property of the tensor — how far its complex pair is from becoming a real double eigenvalue.

How much a missing rank costs #

The eight draws above were the first eight of their kind, so their distances — from 0.023 to 0.21 — are a sample of what a rank-two fit loses on a random rank-three tensor rather than a description of it. The distance is cheap to compute without any fitting, so the distribution can be had directly.

Drawing Gaussian tensors until four hundred have a complex pair takes 1,828 of them, a share of 21.9 per cent against the $1 - \pi/4 = 21.5$ the earlier essay measured. Their distances to the rank-two set run from $10^{-4}$ to 0.33 of the tensor’s norm, with a median of 0.061: a rank-two fit to a typical rank-three tensor leaves six per cent of it, one in ten leaves more than seventeen, and one in ten less than one. None of that is noise in the fit; it is the distance from the tensor to the nearest thing the fit can produce, and the fit gets to within a per cent of it.

The pencil’s eigenvalues give a reading of the distance before anything is computed, and it is a poor one. A complex pair that sits close to the real axis — a small imaginary part relative to its distance from the origin of the projective line — is closer to becoming a real double eigenvalue, and the median distance does rise with that tilt: 0.005 among the fourteen draws whose tilt is below a tenth, 0.087 among the 259 whose tilt is above 0.4. But the rank correlation between the two is only 0.51, and the scatter in the figure spans two decades of distance at every tilt. How far a tensor is from the rank-two set depends on the whole pencil and not only on where its eigenvalues are; the eigenvalues carry about half of the ordering, and what carries the rest is not measured here.

That bears on the earlier essay’s count. It found the rank-n share falling like a Gaussian in n, so that at n = 8 almost every tensor has rank n + 1. What the count did not say is how much rank n + 1 is the higher rank. If most rank-three tensors were within $10^{-4}$ of the rank-two set, the lower rank would be typical for every practical purpose and the count a technicality; at n = 2 the median distance is six per cent, which is a property any application fitting a rank-two model would see.

Approached and never reached #

The surface’s nearest point has a pencil with a double eigenvalue, and the fit can only reach it in the limit. Two rank-one terms with the same eigenvalue are, together, a rank-two tensor whose pencil has a double eigenvalue with two independent eigenvectors; the nearest point generically has one, a Jordan block, and a Jordan block is not a sum of two rank-one terms. It is the limit of two terms whose eigenvalues approach each other while their sizes grow to cancel the difference.

That is what the fit is doing. Its pencil’s two eigenvalues are real at every sweep, as they must be, and they close on each other: on the first draw they are 0.155 apart at sweep 30, 0.048 at sweep 1,000 and 0.0175 at sweep 8,000. The product of that gap and the largest term’s size stays between 1.17 and 1.19 along the whole run, and within a factor of 2.2 on every one of the four draws drawn: the eigenvalues close at exactly the rate the terms grow. A nearest point that is not there built this kind of limit by hand for the tensor at distance zero — two terms that grow as one over a vanishing parameter and cancel — and the fit finds the same construction on its own, at a positive distance, from a random start.

An inverse square, not an exchange rate #

The two cases of a missing nearest point now differ in a number that can be measured. On the border-rank tensor the error itself goes to zero, and it goes as one over the size of the terms: the repair that costs exactly itself measured that exchange rate and the price of a ridge that refuses to pay it. On a random rank-three tensor the error goes to a positive distance, and what goes to zero is the excess over it. The figure plots that excess against the term size, and every draw falls along a slope of minus two. The product of the excess and the square of the size is 0.18 to 0.50 across the four draws at 8,000 sweeps and moves by under a factor of two over the run, while the product with the size alone falls more than fivefold.

So the exchange rate is worse here by a square. On the border-rank tensor a tenfold larger term buys a tenfold smaller error. Here a tenfold larger term buys a hundredfold smaller excess — which sounds better until it is set against what the excess is an excess over. It is the last digits of an error that is already settled in its first three, and the price of each further digit is a factor of $\sqrt{10}$ in the size of the terms, paid in cancellation.

Every draw diverges, at its own rate #

At n = 2 the terms grow at exponents between 0.39 and 0.49 of the sweep count on all eight draws, close to the square root the inverse-square law implies if the excess falls like one over the sweeps. At n = 3 and 4 the exponents spread, from 0.32 to 1.14: some fits grow faster than the square root and one barely faster than the cube root. Larger pencils have more eigenvalues, and a complex pair can be pushed onto the real axis next to either of its real neighbours or both, so the path to the boundary is not unique in its shape even when the distance is. But on every one of the twenty-four complex draws the exponent is above 0.3, and on every real draw that converged it is zero.

What a code should do with this #

A settled error is not a found answer. Every stopping rule a fitting code applies watches the error, and on these tensors the error settles to five digits within a few hundred sweeps. A code that stops there returns terms that are already several times the tensor’s own norm and cancelling, and the next run, from another start, returns different large terms with the same error. A still error is not a settled one found stopping rules fooled by plateaus on the way to an answer; here the error is not on a plateau, it is at its limit, and what is unsettled is everything else.

The pencil says which case a tensor is in, for nothing. An n × n × 2 tensor’s rank question is an eigenvalue question about an n × n matrix. Before fitting at rank n, the eigenvalues of $A^{-1}B$ say whether a rank-n decomposition exists; if they include a complex pair, the best a rank-n fit can do is the distance to the boundary, and its terms will diverge whatever it is started from. At n = 4 that is three random tensors in four.

And the distance is a better number to report than the fit. For a 2 × 2 × 2 tensor it is the distance to the discriminant’s zero set, computed directly, and the fit’s error agrees with it to within one and a half per cent after 8,000 sweeps and is never below it. A quantity that the fit approaches from above, and that can be computed without the fit, is a certificate for how good the fit can get.

What three sizes do not show #

Three pencil sizes and a few dozen draws, all with standard Gaussian entries. The boundary distance is computed only at n = 2, where the surface is one polynomial; at n = 3 and 4 the surface is the set of pencils with any double eigenvalue, and the claim that the fits approach its distance is the n = 2 measurement carried over by the argument, not measured. The fits are plain alternating least squares with a tiny ridge, run for 8,000 sweeps; a regularised or line-searched fit would trade some of the divergence for some of the error, which the repair that costs exactly itself priced on the border-rank tensor and which is not priced here. And the n × n × 2 shape is the one whose rank question reduces to a pencil; for three slices or more the rank is not decided by one eigenvalue problem, and whether random tensors there also lack best approximations at their lower typical rank is a different question.

Still open: the distance at larger n, a fit that stops on purpose, and three slices #

The boundary at n = 3 and 4. The distance to the set of pencils with a double eigenvalue is a minimisation over pencils, and for n above two its constraint is the vanishing of a discriminant of degree $n(n-1)$. Computing it — by Newton on the eigenvalue-coincidence condition rather than on the polynomial — would say whether the fits’ common error at n = 3 is that distance to the same precision as at n = 2, and whether the n = 4 draw whose two starts disagree by six per cent is one where the two starts are heading for two different nearest points.

A fit that stops at the distance. If the distance can be computed, a fit can be stopped when its error is within a stated fraction of it, before its terms have grown. The prediction with a sign is that at a tolerance of one per cent the terms are still within a factor of three of the tensor’s norm on every draw at n = 2, because the excess falls as the square of the size and one per cent is reached early.

Three slices. An n × n × 3 tensor’s typical real ranks are not decided by one pencil. Whether its lower typical rank also has random tensors with no best approximation — and whether a fit there settles at a distance and diverges in its terms in the same way — is the question that would say whether this page describes pencils or real tensors.