Numerical Linear Algebra
where the algebra stops being the arithmetic
When the index is a tuple

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.
32 min read 26 figures Where the algebra stops being the arithmeticMeasured, not assertedAssertions that reject

Worth reading first: An index that is a pair · A bound that holds with probability.

Half of this collection rests on one theorem. Eckart and Young: the best rank-k approximation of a matrix in the Frobenius or spectral norm is its truncated singular value decomposition, the error is the next singular value, and — the part nobody states, because for matrices it needs no stating — the best one exists.

For an array with three or more indices it is false. Not approximately false, not false in a corner case: there are tensors whose distance to the set of rank-two tensors is exactly zero and which no rank-two tensor equals.

A rank-two sequence approaching a rank-three tensor: the residual falls like 1/n and the terms grow like nA_n = n(e₁ + e₂/n)⊗³ − n·e₁⊗³ has rank two for every n and converges to a tensor of rank three. The falling curve is ‖A_n − A‖, which is √(3/n² + 1/n⁴) exactly and reaches 0.00169 at n = 1024; the rising one is the norm of the larger of its two rank-one terms, 1024. Their product runs 2.519, 1.917, 1.777 … 1.73205, descending onto √3 = 1.73205. So getting one digit closer costs a factor of ten in the size of the pieces, for ever, and the infimum of the distance is zero while no rank-two tensor attains it.110¹10²10³10⁻³10⁻²10⁻¹110¹10²10³n‖A_n − A‖ and the largest term's norm‖A_n − A‖the larger of its two termsan infimum that is not attainedn1024‖A_n − A‖0.0017largest term1024their product1.7√31.7the distance goes to zeroand nothing reaches it
Fig. 1 A sequence of rank-two tensors converging to a tensor of rank three. The falling curve is the distance and the rising one is the size of the pieces being subtracted; neither turns.

The example, which is eight numbers

With e₁ = (1, 0) and e₂ = (0, 1) in two dimensions, let

A = e₁⊗e₁⊗e₂ + e₁⊗e₂⊗e₁ + e₂⊗e₁⊗e₁

which is a 2 × 2 × 2 array with three entries equal to one and five equal to zero. Its rank is three: three rank-one terms are written above, and no two suffice.

Now consider, for each n,

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

which is a difference of two rank-one terms and therefore has rank at most two for every n. Expanding the cube,

A_n = A + (1/n)·(the three terms with two e₂’s) + (1/n²)·e₂⊗e₂⊗e₂

so ‖A_n − A‖ = √(3/n² + 1/n⁴), which goes to zero.

The infimum of the distance from A to the rank-two set is therefore zero, and A has rank three, so nothing in the set attains it. The set of tensors of rank at most two is not closed.

What that costs, in numbers

The hero figure plots both quantities. The residual falls like √3/n and the larger of the two rank-one terms grows like n·(1 + 1/n²)^{3/2}, so their product is

√(3 + 1/n²) · (1 + 1/n²)^{3/2}

which descends onto √3 from above: 1.7774 at n = 8, 1.73205 at n = 2048, a fall of 2.6 per cent across two and a half decades. That expression is what the assertion checks, rather than a constant, because the algebra hands over a formula and asserting “constant” where a formula exists is describing the picture instead of testing it.

The practical reading of a constant product is severe. Getting one digit closer to A costs a factor of ten in the size of the pieces being subtracted from one another, for ever. At n = 10¹⁶ the two terms are 10¹⁶ and the answer is their difference — which is the arithmetic this collection’s first field is about, and where the cancellation takes the whole answer.

Relative error of two algebraically identical expressions for (1 − cos x)/x², in binary64A log–log plot of relative error against x. The expression written as it reads loses accuracy as x falls and is eventually wrong in every digit; the rearranged form stays at rounding level.10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹xrelative error of the computed value(1 − cos x)/x², as written2 sin²(x/2)/x²no digits left at allbinary64 throughoutone function, two spellings · zero below 1.5·10⁻⁸
Fig. 2 What the last stage of that sequence runs into, from the arithmetic field: two large numbers whose difference is small, and the digits that are not there afterwards.
A rank-two sequence approaching a rank-three tensor: the residual falls like 1/n and the terms grow like nA_n = n(e₁ + e₂/n)⊗³ − n·e₁⊗³ has rank two for every n and converges to a tensor of rank three. The falling curve is ‖A_n − A‖, which is √(3/n² + 1/n⁴) exactly and reaches 2.64·10⁻⁵ at n = 65536; the rising one is the norm of the larger of its two rank-one terms, 65540. Their product runs 2.519, 1.917, 1.777 … 1.73205, descending onto √3 = 1.73205. So getting one digit closer costs a factor of ten in the size of the pieces, for ever, and the infimum of the distance is zero while no rank-two tensor attains it.110¹10²10³10⁴10⁻⁴10⁻³10⁻²10⁻¹110¹10²10³10⁴10⁵n‖A_n − A‖ and the largest term's norm‖A_n − A‖the larger of its two termsan infimum that is not attainedn6.6·10⁴‖A_n − A‖2.6·10⁻⁵largest term6.6·10⁴their product1.7√31.7the distance goes to zeroand nothing reaches it
Fig. 3 The same picture extended to n = 65,536. Nothing turns, which is the whole content: the figure at the far end is the figure at the near end with both axes lengthened.

