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

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.
18 min read 5 figures Measured, not assumedTwo routes to a numberClaims that can fail

Worth reading first: A nearest point that is not there · An iteration that walks out of the set.

A fit with no answer to find fitted rank-two decompositions to random 2 × 2 × 2 tensors whose slice pencil has a complex pair — tensors of rank three, which have no best rank-two approximation. The fit did not wander. Its error settled at a number, and that number was the tensor’s distance to the surface where its pencil has a double eigenvalue, the boundary of the closure of the rank-two set, computed by Newton’s method with no fitting at all. Meanwhile the fit’s terms grew without limit, cancelling each other, and the error’s excess over the distance fell like the inverse square of their size.

The essay’s open question turned that into a stopping rule. “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.”

The figure at the top is each draw’s largest term at the stop, over the tensor’s norm, against the tolerance. At one per cent the median term is about seven times the norm and the smallest 3.8. No draw is within three. The stop works — it ends the fit at a stated distance from the best achievable error — but it does not end it before the terms have grown, and the reason is the law the prediction cited.

The stop

The draws are the first twenty-four seeded random 2 × 2 × 2 tensors, from seed 200, whose pencil has a complex pair; their distances to the boundary run from 0.0057 to 0.21 of their norms. For each, the distance dd comes from the earlier essay’s Newton solve on the discriminant’s zero set, and the fit is alternating least squares from one fixed random start, run for 20,000 sweeps. The stop at tolerance τ is the first sweep at which the fit’s relative error is at most (1+τ)d(1+\tau)d, for τ of a tenth, three hundredths, a hundredth, three thousandths and a thousandth. At each stop the record is the sweep and the size of the largest rank-one term — the product of its three factor columns’ norms — over the tensor’s norm.

One draw of the twenty-four is set aside, and why is its own small result. On seed 266 the computed distance is 0.559, and the fit’s error falls below it at the first sweep and settles at 0.181. A fit’s error cannot fall below the true distance to the closure of the rank-two set, so the Newton solve there converged to a point of the surface that is not the nearest one. The fit caught it.

The rank-two fit's error after 20,000 sweeps against the distance to the boundary computed by Newton's method, every draw24 draws; 23 lie on or just above the diagonal. Seed 266: computed distance 0.559, fit error 0.181 — the fit beats the distance, so the Newton solve stopped at a point of the surface that is not the nearest.10⁻²10⁻¹110⁻²10⁻¹1computed distance to the boundaryfit's error, 20,000 sweepsseed 266dashed: error equal to the distancethe fit checks the distance
Fig. 1 The fit’s error after 20,000 sweeps against the computed distance for all twenty-four draws; the dashed diagonal is error equal to distance.

Twenty-three draws sit on the diagonal or just above it, as they should. Seed 266 sits far below. The Newton solve starts from the point where the tensor’s own gradient step reaches the surface and then solves the conditions for a stationary distance, which a nearest point satisfies and so do farther ones; on this tensor it converged to one of the farther ones. A stopping rule that trusts a computed distance needs that check, and the check is free: a fit’s error below the distance means the distance is wrong.

One per cent is not early enough

On the twenty-three remaining draws, every one reaches a tenth of the distance within 20,000 sweeps, with terms 1.6 to 7.3 times the norm. Twenty-one reach a hundredth, with terms 3.8 to 12.9 times the norm; seventeen reach three thousandths, at 6.9 to 17.5; thirteen reach a thousandth, at 11.9 to 23.3. The median term roughly triples for each tenfold tightening of τ.

