Numerical Linear Algebra
where the algebra stops being the arithmetic
Two errors, and whose fault they are

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 gets further away as the sequence goes on — because the decomposition has a condition number of its own, and it is 2n².
33 min read 26 figures Whose fault is itExact ground truthMeasured, not asserted

Worth reading first: The condition number is an amplifier · The exact answer to a nearby problem · A nearest point that is not there.

This field’s first essay puts a number on how much a problem amplifies a perturbation, and every essay since has used it in one identity:

forward error ⪅ condition number × backward error

What has always been meant by the problem is a solve. A matrix and a right-hand side go in, a vector comes out, and the condition number is a property of the matrix. This essay is about the same identity applied to an object that is not a solve, and about a case where every quantity in it is known in closed form.

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. 1 A sequence of tensors, every one of which is exactly a sum of two rank-one terms. The rising curve is the conditioning of the step a fit takes; the middle marks are what a fit from a random start actually achieves.

What is being conditioned

A decomposition is a map. Its input is an object and its output is a set of factors, and the question is how far the factors move when the object does.

That is a different question from the one this field usually asks, and the difference is not cosmetic. The condition number of the tensor — however defined — is a property of the object. The condition number of the decomposition is a property of the map from the object to the parameters, and the two can be as far apart as anything.

The clearest way to see that they must be different is to note that the second depends on the rank being asked for and the first does not. The same tensor decomposed at rank two and at rank three has two different maps to condition, and only one object.

How much a perturbation of the right-hand side is amplified, κ = 10⁶The cumulative distribution of the amplification factor over two hundred random perturbation directions, with the condition number marked as the upper limit.110¹10²10³10⁴10⁵10⁶10⁷00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10·10⁵worst found 7.6·10⁵6×6, 200 directionsmedian reaches 0.29 of κ
Fig. 2 The field’s original quantity, from the essay that introduces it: an amplification from a backward error to a forward one, on a solve.

The sequence, which has an answer at every stop

The tensors used here are the ones the tensor field’s third essay is built on:

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

Every one of them is a difference of two rank-one terms, so every one of them has rank at most two, and both terms are written down. There is no question of existence anywhere on this page: the answer is on the paper.

What the sequence does is approach a tensor of rank three, so its two terms become nearly collinear and nearly cancel. That is a statement about the factors, not about the tensor — the norms of the A_n are all within a few per cent of one another — and it is exactly the situation in which a decomposition’s conditioning and its object’s part company.

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. 3 The sequence itself, from the field that introduces it: a residual falling and a term size rising, with their product descending onto √3.

Why the tensor’s own conditioning is the wrong thing

The natural first move is to ask what the tensor’s condition number is and to expect the answer to explain everything. It does not, and the reason is worth being precise about because it is the refusal at the bottom of this page.

Every A_n has a norm within a few per cent of √3 and a smallest unfolding singular value within a factor of two of one across the whole sequence. Whatever quantity is chosen to stand for “the conditioning of this tensor” — the ratio of its unfolding spectra’s extremes, the ratio of its largest and smallest entry, the sensitivity of its norm to a perturbation of its entries — none of them moves by more than a small factor while the difficulty rises by three orders of magnitude.

The reason is that the difficulty is not in the object; it is in the question. Asking for a rank-two decomposition of A_n is asking for two vectors per mode whose outer products cancel to leave something much smaller than either, and the sensitivity of that request is a property of the request. Asking for a rank-three decomposition of the same tensor is a different request with a small condition number.

This collection has met that distinction once before, in the essay about the object a question names against the object worth computing. Here it takes its sharpest available form: one object, two questions, and a conditioning that differs by 10³ between them.

‖AX̂ − I‖ and ‖X̂A − I‖ for a computed Hilbert inverse, to n = 12Two residuals of the same computed inverse, each divided by ‖A‖‖X̂‖ so both are dimensionless. The exact inverse satisfies both to zero. The computed one satisfies ‖AX̂ − I‖ at 3.5·10⁻¹⁸ — the side its columns were solved along — and ‖X̂A − I‖ at 6.8·10⁻¹⁶, 195 times larger, at n = 12. Each column of X̂ is the exact solution of a slightly perturbed system, but a different perturbation for each column, so there is no single nearby matrix whose inverse X̂ is.468101210⁻²⁰10⁻¹⁹10⁻¹⁸10⁻¹⁷10⁻¹⁶10⁻¹⁵10⁻¹⁴10⁻¹³nresidual / (‖A‖ ‖X̂‖)‖X̂A − I‖‖AX̂ − I‖the two sides, comparedn = 6, ratio6.4n = 8, ratio8.3n = 10, ratio82n = 12, ratio195the exact inverse satisfies bothand the computed one satisfies the side it was computed along
Fig. 4 The earlier version of the same distinction, from the essay that measures it: two ways of asking for the same answer, differing by twelve orders of magnitude in backward error.