The word that is missing, and the one that replaces it

What A has and A_n does not is a rank; what A_n has and A does not is membership of a set. The quantity that reconciles them has a name.

The border rank of a tensor is the least r such that it is a limit of tensors of rank at most r. For a matrix, border rank and rank are the same number — that is what closedness means. For A they are two and three, and the gap between them is the whole subject of this page.

Border rank is the more useful of the two for anything an algorithm does, because it is what a truncation can approach. Rank is the more useful for anything a decomposition claims, because it is what a decomposition returns. A field that could only quote one of them would be describing either the algorithms or the objects, and this collection’s habit of putting a computed number beside a claimed one requires both.

There is a third quantity, and it is the one every practical code actually uses. A numerical rank at a tolerance ε is the least r for which some rank-r tensor is within ε — which is a border rank in disguise, since the set being searched is the closure. So the object a code reports is not the rank of the tensor and is not a mistake; it is a different quantity, and this collection has an essay about the matrix version of exactly that confusion.

Singular values of a rank-4 matrix with noise of relative size 10⁻⁸Ten singular values on a logarithmic axis. The first four sit near one; the rest sit at the noise level, and the vertical distance between the two groups is the evidence for the rank.1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision
Fig. 4 The matrix version, from the spectra field: a rank that is a decision about a gap, reported at a tolerance, and not a property the matrix has on its own.

The rank of a 2 × 2 × 2 tensor is a sign

The example above is not an isolated construction. For arrays of this smallest interesting shape the rank is decided exactly, by a polynomial in the eight entries, with no iteration anywhere.

Take the two 2 × 2 slices A₀ and A₁ and form det(A₀ + λA₁), which is a quadratic c₀ + c₁λ + c₂λ². Its discriminant

Δ = c₁² − 4c₀c₂

is Cayley’s hyperdeterminant, and it decides the rank outright:

Δ real rank what the pencil is doing
Δ > 0 2 two distinct real roots, two real rank-one terms
Δ < 0 3 a conjugate pair — the next essay is about this row
Δ = 0 3 a repeated root, and the infimum is zero

The example has A₀ = [[0, 1], [1, 0]] and A₁ = [[1, 0], [0, 0]], so det(A₀ + λA₁) = −1 identically: c₀, c₁ and c₂ are −1, 0 and 0, and Δ = 0. Its three unfoldings all have rank two, which is what separates the rank-three case from the rank-one one.