One random 2 × 2 × 2 tensor at distance 0.102 from the boundary: the fit's excess error over the distance against its largest term, through 20000 sweepsAfter 10, 30, 100, 300, 1000, 3000, 10000, 20000 sweeps: excess 2.1e-1, 1.1e-1, 5.0e-2, 2.0e-2, 6.5e-3, 2.2e-3, 6.8e-4, 3.4e-4; term size 1.54, 1.89, 2.74, 4.27, 7.40, 12.57, 22.75, 32.10 times the norm. The stops at τ = 0.1, 0.03, 0.01, 0.003, 0.001 fall at sizes 2.00, 3.51, 5.99, 10.85, 18.73.seed 244distance0.1terms at one per cent6110¹10⁻⁴10⁻³10⁻²10⁻¹1largest term ÷ tensor's normexcess error ÷ distanceτ 0.1τ 0.03τ 0.01τ 0.003τ 0.001red: where each τ stops ita slope of minus two, on every draw
Fig. 2 One tensor’s excess error over the distance against its largest term through the run, with each stop marked. The dial chooses among four tensors at different distances.

The shape of every draw’s run is the earlier essay’s law, and the dial shows four of them. On log axes the excess error over the distance against the term size is a straight line of slope minus two: the excess is C/size2C/\mathrm{size}^2 for a constant CC belonging to the tensor. A stop at τ\tau is where the excess, relative to dd, equals τ\tau, so the term size there is

size=Cτ d.\mathrm{size} = \sqrt{\frac{C}{\tau\, d}} .

The prediction read the law as saying one per cent comes early, because an inverse square falls fast. It does fall fast — the excess drops a hundredfold for a tenfold growth in the terms — but it starts high. At a term size equal to the tensor’s norm the excess is already CC, and CC is about three per cent of the norm; for a tensor at distance 0.1, an excess of one per cent of the distance is a thousandth of the norm, thirty times smaller than CC, and the terms have to grow by 30\sqrt{30}, past five times the norm, to get there.

The law’s constant

The largest term at the one-per-cent stop against the tensor's distance to the boundary, with the size the inverse-square law gives, square root of C over τ times d21 draws: d 0.175, size 5.00; d 0.050, size 8.20; d 0.023, size 12.86; d 0.194, size 4.46; d 0.077, size 6.87; d 0.210, size 3.81; d 0.138, size 4.56; d 0.074, size 7.39; d 0.102, size 5.99; d 0.152, size 4.34; d 0.046, size 9.68; d 0.087, size 5.74; d 0.056, size 8.71; d 0.069, size 7.02; d 0.048, size 6.91; d 0.081, size 4.60; d 0.130, size 4.53; d 0.025, size 9.04; d 0.031, size 7.33; d 0.105, size 5.53; d 0.021, size 11.91. C = τ·d·size² runs from 0.0165 to 0.0438, median 0.0322; the solid curve is the median and the grey curves the extremes.τ · d · size²C, smallest0.016C, median0.032C, largest0.04410⁻¹10¹distance to the boundarylargest term ÷ norm, at one per cent0.020.050.235curves: the law at the median and extreme Ccloser to the boundary, larger terms
Fig. 3 The largest term at the one-per-cent stop against the tensor’s distance to the boundary, with the law’s curve at the median constant and at the extremes.

The constant is not one number but it is not far from one. Over the twenty-one draws that reach one per cent, C=τ d size2C = \tau\, d\, \mathrm{size}^2 runs from 0.016 to 0.044, median 0.032 — under a factor of three, across tensors whose distances differ thirtyfold. And a tenfold tighter τ multiplies the size by 2.5 to 3.8, around 10=3.16\sqrt{10} = 3.16, on every draw that reaches both. Those two facts make the size at any stop predictable before the fit is run: with the distance computed, a target τ gives a term size of 0.032/(τd)\sqrt{0.032/(\tau d)} to within a factor of 1.2 above and 1.4 below.

The constant shows no trend with the distance. The three smallest values, 0.016, 0.017 and 0.020, belong to tensors at distances 0.031, 0.081 and 0.025; the three largest, 0.044, 0.043 and 0.043, to tensors at 0.175, 0.046 and 0.056. Whatever sets it is a property of the tensor that the distance does not capture — plausibly how the pencil’s complex pair sits relative to the two eigenvalues the fit is forcing together, which the earlier essay saw closing on each other at the rate the terms grow — and it is narrow enough across these draws that its median is a usable planning number.