The closed form

Each sweep of an alternating fit solves an r × r system whose matrix is the entrywise product of the other modes’ Gram matrices. That matrix, not the tensor, is what becomes singular.

For A_n the exact factors are known, so the matrix can be evaluated on them rather than on whatever an iteration returned. With v = (1, 1/n) the factor matrix is [[1, 1], [1/n, 0]] in every mode, its Gram is [[1 + 1/n², 1], [1, 1]], and the entrywise product of two of them is

V = [[(1 + 1/n²)², 1], [1, 1]]

whose condition number has a closed form in n and whose asymptote is 2n².

Measured, it runs 9.57, 33.1, 129.0, 513.0, 2049.0 and 8193.0 at n = 2, 4, 8, 16, 32 and 64, and the fitted slope of log κ against log n is 1.96. The marks on the hero figure are the measured values and the dashed line is the closed form; they agree to eight digits.

The other quantity that closed form is checked against is the collinearity of the two terms, which is 1/√(1 + 1/n²) exactly and goes to one. So the two descriptions — the terms line up and the step becomes singular — are the same statement with a formula connecting them.

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 1.1·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 = 1024. Started at the answer instead, the same code stays within 9.2·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⁻⁸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 = 10242.1·10⁶its closed form2.1·10⁶cosine of the terms1from a random start0.012from the answer9.2·10⁻⁹the answer existsand cannot be found
Fig. 5 The same measurement carried three decades further, to n = 1,024, where the closed form is a difference of two numbers agreeing to eleven digits and is the less accurate side of the comparison.

What it costs

The identity says a forward error is the condition number times a backward error, and both are available here.

The backward error is tiny at every stop: the fit reproduces the tensor to a few parts in a thousand at worst, and to the rounding level where it succeeds.

The forward error is in the factors, and it is everything. A three-hundred-sweep fit from a random start reaches 2.1·10⁻⁴ at n = 2 and 1.2·10⁻² at n = 64 — that is, it gets worse as the sequence goes on, by a factor of 56 over five doublings, while the answer it is looking for stays exactly as available as it was.

The control that makes that a statement about conditioning rather than about the code is the third curve. Started at the answer, the same fit stays within 2.3·10⁻⁹ of it at every stop. Not the rounding level — the drift from an exact start is itself about κ times the unit roundoff, which is the identity again — but nine orders below what a random start reaches.

So: a tensor that is exactly rank two, whose rank-two decomposition is written down, and which a standard method cannot recover.

Backward and forward error against the condition numberA log–log plot over twelve decades of condition number. The backward error is a flat line at ten to the minus sixteen; the forward error rises in proportion to the condition number.110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)relative errorforward errorbackward errorpredicted: κ · u8×8, 20 seeds per κ; dashed is the worstthe problem worsens, not the method
Fig. 6 The two errors this field separates, from the essay that separates them: the one that can be seen and the one that matters.
Backward error, forward error and the condition number, with measured valuesTwo boxes at the top — the problem posed and the nearby problem the algorithm answered exactly — and two answers below them, with the distances between all four labelled by numbers from a Hilbert solve.the problem you posedA = H12b = A·(1, 2, …, 12)the problem it answered exactlyA + δA, b + δb‖δ‖ / ‖A‖ = 1.8·10⁻¹⁷the answer you wantedx = (1, 2, …, 12), exactlythe answer you gotx̂, wrong by 0.02 relativebackward error 1.8·10⁻¹⁷forward error 0.02κ = 1.8·10¹⁶κ · η = 0.33, and the measured forward error is 0.02.The algorithm is not at fault. The problem is.H12, LU with partial pivotingresidual and error differ
Fig. 7 And the identity itself, drawn — the same three quantities as on this page, on a problem where the conditioned object is a matrix.