A plane of 2 × 2 × 2 tensors, coloured by the sign of the hyperdeterminant that decides their rankTwo of the eight entries are varied over ±2 and the other six are held at the values that make the centre of the picture the rank-three tensor A = e₁⊗e₁⊗e₂ + e₁⊗e₂⊗e₁ + e₂⊗e₁⊗e₁. The light region is Δ > 0, where the tensor has real rank two and two real rank-one terms exist; the dark region is Δ < 0, where the real rank is three and the complex rank is two. 54.2 per cent of this window is rank two. The boundary between them is the curve Δ = 0, on which the rank is three and the distance to the rank-two set is zero — every point of it is a tensor with no nearest rank-two approximation.rank three, Δ = 0a₁₁₁ across, a₀₀₀ up, both over ±2light: two real roots, rank two · dark: a conjugate pair, rank threeone sign, two rankscells sampled4096rank two2222rank three1874Δ at the centre0rank at the centre3the rank is a signcomputed from eight numbers
Fig. 5 A plane of 2 × 2 × 2 tensors coloured by the sign. The light region is rank two and the dark one is rank three; the boundary between them is where the infimum is zero and is not attained.
A plane of 2 × 2 × 2 tensors, coloured by the sign of the hyperdeterminant that decides their rankTwo of the eight entries are varied over ±0.5 and the other six are held at the values that make the centre of the picture the rank-three tensor A = e₁⊗e₁⊗e₂ + e₁⊗e₂⊗e₁ + e₂⊗e₁⊗e₁. The light region is Δ > 0, where the tensor has real rank two and two real rank-one terms exist; the dark region is Δ < 0, where the real rank is three and the complex rank is two. 50.0 per cent of this window is rank two. The boundary between them is the curve Δ = 0, on which the rank is three and the distance to the rank-two set is zero — every point of it is a tensor with no nearest rank-two approximation.rank three, Δ = 0a₁₁₁ across, a₀₀₀ up, both over ±0.5light: two real roots, rank two · dark: a conjugate pair, rank threeone sign, two rankscells sampled4096rank two2048rank three2048Δ at the centre0rank at the centre3the rank is a signcomputed from eight numbers
Fig. 6 The same window at four times the magnification. The boundary does not resolve into anything — the rank-three curve passes through the centre at every scale, which is what makes the rank-two set non-closed rather than merely awkward.
The share of random 2 × 2 × 2 tensors with real rank two, against the number drawn, and π/4Each draw is eight independent standard normal entries and its rank is decided exactly, by the sign of the hyperdeterminant, with no iteration involved. Over 1,995 draws 1,589 have rank two — a share of 0.7965 against the exact value π/4 = 0.7854, inside 1.2 standard errors. The band is ±2 of them. A random matrix has one typical rank; this is the picture of a random object having two, each with a probability that is a number rather than an experiment.10¹10²10³00.050.10.150.20.250.30.350.40.450.50.550.60.650.70.750.80.850.90.951drawsshare with real rank twoπ/4 = 0.7853981,589 of 1,995 have rank twoa probability with a closed formdraws1995rank two1589share0.8π/40.79standard errors out1.2two typical ranksand the split is π/4
Fig. 7 And how much of the plane each region is worth, over a thousand draws rather than a window: the two signs occur with probabilities that are numbers rather than experiments.

Why the matrix case has no analogue of this

It is worth being precise about what the matrix case has that this does not, because the difference is not that matrices are simpler.

The set of matrices of rank at most k is closed: it is the zero set of all (k+1) × (k+1) minors, which is a system of polynomial equations, and the zero set of polynomials is closed by definition.

The set of tensors of rank at most r is not a zero set of anything. It is the image of a polynomial map — take r triples of vectors, form the sum of their outer products — and the image of a polynomial map need not be closed. Its closure is a variety, and the difference between the image and its closure is exactly the tensors whose border rank is r and whose rank is more.

So the failure is not a defect in the definition of tensor rank; it is the ordinary behaviour of images of maps, and the matrix case is the accident. What makes the matrix case work is that rank-≤k matrices happen to be describable by equations as well as by a parametrisation, and nothing hands that over for three indices.

Singular values of a rank-4 matrix with noise of relative size 10⁻⁸Ten singular values on a logarithmic axis. The first four sit near one; the rest sit at the noise level, and the vertical distance between the two groups is the evidence for the rank.1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision
Fig. 8 What rank means for a matrix on this site, from the essay that settled it: a decision about a gap in a spectrum, on a set that at least contains its own limit points.
Error of the best rank-k approximation to a 12×12 matrixApproximation error against k on a logarithmic axis, with the measured error and the next singular value drawn as separate curves lying exactly on top of one another.123456789101110⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1rank k of the approximation‖A − Aₖ‖measured, 2-normσₖ₊₁, from theorymeasured, Frobeniusthe first two agreeto 2·10⁻⁸worst |‖A−Aₖ‖₂ − σₖ₊₁| / σₖ₊₁2·10⁻⁸worst Frobenius discrepancy2·10⁻⁸κ = 10⁹; 30 random rank-3 matrices, none closerthe error is σₖ₊₁
Fig. 9 And the theorem this page is about the failure of: the truncated decomposition’s error, which is the next singular value and is attained.

One more difference is worth naming because it is the one that bites in practice. For matrices, the rank-≤k set is irreducible and its dimension is known: k(m + n − k). For tensors, the set of rank-≤r tensors can have several components of different dimensions over the reals, which is what the next essay’s two typical ranks are a symptom of. So even the question how many parameters does a rank-r tensor have does not have one answer.