What the law says plainly is that the terms at a fixed relative stop grow as the distance shrinks, like 1/d1/\sqrt{d}. A tensor near the boundary — nearly of rank two — is the one whose fit must grow the largest terms to come within a given fraction of its small distance. The relative tolerance is the wrong kind for this: one per cent of a small distance is a small absolute error, and absolute error is what costs size.

Close tensors are slow

Sweeps a rank-two fit takes to come within a tenth and within a hundredth of the distance, against the distance, draws that never get there drawn at the topτ 0.1: d 0.175 5, d 0.050 11, d 0.023 695, d 0.194 11, d 0.077 55, d 0.210 2, d 0.138 92, d 0.074 13, d 0.102 37, d 0.152 12, d 0.046 166, d 0.087 34, d 0.017 1138, d 0.056 171, d 0.069 78, d 0.048 115, d 0.081 38, d 0.006 13622, d 0.130 169, d 0.025 331, d 0.031 467, d 0.105 26, d 0.021 484. τ 0.01: d 0.175 178, d 0.050 2027, d 0.023 12639, d 0.194 101, d 0.077 1110, d 0.210 121, d 0.138 133, d 0.074 1198, d 0.102 635, d 0.152 51, d 0.046 3356, d 0.087 686, d 0.017 not reached, d 0.056 2276, d 0.069 1257, d 0.048 2615, d 0.081 883, d 0.006 not reached, d 0.130 177, d 0.025 5817, d 0.031 5898, d 0.105 501, d 0.021 12493. The run is 20000 sweeps.in 20000 sweepsunreached at a hundredth2unreached at a tenth010⁻²10⁻¹110¹10²10³10⁴distance to the boundarysweeps to the stopwithin a tenthwithin a hundredthdashed: the end of the runclose tensors are slow
Fig. 4 Sweeps to come within a tenth and within a hundredth of the distance, against the distance; draws that never get there are drawn above the end of the run.

The same tensors pay in sweeps too. Every draw with a distance above 0.1 reaches one per cent within 700 sweeps, most within 200. The two closest — distances of 0.0165 and 0.0057 — do not reach it in 20,000, and the closest takes 13,622 sweeps to reach even a tenth. The earlier essay found the terms growing like the square root of the sweep count, so sweeps go as the square of the size, and with the size at the stop going as 1/τd1/\sqrt{\tau d} the sweeps go roughly as 1/(τd)1/(\tau d), with a constant that varies more from draw to draw than the size’s does: the scatter in the figure is a factor of five at a given distance.

So the stop is cheap for the tensors that are easy anyway and expensive for the ones near the boundary. That is the opposite of what a stop is wanted for. A fit to a tensor of distance 0.2 settles in a few hundred sweeps under any sensible rule; the stop earns its keep where the fit would otherwise run on, and there it is the slowest.

The stall test lands in the same place

Where a stall test stops a rank-two fit — the error changing by under a millionth of itself — against the stops at one per cent and a tenth of a per cent of the distance22 draws stall at 10⁻⁶: terms 8.2 to 12.4 times the norm, excess 1.2e-3 to 1.5e-2 of the distance. No draw stalls at 10⁻⁹ in 20000 sweeps.110¹10⁻³10⁻²10⁻¹largest term ÷ tensor's normexcess error ÷ distancestall at a millionthone per centa tenth of a per centone dot per draw and stopa stall stops anywhere in a decade
Fig. 5 Where the stall test at a millionth stops each fit, against the stops at one per cent and a tenth of a per cent of the distance, as excess error against term size.