An ill-posed problem is one with an infinite condition number

The limit is worth taking, because it connects this page to a phrase the regularisation field uses constantly.

As n grows, κ grows like 2n² without bound, and in the limit the tensor is the rank-three object whose distance to the rank-two set is zero and which no rank-two tensor equals. A decomposition of it at rank two does not exist, so the map being conditioned has no value there — and a map whose value does not exist is the limit of maps whose conditioning diverges.

That is what ill-posed means operationally, and this collection’s regularisation field says the same thing about a different object: a problem whose data does not determine its answer has an infinite condition number, and something outside the data has to choose. Here the something outside the data is the rank, and choosing it one higher makes the problem well posed instantly — a rank-three fit to the limit reaches the rounding level in fifty sweeps.

Singular values and |uₖᵀb|, with and without 0.10% noiseThree curves against the index on a logarithmic vertical axis. The singular values fall exponentially to the level of rounding. With an exact right-hand side the coefficients fall faster and every term of the solution stays bounded. With noise they flatten at index 32, and from there on each term is noise divided by a σ of 6.8·10⁻⁴.081624324048566410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹index kmagnitudethe floor: k = 32best truncation: k = 28σₖ|uₖᵀb| exact|uₖᵀb| with noisetwo different indicesthe crossing, from the data alone32the truncation that is actually best28relative error there0.11the exact coefficients never flattenthe noisy ones stop at ‖e‖/√n
Fig. 8 The regularisation field’s picture of the same word, from the essay that measures it: a spectrum with no gap, and a solution the data does not determine.
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. 9 And what an optimiser does at the limit, from the field that measures it.

Where the collinearity comes from

It is worth separating two things that both make a decomposition ill-conditioned, because only one of them is about the boundary.

Terms that are nearly collinear. Two rank-one terms whose vectors point nearly the same way are nearly the same term, so their coefficients are nearly indeterminate — the same mechanism as two nearly parallel columns in a least-squares design matrix, and this collection has an essay about that.

Terms that are large and cancel. Two terms of magnitude 10 whose sum has magnitude 1.7 mean that the data is a difference of things much larger than itself, which is the arithmetic field’s subject.

On this sequence they are the same phenomenon, because the construction produces both at once. They are separable in general: a decomposition can have well-separated terms of enormous size (no problem), or nearly collinear terms of modest size (a problem). The quantity that catches the second is the Gram product’s condition number, which is why it is what the code reports.

Fitting the same degree-11 polynomial in two basesOn the left, the data and two fitted curves that lie on top of each other. On the right, the condition numbers of the two design matrices, ten orders of magnitude apart.00.10.20.30.40.50.60.70.80.910.20.40.60.81xyboth fits, drawn on top of one anothercondition number of the design matrixmonomial1.2·10⁸Chebyshev2.5largest fitted coefficientmonomial113Chebyshev0.51rms residual: 3.9·10⁻⁶ and 2.9·10⁻⁷ — the data is fitted either way.30 points, degree 11, single precisionthe basis is part of the problem
Fig. 10 The least-squares field’s version of the first mechanism, from the essay that measures it: a design matrix whose columns nearly agree.
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. 11 And the arithmetic field’s version of the second, which is what the far end of the sequence runs into regardless of the conditioning.

Two routes to the same number

The conditioning here is checked the way everything else on this site is: by computing it twice.

The closed form comes from the algebra. The exact factors of A_n are written down, their Gram matrices are 2 × 2, the entrywise product of two of them is 2 × 2, and its condition number is an expression in n. Evaluating that expression involves no decomposition and no iteration.

The measured value comes from forming the same matrix numerically at the exact factors and taking its condition number with the site’s own decomposition. That involves a decomposition and is subject to rounding.

They agree to eight digits over six doublings, which is what makes the dashed line on the hero figure a check rather than a fit. At n = 1,024 they stop agreeing to eight digits, and the reason is instructive: the closed form is a difference of two numbers that agree to eleven digits, so the formula is the less accurate side of the comparison. That is stated in the assertion’s tolerance rather than hidden in it.