How far the coefficients can move without changing the fit, degree 11Relative increase in the residual against relative change in the coefficients, along the least determined direction. The residual does not move measurably until the coefficients have changed by more than a factor of one.10⁻⁴10⁻³10⁻²10⁻¹110¹10²10³10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹relative change in the coefficients, along the worst directionrelative increase in the residualcoefficients doubled1544% change, fit unmoved in the sixth digit308×: the third digit movesκ(A) = 1.4·10⁸. Exact arithmetic would pick one point on this floor. It would not raise it.24 points, degree 11, monomial basisthe data leaves them free
Fig. 10 The least-squares field’s picture of a parametrisation with directions that cost nothing, for comparison: a valley whose floor is flat, on a problem whose set at least has a dimension.

What it does to an algorithm

An optimisation over a set that does not contain its own limit points has a specific and recognisable failure, and it is not divergence.

The objective decreases, monotonically, for as long as anyone is prepared to wait. The parameters — here the rank-one terms — grow without bound. The two are in exact proportion, so the iterate keeps improving and the representation keeps degenerating, and neither an objective plot nor a residual test can tell that from slow convergence.

This collection has a name for that shape from its own hierarchy field: a quantity going to zero is one arithmetic event with two opposite meanings. Here it is a quantity going to zero that means the answer is being left behind rather than approached.

The field’s essay on alternating least squares measures it. What is worth carrying from here is that the phenomenon is geometric and not numerical: it is not a rounding effect, it does not go away in higher precision, and it is not a bad starting point. It is the set.

Alternating least squares on a tensor with a rank-two answer and on one without, over 20,000 sweepsThe steeply falling curve is a rank-three fit to a tensor built from rank-three factors: it reaches 9.74·10⁻¹⁵ in 58 sweeps and its largest term does not move — 12.202 at sweep twenty and 12.202 at the end. The other is a rank-two fit to the border-rank tensor, whose error goes from 0.00677 to 0.00141 and has not finished, while the rising curve is its largest term: 4.698 to 10.15, a factor of 2.16. Fitted over 199 points, the error falls as the 2.03 power of the term size — a better path than the explicit sequence's 1/n, and still one that leaves the set rather than converging inside it.110¹10²10³10⁴10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹sweeprelative error, and the largest term's sizerising: the swamp's largest rank-one termfalling, slowly: its errorfalling, once: a fit with an answera plateau with a rising floorswamp error0.0014swamp term10term growth2.2benign error9.7·10⁻¹⁵benign term growth1the error alone cannot tellthe size of the terms can
Fig. 11 The shape it takes in an iteration, from the essay that measures it: twenty thousand sweeps, an error that keeps falling and terms that keep growing.

And what it does to a bound

The other consequence is that a whole class of statement stops being available.

For matrices, every low-rank approximation on this site is priced against the best one: the hierarchy field’s blocks are compared with bestError, the randomised field’s sketches are compared with the truncated decomposition, and the word quasi-optimal means within a factor of the best. All of that needs the best to exist.

For tensor rank it does not, so the phrase has nothing to attach to. What replaces it is a different notion of rank — the multilinear rank, and the train ranks, which are ranks of ordinary matrices — for which the best does exist and the projection onto it is computable. Two essays on, that is exactly the repair: carry the algorithm across rather than the definition.

The truncation error of a smooth tensor against the rank kept, between the two bounds the theorem givesThe middle curve is the measured error of the projection; the upper dashed one is √(Σ_k tail_k²), which the theorem says it cannot exceed, and the lower one is max_k tail_k, which the best possible error cannot fall below. They are a factor of √3 apart. The measurement is that the projection sits on the upper one, and not between them: the ratio of error to bound runs 0.688, 0.717, 0.879, 0.933 … 0.999982, so by rank 10 the bound is attained to five decimals and the ratio to the lower bound is 1.7320 against √3 = 1.7321. That reads as a bad result and is not one — what it says is that the lower bound is weak, which only a second measurement can establish.024681010⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹rank kept in every moderelative errordashes above: √(Σ tail²), the upper bounddashes below: max tail, a floor under the bestsolid: what the projection returnssmooth: pinned to the upper boundrank 10 error1.1·10⁻¹¹its upper bound1.1·10⁻¹¹the lower bound6.3·10⁻¹²error ⁄ bound1error ⁄ lower1.7inside the boundand sitting on it
Fig. 12 Where the repair lands: a truncation with a computable bound either side of it, and both bounds made of singular values of matrices.
How many columns a decade of accuracy costs, measured and predicted, at q = 0.500The number of singular values above ε, against the number of digits ε asks for, on a 128 × 128 block between two intervals separated by a gap of 1. The measured curve is a straight line at 0.55 columns a decade: a digit costs the same handful of columns wherever you buy it, which is why the accuracy is a knob and not a cliff. The upper line is what the geometry alone promises — q^(p+1)/(1 − q) below ε, solved for p, using four numbers and no entry of the matrix — at 3.32 columns a decade. Both are straight and they are not the same straight: the bound is right about the shape and loose by 5.3× about the constant, which is the safe direction for a quantity you have to allocate storage from.0369121501122334455digits asked for, −log₁₀ εcolumns keptwhat the geometry promiseswhat the matrix costsa rank is a number of digitscolumns a decade0.55bound, a decade3.3rank at 10⁻⁸5bound at 10⁻⁸28q0.5the shape is rightand the constant is not
Fig. 13 And the hierarchy field’s version of a bound that is available, for comparison — a rank against an accuracy, where every quantity in sight is a matrix’s.