The stop a code actually makes is not the distance stop, which needs a distance; it is a stall test — stop when the error changes by less than a small fraction of itself from one sweep to the next. At a threshold of 10−610^{-6} it stops 22 of the 23 fits, at terms 8.2 to 12.4 times the norm and excess errors from 0.12 to 1.5 per cent of the distance: in the same range as the one-per-cent stop, by accident, because a run whose excess falls as C/size2C/\mathrm{size}^2 and whose size grows as the square root of the sweep count has an error that changes by about a millionth per sweep somewhere in that range. At 10−910^{-9} it stops none of them in 20,000 sweeps.

A still error is not a settled one found a stall test stopping a fit with one term too many before it had converged; here the same test is all that ends a fit with nothing to converge to, and where it ends it says nothing about how close the fit is. The figure puts the stall stops across a decade of excess — from a tenth of a per cent to one and a half — at nearly the same term size. The distance stop at least states its excess.

A stop in the tensor’s units

If the trouble with the relative stop is that one per cent of a small distance is a small absolute error, the remedy is to state the tolerance in the tensor’s units instead: stop when the error is within ε of the distance, ε a fraction of the tensor’s norm. The law then gives a term size of C/ε\sqrt{C/\varepsilon}, with the distance gone from it.

Measured on the same runs, it does what the law says. Stopped within 10−310^{-3} of the norm, all twenty-three draws stop — including the two the one-per-cent stop never reached — with terms between 4.1 and 6.6 times the norm, a spread of 1.6 against the relative stop’s 3.4, in 122 to 6,395 sweeps. Within 10−210^{-2} of the norm they stop at 1.5 to 4.5 times the norm in at most 234 sweeps. The price is visible in the closest tensor: at distance 0.0057, an absolute 10−310^{-3} is eighteen per cent of its distance, so its fit stops further from its best than a relative stop would allow. That is the trade stated honestly. A relative stop promises a fixed fraction of the best achievable error and charges near-boundary tensors in size and sweeps; an absolute stop promises a fixed error and a nearly fixed size, and charges them in how close to the best the fit comes.

A fit that has an answer and cannot stop met the mirror image of this choice on a tensor with a best approximation and a spare term; there too the question a stopping rule answers had to be stated in the units the caller cares about, because the iteration itself would not supply one. And a rank that is not a property of the tensor found the same eight numbers of rank three over the reals and two over the complexes; near the boundary there is a third dependence, on the tolerance. A tensor at distance 0.0057 is of rank three, and to any tolerance above that distance it is a rank-two tensor, which is the choice between the two stops in other words.

What the distance buys

The distance stop is the first rule in this field that says how far a fit to a tensor of this kind is from the best it could do, and that is worth having. The test that is a deadline found an indicator that fires on fits with nothing to reach and cannot say how near the end they are; a nearest point that is not there established that the infimum exists and is not attained. With the distance in hand, a fit can report its error as a multiple of the infimum, and a caller can choose τ knowing what it costs: 0.032/(τd)\sqrt{0.032/(\tau d)} in term size, roughly 1/(τd)1/(\tau d) in sweeps.

What it does not buy is small terms. The terms at any useful τ are several times the tensor’s norm, and the decomposition at the stop is two large terms that mostly cancel — a representation whose factors carry digits the tensor does not, which is what one term too many found for a spare term and an iteration that walks out of the set found for the sequence as a whole. A user who needs a usable rank-two factorisation of a rank-three tensor needs a different answer: a constraint that keeps the terms bounded, accepting an error above the distance in exchange, or a rank-three decomposition, which is exact.

The bounded alternative, priced

The law suggests a price for that alternative without running it, on one assumption. The unconstrained fit passes through term size ss with error d+C/s2d + C/s^2; if a fit constrained to terms no larger than ss times the norm can do no better than that — if the fit’s own path is the best trade between size and error, which nothing here proves — then a bound of three times the norm costs an excess of about 0.032/9≈0.00360.032/9 \approx 0.0036 of the norm: for a tensor at distance 0.1, an error 3.6 per cent above the distance; for one at 0.02, eighteen per cent above it. The near-boundary tensor is again the one that pays, now in error rather than size, and the same quantity, C/dC/d, sets the price in both currencies.