Three routes to the error of a rank-k approximation of one block, at q = 0.5The upper line is q^(p+1)/(1 − q), which used four numbers about two intervals and no entry of the matrix. The middle line is the truncated expansion actually evaluated — a rank p + 1 matrix written down as a table of powers, with no decomposition anywhere in it — and it falls at -0.36 decades a column, close to the log₁₀ q = -0.30 the bound predicts. The lower line is the decomposition, which is optimal by construction, and it falls at -1.74 — 4.8 times as fast. Two of these curves share no arithmetic. What they agree on is that the error is geometric in the rank; what they disagree on is the base, by a factor in the exponent rather than a constant, and the disagreement is why a partition allocated from the bound is safe and wasteful at the same time.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹rank of the approximationrelative errorthe boundthe expansion, evaluatedthe decompositiontwo routes, one shapebound at rank 50.063expansion at rank 50.0048decomposition at rank 52.8·10⁻⁹written, decades a column0.36best, decades a column1.7one route used the matrixand the other used four numbers
Fig. 12 The hierarchy field’s version of the same discipline: a rank obtained by a decomposition and by arithmetic on two endpoints, made to agree.

What can be done about it

Three answers, and the first is the one that generalises.

Report the conditioning. It costs one small condition number per sweep, it is computable from quantities the method already forms, and it turns a silent failure into a reported one. Nothing else on this page requires knowing that the target is on a sequence.

Change the rank. A decomposition that is ill-conditioned at rank r is often well conditioned at r + 1, because the degeneracy is two terms trying to represent something that needs three. That is a rank-selection criterion with a number behind it, unlike the residual, which is flat.

Regularise the factors. Penalising the terms’ magnitudes makes the feasible set bounded and removes the divergence outright. What it does not do is recover the answer: it answers a different question, and the regularisation field’s whole subject is what that substitution costs.

Four knobs on one problem at 0.20% noiseRelative error against the fraction of each method's own range, on a logarithmic vertical axis. A truncation, a Tikhonov parameter, a conjugate gradient step count and a randomised rank each have an interior minimum, and the four minima are 0.1127, 0.1113, 0.1113, 0.1126 — a spread of 1%. The horizontal line is the best of them.00.250.50.75110⁻¹110¹10²10³fraction of the method's own rangerelative errorfloor 0.111truncation KTikhonov λCGLS steprandomised rankfour methods, one floortruncation K0.11Tikhonov λ0.11CGLS step0.11randomised rank0.11four knobs from four fieldsand one obstruction underneath them
Fig. 13 The combination field’s measurement of what a penalty buys and where it stops buying, for the third option.
The L-curve, and where four rules put λThe norm of the solution against the norm of its residual, on logarithmic axes, as λ sweeps eight decades. The curve has a corner: to the left of it the noise is being amplified and to the right the signal is being thrown away. Four points are marked — the three rules that use only the data, and the oracle, which requires the exact answer and is not a method.10⁻²10⁻¹110¹10²10³10⁴‖Ax − b‖‖x‖the oraclediscrepancyL-curvegeneralisedscored against a truth none hasoracle, relative error0.11discrepancy principle, as a multiple1.1L-curve corner, as a multiple2.3generalised cross-validation, as a multiple1the oracle needs the exact answer and is not a methodit is the reference the others are scored on
Fig. 14 And the regularisation field’s scoring of the rules for choosing one, which is the cost of the substitution.

What the identity looks like when both factors are known

One more thing separates this page from the rest of the field, and it is the reason the sequence is worth a whole essay rather than a paragraph.

Everywhere else on this site, a backward error is a diagnosis. The algorithm runs, and an analyst then measures how far the problem would have to move to make the returned answer exact. The condition number is a separate measurement of the problem, and the identity is checked afterwards.

Here both factors are known in advance. The condition number of the step has a closed form in n, and the backward error of the fit is bounded by the tolerance the sweep is stopped at. So the forward error is predicted before anything runs, and the measurement is whether the prediction holds.

It does, in the direction that matters: the random-start error rises as the sequence goes on, at roughly the rate the conditioning does, while the exact-start error rises at κ times the unit roundoff. Neither is a tight prediction — the identity is an inequality and the constants in it are not one — and both are the right order.

The hierarchy field made the same observation about a compression tolerance, and its sentence is the one worth carrying: decide the digits the answer needs, divide by κ, and compress to that. Here the sentence reads decide the accuracy the factors need, multiply by κ, and that is the accuracy the tensor has to be given — and for the far end of the sequence there is no such accuracy, because κ has outrun the arithmetic.

