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 3 essays across one field — 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

Named alongside it

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

Alternating least-squaresBorder-rankCP decompositionIll-posed problemSwampTensor rankUniquenessStopping criterionConvergence rate

All concepts