What a library could report

None of this needs the stopping rule to be adopted to be useful. A rank-rr fitting routine that can compute, or be given, the distance to the boundary can report two numbers at whatever point it stops: its error as a multiple of the distance, and its largest term as a multiple of the tensor’s norm. The first says how much better any rank-rr fit could be; the second says how much the representation has paid to get there. On the runs here the stall stop at 10−610^{-6} would have reported excesses of 0.12 to 1.5 per cent and term ratios of 8 to 12 — a caller seeing those knows the decomposition is two large cancelling terms near the best achievable error, and can decide whether that is what they wanted, which a bare “converged” never tells them.

What twenty-three tensors do not show

One size, n=2n = 2, where the boundary is the zero set of a single quadratic discriminant and its distance can be computed by Newton’s method in nine unknowns; one random start per tensor; and one family of random tensors. At n=3n = 3 and above the boundary’s equation has degree n(n−1)n(n-1) and the distance is not computed here, so the stop does not yet exist there. The one wrong distance in twenty-four is a warning that the Newton solve needs either several starts or the fit’s check before its answer is trusted.

Still open: the distance at n = 3, and a bounded fit

The distance at n = 3. The boundary for 3 × 3 × 2 tensors is where the pencil has a double eigenvalue, and the distance to it can be found by Newton on the eigenvalue-coincidence condition rather than on the discriminant polynomial. The prediction with a sign is that the fits’ common error at n=3n = 3 equals that distance to within two per cent, as at n=2n = 2, and that the size at a one-per-cent stop follows the same C/(τd)\sqrt{C/(\tau d)} with a constant in the same range.

A fit with its terms bounded. Add a penalty on the term sizes to the least-squares objective and the fit has a best answer again. The prediction is that the penalised fit’s error at a term bound of three times the norm sits within ten per cent of d+C/9d + C/9, the unconstrained law’s value at that size, so that the law prices the bounded alternative before it is run.

Where this goes next

fit ÷ distance, less oneleast excess over the distance1.8·10⁻⁴greatest0.01510⁻²10⁻¹110⁻²10⁻¹1distance to the double-eigenvalue surfaceerror the fit settles atdashed: equalitytwo routes to one number 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. 110¹10²10³10⁻³10⁻²10⁻¹110¹10²10³n‖Aₙ − A‖ and the largest term's norm‖Aₙ − A‖the larger of its two termsan infimum that is not attainedn1024‖Aₙ − A‖0.0017largest term1024their product1.7√31.7the distance goes to zeroand nothing reaches 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. start 1, errorreaches2.8·10⁻¹³stopped by δ = 0.010.0099stopped by δ = 0.0010.0098stopped by δ = 10⁻⁴2.6·10⁻¹³110¹10²10³10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²sweeprelative errorδ = 0.01δ = 0.001δ = 10⁻⁴δ = 10⁻⁵a plateau is a still errorand a still error is what the test asks for A still error is not a settled one A CP fit with one term too many on a noisy tensor never meets the usual stopping test, and its error has settled by sweep 150. A test that asks only whether the error has moved by less than δ of itself over ten sweeps stops those fits by sweep 25, and over twenty-four noisy tensors it names the same rank as the usual test every time, at δ = 10⁻² for 30,250 sweeps against 311,458. But δ = 10⁻² is the tolerance a rank decision states, and on a slow fit that converges it stops five starts of six on a plateau ten orders above the answer and names the wrong rank for four tensors of six. A tenth of the decision's tolerance keeps every decision on both families.

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.

Alternating least-squaresBorder-rankCP decompositionDegeneracyMatrix pencilStopping criterionTensor rank