The backward error of a hierarchical solve, against the error of the representation it usedSolve A_H x = b exactly and the residual against the matrix that was wanted is b − Ax = (A_H − A)x, so ‖b − Ax‖ ⁄ ‖A‖‖x‖ cannot be anything but the representation's own error. Measured across six accuracies spanning ten decades, the two track at a slope of 0.994 and sit a constant 6.7× apart, which is the difference between a norm of a matrix and a norm of that matrix applied to one vector. The reading is the one this field is built on: the accuracy knob is not an accuracy, it is a backward error chosen in advance. Everywhere else on this site a backward error is something an algorithm produced and somebody then measured; here it is a line in the program, and its size is known before the solve starts.10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³‖A − A_H‖ ⁄ ‖A‖, the representation‖b − Ax‖ ⁄ ‖A‖‖x‖, the solveequala backward error, chosenslope0.99representation at 10⁻⁸1.2·10⁻⁹backward error there1.3·10⁻¹⁰representation at 10⁻¹²1.2·10⁻¹³backward error there2.5·10⁻¹⁴the compression is not an approximationit is a perturbation of the problem
Fig. 15 The hierarchy field’s version of both factors being known in advance, from the essay that establishes it: a slope of 1.000 over ten decades.
The forward error of a hierarchical solve, and κ times the backward error that was chosen for itForward error ⪅ condition number × backward error is the identity this collection is organised around, and it is normally used after the fact: the algorithm ran, somebody measured what it did, and the condition number explains the difference. Here both factors are known in advance — κ = 24.39 is a property of the problem, and the backward error was set at the top of the program — so the upper line is a prediction rather than an account. The measured error tracks it at a slope of 0.981 and sits 14× below it throughout, which is the usual looseness of a worst-case bound applied to one right-hand side and not a failure of the prediction. What the figure licenses is the sentence a code needs: decide how many digits the answer requires, divide by κ, and compress to that.10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹‖A − A_H‖ ⁄ ‖A‖, chosen‖x − x*‖ ⁄ ‖x*‖κ × the chosen backward errorthe error in the answerboth factors known firstκ24chosen at 10⁻⁸1.2·10⁻⁹predicted forward3·10⁻⁸measured forward1.6·10⁻⁹bound ⁄ measured19the amplifier, used forwardsfor once
Fig. 16 And the forward error that follows from it there, which is the same prediction this page makes about a decomposition.

The refusal

The claim under test is the one that makes the whole page unnecessary if it is true: that an ill-conditioned decomposition is a decomposition of an ill-conditioned object, so the tensor’s own conditioning is the thing to look at.

The assertion that the step’s condition number stays within half of its starting value along the sequence is fed the two ends. It fails: 9.57 at n = 2 and 8,193 at n = 64, a factor of 856, on a sequence whose members all have nearly the same norm and exactly the same rank.

What that refusal records is that the conditioning here is not inherited. It is a property of the map being asked for — decompose at rank two — and changing the request to rank three makes it vanish without changing the object at all.

The file’s other refusals cover the neighbouring readings. One is fed a swamp run and required to refuse the claim that its terms stay bounded; one is fed the narrow uniqueness case and required to refuse the claim that every CP decomposition is unique; and one is fed a benign run and required to refuse the claim that alternating least squares can go uphill.