What survives

It is worth stating plainly what is not damaged, because the list is longer than the damage.

The Frobenius norm is still a norm and distances still mean what they mean. The unfoldings are still matrices and their singular values are still computable, exactly and cheaply. Every statement in the previous two essays about Kronecker structure is untouched, because a Kronecker sum is a matrix. And the tensor’s own entries are as available as they ever were.

What is damaged is one specific inference: there is a best approximation of this shape, therefore what an algorithm returns can be compared against it. That inference is used, unstated, in every low-rank argument this collection makes, and the rest of the field is about the two ways of restoring it — change the notion of rank until the set is closed, which is what the Tucker and train formats do, or accept the non-closedness and measure what an iteration does inside it, which is what the alternating-least-squares essay does.

Train ranks at each of the 4 cuts of a 5-index tensor on 6 points a side, four familiesCut the index list after position k, put the first k indices on the rows and the rest on the columns, and take the rank of the matrix that results. There are 4 such cuts and each rank is an ordinary matrix rank. sin(x₁ + … + x_d) has rank exactly two at every one of them, for every d, because the addition formula separates it into two terms at every cut — a rank written down rather than measured, and the computed values are 2, 2, 2, 2. The reciprocal family climbs to 9, the product family is one everywhere, and independent normal entries reach 36, which is the largest rank the cut allows. Storage runs sinsum 96, reciprocal 1,206, product 30, noise 10,440 against 7,776 entries.012345061218243036cut after index krank of the reshapesinsum · 2 2 2 2reciprocal · 6 9 9 6product · 1 1 1 1noise · 6 36 36 64 cuts, 4 rankssinsum stored96reciprocal stored1206product stored30noise stored10⁴entries7776one rank per cutand one of them is a theorem
Fig. 14 The first repair, from three essays on: ranks of ordinary matrices, one per place the index list can be cut, every one of them a quantity with a best approximation behind it.

What it means for a claim about data

One more consequence, and it is the one that reaches outside numerical linear algebra.

A CP decomposition is used because its factors are interpretable: the columns are supposed to be the components a measurement is a mixture of, and the whole reason for preferring it to a matrix factorisation is that they are recoverable rather than arbitrary. The last essay of this field measures that and finds it true.

What this page adds is the condition under which the sentence is meaningful at all. If the best rank-r approximation of the data does not exist, then the components a rank-r model would recover is not a well-formed phrase — there is no rank-r model that is nearest, so there is nothing for the recovered factors to be an estimate of. A fit that has entered a swamp is returning terms of size 10⁶ that cancel to within 10⁻³, and reading those terms as components is reading an artefact of where the iteration stopped.

The diagnostic is on the hero figure and costs nothing: report the size of the terms beside the residual. A model whose terms are the size of its data is a model; a model whose terms are a thousand times its data is a subtraction.

