Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Degeneracy — where it appears

The behaviour of a fit whose terms nearly cancel: two or more components grow large and point almost the same way, so their sum is small while each is not. It marks a model with more terms than the data support, or a best approximation that does not exist at that rank.

Named by 9 essays across 2 fields — each of them below, with the objects they name alongside it.

01210⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹terms fitted1 − the largest cosine between two fitted terms3 — the tensor's rank45below this line, two terms are the same termthe residual says nothing3 terms, collinearity0.524 terms, collinearity15 terms, collinearity13 terms, error2.1·10⁻¹⁴4 terms, error10⁻¹³4 terms, sweeps76one term too manyand two of them cancel

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.

tensor · Alternating least squares at rank threelowest across tensors1highest across tensors1at rank fourlowest across tensors0.056highest across tensors0.25234500.20.40.60.81rank fittedagreement among the starts that reach itsix planted tensorsdashed: the true rankeach line one tensor, fitted at ranks two to fivefive starting points at every rank

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.

tensor · Alternating least squares no noisesweeps to stop49final error2.5·10⁻¹⁴1% noisesweeps to stop6000largest term, ÷ data0.67110¹10²10³10⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1sweeprelative change in the error, per sweepthe stopping test1% noiseno noise: stops at 10⁻¹⁴the clean run stops; the noisy one crawlsits terms stay the size they were

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.

tensor · Alternating least squares 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.

tensor · Alternating least squares 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.

tensor · Tensor rank term size ÷ normτ 0.01, smallest term ratio3.8τ 0.003, smallest term ratio6.9τ 0.001, smallest term ratio1210⁻³10⁻²10⁻¹110¹stop when the error is within τ of the distancelargest term ÷ tensor's normmedianthree times the normgrey: one line per drawone per cent is not early enough

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.

tensor · Tensor rank 0246810121416neverno extra rowsthe guess as it standsa basis chosen by z/sregularised, δ = 10⁻¹⁰basis point, any multipliers2 extra rowsthe guess as it stands3 of 6a basis chosen by z/sregularised, δ = 10⁻¹⁰4 of 6basis point, any multipliers4 extra rowsthe guess as it stands6 of 6a basis chosen by z/s4 of 6regularised, δ = 10⁻¹⁰4 of 6basis point, any multipliers8 extra rowsthe guess as it stands6 of 6a basis chosen by z/s5 of 6regularised, δ = 10⁻¹⁰5 of 6basis point, any multipliersfirst iterate whose crossover certifiessix programmes a row; QP shown, LP the samethe multipliers are a set

The multipliers were a set

A crossover that solves the equality problem an interior-point iterate's diagonal suggests, then certifies the answer, refuses a guess with more active rows than unknowns — which a degenerate vertex produces as a matter of course. The two remedies a simplex code and a regularised solver would reach for, choosing a basis or regularising the extra rows, both return the right point from the first or second iterate, and both fail the certificate on most programmes, at almost every iterate. The point is never what fails. The certificate checks the one multiplier vector a solve happens to return, and at a degenerate vertex the multipliers are a set; asking whether the set holds a nonnegative vector certifies the same point at once.

constraint · Interior-point conditioning 110¹10⁻²10⁻¹110¹largest term ÷ tensor's norm(error − distance) ÷ C4 × the balance μ2 × the balance μ1 × the balance μ0.5 × the balance μ0.25 × the balance μdashed: the unbounded fit's law · dotted: size threethe penalty walks the same curve

The penalty walks the same curve

A rank-two fit to a random 2 × 2 × 2 tensor of rank three has no best answer: its error falls towards the tensor's distance to the boundary along a law, d + C/s², while its terms grow without limit. A penalty on the term sizes restores a best answer, and the prediction was that its error at terms three times the tensor's norm would sit within ten per cent of the law's d + C/9 — on the assumption, unproved, that the unbounded fit's path is already the best trade between size and error. On twelve tensors the penalised fit's error at that size is within 1.1 per cent of the law, and every penalised fit with terms past two and a half times the norm lies on the same curve. The assumption holds as far as a penalty can test it. And the penalised fit needs tens of thousands of sweeps to settle where the unbounded fit arrives in at most 144, so the cheap way to a bounded fit is to stop the unbounded one when its error reaches the law's price — not when its terms reach the bound, which on four tensors of twelve happens before the fit has found the boundary at all.

tensor · Tensor rank 0246810121416182022slack exactly zerothe guess as it stands××××××a basis by the diagonal×××××regularised××××××the set questionslack 10⁻⁶the guess as it standsa basis by the diagonalregularisedthe set questionslack 10⁻⁸the guess as it stands××××××a basis by the diagonalregularised××××××the set questionslack 10⁻¹⁰the guess as it stands××××××a basis by the diagonalregularised××××××the set questionslack 10⁻¹²the guess as it stands××××××a basis by the diagonalregularised××××××the set questionslack 10⁻¹⁴the guess as it stands××××××a basis by the diagonal×××××regularised××××××the set questioniterate from which every later iterate certifies× at the right: never settles in the runlate where the rows are near, not on

The row that was nearly there

Move the spare rows of a degenerate vertex off it by 10⁻⁶ to 10⁻¹⁴ and the set question still certifies the last iterate of every run, as predicted. It no longer certifies early. Between 10⁻⁶ and 10⁻¹⁰ it waits nine to seventeen iterates, because the basis it certifies holds a near row at zero and its point sits three to forty-eight times that row's slack outside the feasible set. At 10⁻¹² the same displacement falls under the certificate's tolerance and the set certifies from the first iterate. The basis turns when μ passes a tenth of the slack, while the diagonal still calls every near row active.

constraint · Interior-point conditioning

Named alongside it

The objects these essays reach for when they reach for this one.

Alternating least squaresTensor rankBorder-rankCP decompositionStopping criterionSwampIll-posed problemUniquenessActive setCertificateConvergence rateForward error

All concepts