At other settings

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 2.2·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.0103 at n = 8. Started at the answer instead, the same code stays within 1.5·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⁻³1ncondition 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 = 8129its closed form129cosine of the terms0.99from a random start0.01from the answer5.6·10⁻¹³the answer existsand cannot be found
Fig. 17 The first three stops, where the conditioning is still small enough that a random start finds the answer.
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 8·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.0117 at n = 32. Started at the answer instead, the same code stays within 8.9·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 = 322049its closed form2049cosine of the terms1from a random start0.012from the answer8.9·10⁻¹²the answer existsand cannot be found
Fig. 18 And five, where it has begun to separate.
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. 19 The sequence carried as far as it is drawn, for the relation between the two quantities on it.
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. 20 Where the limit sits in its own plane, from the field that classifies it.
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. 21 And what a well-conditioned decomposition returns, for contrast: the same answer from every starting point.
How much a perturbation of the right-hand side is amplified, κ = 10⁴The cumulative distribution of the amplification factor over two hundred random perturbation directions, with the condition number marked as the upper limit.110¹10²10³10⁴10⁵00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10000worst found 76206×6, 200 directionsmedian reaches 0.29 of κ
Fig. 22 The amplifier at a smaller condition number, for reading the identity at two scales.
The condition number of one eigenvalue, at an off-diagonal entry of 100A rising curve against the size of an off-diagonal entry, on logarithmic axes, with a flat line at one below it and a vertical marker at the current value.110¹10²10³110¹10²10³off-diagonal entry ccondition number of the eigenvalue√(1 + c²)decoupled: 1measuredthree routes, one number‖A − ZTZᵀ‖/‖A‖1.7·10⁻¹⁵closed form100computed 1/|yᵀx|100worst measured movement46four eigenvalues, two conditioning numbersthe symmetric case has one, and it is 1
Fig. 23 The spectra field’s version of a condition number attached to one output rather than to the problem, which is the nearest relative of this page’s quantity.
sep(A, B) and the smallest |λᵢ(A) + μⱼ(B)| as the departure from normality grows, n = 6A and B are upper triangular with diagonals 1, 2, …, 6 and μ above them, so every eigenvalue sum is at least 2 at every point on the axis and the flat line is exact rather than nearly flat. sep — the smallest ‖AX + XB‖_F over ‖X‖_F = 1, and the reciprocal of the amplification a perturbation of C receives — starts equal to the gap at μ = 0, where the matrices are normal, and falls to 9.47·10⁻⁴ at μ = 8. The number a reader is invited to consult is the one that does not move.01234567810⁻⁵10⁻⁴10⁻³10⁻²10⁻¹110¹μ, the entry above the diagonalsep, and the eigenvalue gapmin |λᵢ + μⱼ|sep(A, B)the spectra never moveeigenvalue gap, throughout2sep at μ = 02sep at μ = 89.5·10⁻⁴amplification there1056solvability is the eigenvaluesand conditioning is not
Fig. 24 And the structure field’s, where the conditioning of a subspace is not the gap anybody expects.
How close Hager's estimate is to the true κ₁, over 200 seeded 12×12 matricesFive bars. The estimate is exactly the true condition number on 84% of the sample and inside ten per cent on 90%; the worst underestimate in the whole sample returns 36% of the truth. The last bar is the matrix built to defeat it, at 7.7%, well below anything the random sample reached.each bar is a percentage — of the sample, or of the true condition numberexactly right83.5%inside 10%89.5%inside a factor of 289.5%worst in the sample, ×10035.7%the constructed matrix, ×1007.7%usually exactexact share0.83worst of the sample0.36the constructed matrix0.077a routine that is right most of the timeand never wrong in the safe direction
Fig. 25 The condition estimator every library prints, from the essay that fools it — the reminder that a reported conditioning is itself a computed quantity.
Two condition numbers of one 8×8 system, as its rows are put into different unitsFour curves against the spread of the row units, in decades. κ_∞ of the scaled matrix rises from 9.83 to 1.9·10⁸ while the componentwise condition number stays at 6.98 throughout — the same system, the same solution, and one of the two numbers is a fact about the units. Hilbert's two numbers are drawn flat beside them at 3.4·10¹⁰ and 1.2·10¹⁰: a matrix whose sensitivity no scaling repairs.02468110²10⁴10⁶10⁸10¹⁰10¹²spread of the row units (decades)condition numberκ_∞(DA)cond(DA)Hilbert κ_∞Hilbert condone system, two numbersκ_∞ at no spread9.8κ_∞ at 8 decades1.9·10⁸cond, either end7Hilbert, equilibrated1.3·10¹⁰the solution is the same at every spreadand one of these curves knows it
Fig. 26 And the reminder that a condition number is a choice of units, which is why the quantity on this page is scaled before it is compared with anything.

Where this goes next

110¹10²10³10⁴10⁵10⁶10⁷00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10·10⁵worst found 7.6·10⁵6×6, 200 directionsmedian reaches 0.29 of κ The condition number is an amplifier κ is usually introduced as a definition and then quoted. It is a measurement: perturb the input by a known amount, look at how much the output moves, and the largest ratio you can find is the number. 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 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. 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 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.

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 squaresBackward errorBorder rankCondition numberCondition squaringCP decompositionExact ground truthForward errorIll posed problemTensor rank