Alternating least squares on a tensor with a rank-two answer and on one without, over 5,000 sweepsThe steeply falling curve is a rank-three fit to a tensor built from rank-three factors: it reaches 9.74·10⁻¹⁵ in 58 sweeps and its largest term does not move — 12.202 at sweep twenty and 12.202 at the end. The other is a rank-two fit to the border-rank tensor, whose error goes from 0.00677 to 0.00266 and has not finished, while the rising curve is its largest term: 4.698 to 7.42, a factor of 1.58. Fitted over 197 points, the error falls as the 2.04 power of the term size — a better path than the explicit sequence's 1/n, and still one that leaves the set rather than converging inside it.110¹10²10³10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹sweeprelative error, and the largest term's sizerising: the swamp's largest rank-one termfalling, slowly: its errorfalling, once: a fit with an answera plateau with a rising floorswamp error0.0027swamp term7.4term growth1.6benign error9.7·10⁻¹⁵benign term growth1the error alone cannot tellthe size of the terms can
Fig. 15 The diagnostic at a shorter run, where the two readings are still hardest to tell apart and the term size is already the thing that separates them.
How much two runs of the same fit agree about the factors, from 6 starting points eachEvery run here reaches its target to the rounding level — 3·10⁻¹³, 1.16·10⁻¹¹ and 2.39·10⁻¹⁵ at worst — so all three are successful factorisations. The bar is the worst agreement between any two of them about the *factors*, matched over permutations and scalings, which is exactly the freedom the uniqueness theorem allows. Kruskal's condition k_A + k_B + k_C ≥ 2r + 2 holds for the first (9 ≥ 8) and fails for the second (6 < 8), and the bars are 1.0000 and 0.0207. The matrix is the comparison the whole thing rests on: AB = (AM)(M⁻¹B) for every invertible M, so its runs agree to 0.1089 and its factors mean nothing on their own.6 × 6 × 6, rank 3 · 9 ≥ 81.00002 × 2 × 2, rank 3 · 6 < 80.02076 × 6 matrix, rank 3 · no condition0.1089worst agreement between two runs about the factors, 0 to 1every run fits to 3·10⁻¹³every run fits to 1.2·10⁻¹¹every run factorises to 2.4·10⁻¹⁵ and none agrees with anotherthe only thing that improvestensor, Kruskal holds1tensor, Kruskal fails0.021matrix0.11worst residual1.2·10⁻¹¹three successful fitsone recoverable answer
Fig. 16 And what the factors are worth when the fit is well posed, from the field’s last essay: the one property a tensor has and a matrix does not.

The refusal

The claim under test is the assumption every low-rank argument on this site has made without stating it, and the refusal has to be the other direction: not that the phenomenon exists, but that it does not happen everywhere.

If the classification reported rank three for every 2 × 2 × 2 tensor, the whole page would be a bug. So it is fed an ordinary rank-two tensor — a sum of two rank-one terms with disjoint supports, which is as far from the boundary as this shape allows — and required to refuse the claim that it has rank three.

That matters more than it looks. A phenomenon that applied to every tensor would be a statement about the definition rather than about the geometry, and the measured fact that the light region of the plane figure occupies most of the window is what makes the dark boundary a boundary.

The second refusal in the same file is aimed at the reading that most nearly works. The unfoldings of a tensor are matrices and their ranks are ordinary ranks, so it is tempting to take the largest of them as the tensor’s rank. It is fed the Δ < 0 tensor, whose unfoldings are all rank two and whose real rank is three, and required to fail.

At other settings

