Border-rank — where it appears
Named by 12 essays across 2 fields — each of them below, with the objects they name alongside it.
A nearest point that is not there
Eckart and Young guarantee that a matrix has a best rank-k approximation and that the truncated SVD is it. For three indices the guarantee is false in the strongest available way — there are tensors whose distance to the rank-two set is zero and which no rank-two tensor equals.
A rank that is not a property of the tensor
The same eight real numbers have rank three over the reals and rank two over the complexes, and a random 2 × 2 × 2 tensor has rank two with probability exactly π/4. Neither sentence has an analogue for matrices, where the rank is one number and a random matrix has the largest one.
An iteration that walks out of the set
Every sweep of alternating least squares is the exact minimiser of its own subproblem, so the objective can only fall. What it cannot do is converge, when the target's nearest rank-r point is not in the rank-r set — and a plateau at a small residual looks identical to slow convergence unless the size of the terms is plotted beside it.
A tensor that cannot be decomposed
Every member of a certain sequence is exactly a sum of two rank-one terms, and both terms are written down in closed form. A three-hundred-sweep fit from a random start does not find them, and stalls at the same one per cent however far the sequence goes — while a fit started at the answer loses digits exactly as 2n² says it should.
One term too many
A tensor built from three rank-one terms, fitted with four, reaches a relative error of 1.0·10⁻¹³ in seventy-six sweeps. Two of the four terms come back with a cosine of 0.99927 between them, subtracting each other, and the smallest weight is a fifth of the largest rather than a rounding. Nothing in the residual says any of it.
The repair that costs exactly itself
A ridge on every subproblem is the standard cure for a swamp and it works — the terms stop at 1.61 instead of climbing past 6.7, and a run that never finished finishes in 798 sweeps. On a tensor that does have an answer the error it costs is the ridge itself, to within a factor of two, at every setting from 10⁻¹⁰ to 10⁻¹. And the terms it returns are still the right terms.
The test that is a deadline
The quantity that separates a boundary from slow convergence fires on every run that has nothing to reach, at sweep 21 of four thousand, and on no ordinary fit. It also fires on every badly conditioned fit that does converge — at sweep 758. No threshold between 0.10 and 0.40 separates those two, and the sweep it fires at separates them by a factor of thirty-six.
The rank a sweep can vouch for
To decide a tensor's rank, fit it at one rank after another and stop where something changes. Three things can be read off each rank's fits — the error, how nearly parallel the terms are, and whether fits from different starting points agree — and over six planted rank-three tensors at four noise levels they decide it 24, 12 and 15 times out of 24; the ratio of consecutive errors, which needs nothing, decides it 24 times. The error is right every time and has to be told the noise level. The collinearity is a coin toss. Agreement among starts is never wrong and, under noise, cannot decide on nine of the twenty-four — and the rank past the answer, where every decision is made, costs ten times the answer.
A fit that has an answer and cannot stop
Fit a noisy rank-three tensor with four terms and the prediction was that the spare term would find real structure in the noise and stop pairing off with the others. It does not: the largest cosine between two fitted terms has a median of 0.977 at 1% noise against 0.975 without noise. What changes is the solver. Without noise the four-term fit stops in fifty sweeps; with noise it never stops: its error keeps moving by a part in a million a sweep for six thousand sweeps, while on most tensors its terms stand still. The extra term takes exactly its share of the noise, and the error is settled by sweep 150.
The rank that stops being typical
A random 2 × 2 × 2 tensor has rank two with probability π/4 and rank three otherwise, and the sentence has no analogue for matrices. It is the first of a family. An n × n × 2 tensor is a pencil of two slices, and it has rank n exactly when the pencil's eigenvalues are all real, n + 1 otherwise. Over draws, the share of rank n is 0.786 at n = 2, 0.500 at 3, 0.264 at 4, 0.039 at 6, 0.004 at 8 and none of 4,000 at 10 — falling like e^(−0.087n²) — because the mean number of real eigenvalues grows only like the square root of n, to Edelman, Kostlan and Shub's closed form within two per cent. Both ranks stay typical in theory; in practice the lower one disappears.
A fit with no answer to find
Half of all random 3 × 3 × 2 tensors, and most larger ones, have no rank-three decomposition, because their pencil has a complex pair. A rank-n fit to one of them does not wander and does not stall. Two starts settle at the same error to five digits, and that error is the distance from the tensor to the surface where its pencil has a double eigenvalue — found with no fitting at all, and matched to within one and a half per cent. Meanwhile the fit's terms grow without limit, like the square root of the sweep count, while the fitted pencil's two closest eigenvalues close on each other at exactly the rate the terms grow. The error has an answer; the decomposition does not.
A stop that knows the distance
A rank-two fit to a random 2 × 2 × 2 tensor of rank three settles at the tensor's distance to the boundary of the rank-two set while its terms grow without limit, and the distance can be computed without fitting. So a fit can be stopped when its error is within a stated fraction of it, and the prediction was that at one per cent the terms would still be within three times the tensor's norm, because one per cent is reached early. On 23 random tensors the terms at the one-per-cent stop are 3.8 to 12.9 times the norm — none within three — and the reason is the law the earlier essay found: the excess falls as the inverse square of the term size, so the size at the stop is the square root of a constant over τ times the distance, and a tensor close to the boundary pays twice, in larger terms and in sweeps. The two closest tensors never reach one per cent in 20,000 sweeps. The stall test a code would use stops in the same range by accident. And one of the 24 computed distances was wrong, which the fit itself exposed.
Named alongside it
The objects these essays reach for when they reach for this one.
CP decompositionTensor rankAlternating least-squaresIll-posed problemSwampDegeneracyCondition squaringStopping criterionLow-rank approximationMatrix pencilUniquenessEckart–Young