A rank-two sequence approaching a rank-three tensor: the residual falls like 1/n and the terms grow like nA_n = n(e₁ + e₂/n)⊗³ − n·e₁⊗³ has rank two for every n and converges to a tensor of rank three. The falling curve is ‖A_n − A‖, which is √(3/n² + 1/n⁴) exactly and reaches 0.108 at n = 16; the rising one is the norm of the larger of its two rank-one terms, 16.09. Their product runs 2.519, 1.917, 1.777 … 1.74334, descending onto √3 = 1.73205. So getting one digit closer costs a factor of ten in the size of the pieces, for ever, and the infimum of the distance is zero while no rank-two tensor attains it.110¹10⁻¹110¹n‖A_n − A‖ and the largest term's norm‖A_n − A‖the larger of its two termsan infimum that is not attainedn16‖A_n − A‖0.11largest term16their product1.7√31.7the distance goes to zeroand nothing reaches it
Fig. 17 The first four terms of the sequence, at the scale where the two curves are still close together.
A rank-two sequence approaching a rank-three tensor: the residual falls like 1/n and the terms grow like nA_n = n(e₁ + e₂/n)⊗³ − n·e₁⊗³ has rank two for every n and converges to a tensor of rank three. The falling curve is ‖A_n − A‖, which is √(3/n² + 1/n⁴) exactly and reaches 4.23·10⁻⁴ at n = 4096; the rising one is the norm of the larger of its two rank-one terms, 4096. Their product runs 2.519, 1.917, 1.777 … 1.73205, descending onto √3 = 1.73205. So getting one digit closer costs a factor of ten in the size of the pieces, for ever, and the infimum of the distance is zero while no rank-two tensor attains it.110¹10²10³10⁻³10⁻²10⁻¹110¹10²10³10⁴n‖A_n − A‖ and the largest term's norm‖A_n − A‖the larger of its two termsan infimum that is not attainedn4096‖A_n − A‖4.2·10⁻⁴largest term4096their product1.7√31.7the distance goes to zeroand nothing reaches it
Fig. 18 And a decade further, for reading against the hero.
A plane of 2 × 2 × 2 tensors, coloured by the sign of the hyperdeterminant that decides their rankTwo of the eight entries are varied over ±6 and the other six are held at the values that make the centre of the picture the rank-three tensor A = e₁⊗e₁⊗e₂ + e₁⊗e₂⊗e₁ + e₂⊗e₁⊗e₁. The light region is Δ > 0, where the tensor has real rank two and two real rank-one terms exist; the dark region is Δ < 0, where the real rank is three and the complex rank is two. 87.2 per cent of this window is rank two. The boundary between them is the curve Δ = 0, on which the rank is three and the distance to the rank-two set is zero — every point of it is a tensor with no nearest rank-two approximation.rank three, Δ = 0a₁₁₁ across, a₀₀₀ up, both over ±6light: two real roots, rank two · dark: a conjugate pair, rank threeone sign, two rankscells sampled4096rank two3572rank three524Δ at the centre0rank at the centre3the rank is a signcomputed from eight numbers
Fig. 19 The widest window the plane is drawn over, where the rank-three region is a thin wedge and the share of rank-two tensors is at its largest.
A plane of 2 × 2 × 2 tensors, coloured by the sign of the hyperdeterminant that decides their rankTwo of the eight entries are varied over ±1 and the other six are held at the values that make the centre of the picture the rank-three tensor A = e₁⊗e₁⊗e₂ + e₁⊗e₂⊗e₁ + e₂⊗e₁⊗e₁. The light region is Δ > 0, where the tensor has real rank two and two real rank-one terms exist; the dark region is Δ < 0, where the real rank is three and the complex rank is two. 50.0 per cent of this window is rank two. The boundary between them is the curve Δ = 0, on which the rank is three and the distance to the rank-two set is zero — every point of it is a tensor with no nearest rank-two approximation.rank three, Δ = 0a₁₁₁ across, a₀₀₀ up, both over ±1light: two real roots, rank two · dark: a conjugate pair, rank threeone sign, two rankscells sampled4096rank two2048rank three2048Δ at the centre0rank at the centre3the rank is a signcomputed from eight numbers
Fig. 20 And the intermediate magnification, where the boundary curve’s shape is clearest.
The share of random 2 × 2 × 2 tensors with real rank two, against the number drawn, and π/4Each draw is eight independent standard normal entries and its rank is decided exactly, by the sign of the hyperdeterminant, with no iteration involved. Over 19,953 draws 15,705 have rank two — a share of 0.7871 against the exact value π/4 = 0.7854, inside 0.6 standard errors. The band is ±2 of them. A random matrix has one typical rank; this is the picture of a random object having two, each with a probability that is a number rather than an experiment.10¹10²10³10⁴00.050.10.150.20.250.30.350.40.450.50.550.60.650.70.750.80.850.90.951drawsshare with real rank twoπ/4 = 0.78539815,705 of 19,953 have rank twoa probability with a closed formdraws2·10⁴rank two1.6·10⁴share0.79π/40.79standard errors out0.59two typical ranksand the split is π/4
Fig. 21 How often each rank actually happens, from the next essay: two typical ranks with positive probability, in a proportion with a closed form.
The three unfoldings of a 10 × 11 × 12 noise tensor, and the singular values of eachA tensor has one matrix per index — put that index on the rows and every other index down the columns — and each of those matrices has an ordinary rank. Here they are 10, 11, 12 at a relative tolerance of 10⁻⁸, from a tensor of 1320 entries whose modes are of different lengths. Nothing requires the three numbers to agree, and nothing requires any of them to be the tensor's own rank: they are three different matrices built from one array. The leading singular values are 14.2, 13.6, 13.4, each normalised to its own mode below.02468101210⁻¹⁶10⁻¹²10⁻⁸10⁻⁴1index of the singular valueσ ⁄ σ₁the tolerance the ranks are read atmode 1 · rank 10mode 2 · rank 11mode 3 · rank 12noise: three matrices, one arrayentries1320mode-1 rank10mode-2 rank11mode-3 rank12‖T‖36three ranksand none of them is the tensor's
Fig. 22 The three matrices a tensor comes with, on an array with no structure — none of which is its rank.
Along a sequence of exactly rank-two tensors: the step's condition number, and what a fit from a random start achievesEvery A_n on this sequence *is* a rank-two tensor and its two rank-one terms are written down, so nothing here is about existence. The rising curve is the condition number of the r × r system each alternating sweep solves, which on this sequence has a closed form in n whose asymptote is 2n² — the marks are measured and the dashed line is that closed form, agreeing to 4.5·10⁻¹³. The lower marks are what a three-hundred-sweep fit from a random start returns: 2.1·10⁻⁴ at n = 2 rising to 0.0118 at n = 128. Started at the answer instead, the same code stays within 1.4·10⁻¹⁰ of it at every n — not the rounding level, because the drift from an exact start is itself about κ times the unit roundoff, but nine orders below what a random start reaches. That is the control that says the failure is the conditioning and not the implementation. A tensor away from the boundary conditions its step at 6.03.110¹10²10⁻¹²10⁻⁸10⁻⁴110⁴ncondition number, and residual reachedmarks above: κ of the step · dashes: its closed formmiddle: a fit from a random startbelow: the same fit started at the answera decomposition that is ill-conditionedκ at n = 1283.3·10⁴its closed form3.3·10⁴cosine of the terms1from a random start0.012from the answer1.4·10⁻¹⁰the answer existsand cannot be found
Fig. 23 What the boundary does to the conditioning of a decomposition, from the error field’s essay on it: a condition number that is a square in the distance.
How far |r_nn| sits above σ_min on Kahan's matrix, against the size and the parameter3 curves of |r_nn| ÷ σ_min against n, one per Kahan parameter. Every curve rises without turning over, reaching 4·10⁶ at n = 40, c = 0.5. Column pivoting makes no interchange at any point on any of them, so the failure is not a poor choice — there is nothing to choose.815222936110¹10²10³10⁴10⁵10⁶10⁷10⁸size of the matrix|r_nn| ÷ σ_minthe two agreec = 0.2c = 0.35c = 0.5no ceilingratio at n = 1021ratio at n = 404·10⁶interchanges, anywhere0the greedy rule never had a choiceand the gap grows with every row
Fig. 24 The matrix field’s own example of a rank verdict that is a decision rather than a fact, for comparison — where at least the object being decided about exists.
What a rank-10 approximation can achieve, by spectrumA semi-logarithmic plot of singular value against index for three spectra — geometric decay, algebraic decay, and flat — with the rank-ten approximation error marked on each.1112131415110⁻³10⁻²10⁻¹1index jσⱼσ11geometric, 0.85ʲalgebraic, j^−0.50flatmeasured, and equal to σ₁₁rank-10 error, geometric0.2rank-10 error, algebraic0.3rank-10 error, flat160×60, spectrum chosen rather than the entriesthe matrix decides, not the method
Fig. 25 And a spectrum with no gap in it, from the randomised field, which is the matrix case’s version of a question with no clean answer.
Relative error of three summation algorithms in binary32A log–log plot of relative error against the number of terms for naive, pairwise and compensated summation, each measured against the exactly rounded sum.10¹10²10³10⁴10⁵10⁶10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹number of terms addedrelative error against the exact sumin orderin a treecompensatedbinary32 · terms are 1/icompensated: 3·10⁻⁸
Fig. 26 What a difference of two large numbers costs at the far end of the sequence, measured in the field that owns it.

Where this goes next

12345678910⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1rank k of the approximation‖A − Aₖ‖measured, 2-normσₖ₊₁, from theorymeasured, Frobeniusthe first two agreeto 4.3·10⁻⁹worst |‖A−Aₖ‖₂ − σₖ₊₁| / σₖ₊₁4.3·10⁻⁹worst Frobenius discrepancy4.3·10⁻⁹κ = 10⁹; 30 random rank-3 matrices, none closerthe error is σₖ₊₁ The best approximation there is The error of the best rank-k approximation is not bounded by the next singular value. It is equal to it. That is an unusually sharp theorem, and it makes the theorem itself usable as an independent check on the computation. 1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision Rank is a decision A floating-point matrix does not have a rank. It has a spectrum of singular values, and somewhere in that spectrum is a place where the values stop being signal and start being noise. Deciding where is a judgement, and the evidence for it is a gap. 03672108144180216024681012eigenvalues in orderλthe closed formmarks: the assembled matrix, decomposeda spectrum nobody computedrows of the matrix216numbers that describe it108λ smallest0.59λ largest11worst |computed − exact|7.1·10⁻¹³the matrix is never neededand neither is its decomposition An index that is a pair A discretisation on a two-dimensional grid of n points a side has n² unknowns and a matrix with n⁴ entries — 10⁸ at n = 100. What that matrix is instead is two Kronecker products of an n × n matrix, which is 2n² numbers, and nothing has been approximated: assembling it was the mistake.

Reads more easily once this is understood

Essays that name this one as worth reading first.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Border rankEckart–YoungHyperdeterminantIll posed problemLow-rank approximationNumerical rankSeparabilityTensor rankTruncated svdUnfolding