Numerical Linear Algebra
where the algebra stops being the arithmetic
Theme

The thread: Exact ground truth — page 3

Essays 49 to 72 of the 170 on this theme, in the same order.
1216202428323640444810⁻¹110¹10²grid points nrelative error against the continuous signalbest truncation, 0.117best grid: n = 26best K = 28with noisenoise-freeno λ anywhere in this curvebest grid, error0.13best truncation, error0.12κ on the best grid61grid where it has doubled34every point is an unregularised solvethe grid chose the truncation Regularisation, and the answer that is chosen

The grid was the first filter

A continuous deconvolution discretised on n points and solved with no regularisation at all is not unregularised. Its error against the continuous signal is least at 24, 26 and 34 points for noise of 1%, 0.1% and 0.01% per sample — beside best truncations of 24, 28 and 32 components on a 64-point grid — and within 4 to 16 per cent of their error. The grid's own filter factors sum to n exactly and fall through a half at k = n. Choosing the grid was choosing a truncation, before anybody chose a λ.

 0246810121410⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹interior-point iterationrelative error, and μcertified from iterate 1μthe iterate's errorthe crossover's errorone solve, checkediterations15first certified iterate1iterate error there0.22crossover error there4·10⁻¹⁴the active set arrives long before the digitsand a crossover collects them at once The matrix a constraint makes

The active set before the digits

An interior-point method takes fifteen iterations on a quadratic programme with forty constraints, and its iterate has eight correct digits at the eleventh. Take the constraints its diagonal calls active at the first iterate, solve the equality problem they define once, and check the answer against the conditions for optimality. It passes, to thirteen digits. The step's matrix had a condition number of 43 at that iterate, and 7·10¹⁵ at the last.

 the same lattice, twicewhat the reduction may not changedet, before1det, after1defect, before7.1defect, after1LLL steps1the determinant is the invariantand the defect is what is being reduced Exact arithmetic, and what it costs instead

A basis that describes its lattice badly

The same set of points has infinitely many bases, they are all correct, and they are not equally useful. One measurement separates them — the product of the vectors' lengths over the lattice determinant — and the determinant is the invariant the reduction may not change, which is what makes the reduction checkable.

 the upper pair is distance from the truth; the lower pair is ‖Ax − b‖least squares · error0.08523total least squares · error0.037least squares · ‖Ax − b‖3.965total least squares · ‖Ax − b‖4.078two orderingserror ratio (ls ÷ tls)2.3residual ratio (tls ÷ ls)1seeds40no vector makes the residual smallernot even the one the problem was built from Least squares, and the road not to take

The two numbers a caller has

Choosing between the two least-squares methods is a statement about where the noise is, and the two quantities a caller can compute are both blind to it. The residual separates the answers by 0.14 per cent where their accuracies differ by 14, and κ(A) falls from 3.54 to 2.46 across a sweep in which the error rises by a factor of sixty-two.

 10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻⁷10⁻⁵10⁻³10⁻¹10¹relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error10⁻¹²answer error10·10⁻⁴amplification10·10⁸rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway Exact arithmetic, and what it costs instead

An exact answer to a measured problem

The residual is the zero vector, nothing was rounded at any step, and the answer is wrong in its first digit. Data accurate to fourteen places, an exact solve of the system it defines, and an error of 10⁻⁵ — because conditioning was never a statement about arithmetic and removing the arithmetic error removes none of it.

 10²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)‖x̂ − x‖ / ‖x‖modified, through Qᵀbclassical, either route‖QᵀQ − I‖, modifiedHouseholdermodified, on [A b]κ²uκuforward error at κ = 10⁸Householder4·10⁻⁹modified, through Qᵀb0.13modified, on [A b]2.7·10⁻¹⁰classical840×8, three seeds, against an exact rational solveQ is not orthogonal; x is right Orthogonality, measured

The right-hand side as one more column

Modified Gram–Schmidt's Q is 4.3·10⁻⁹ from orthogonal at κ = 10⁸, and a least-squares solve that multiplies b by it is wrong by 0.13. Hand the same routine b as an extra column instead and the answer is right to 2.7·10⁻¹⁰ — closer than Householder's 4.0·10⁻⁹. Classical Gram–Schmidt gains nothing from the same trick, to the last bit.

 12345610⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹digits of measurement accuracybest relative errorTikhonovtruncationCGLS stepslope 0.89, optimalslope 2/3, Tikhonov's limithow fast the error fallsTikhonov slope0.7truncation slope0.94CGLS step slope0.89optimal 2ν/(2ν + 1)0.89Tikhonov's limit0.67better data, smaller errorat a rate the method may not be able to keep Methods that were designed apart

The method that cannot use a smooth answer

On the collection's own signal four regularisers reach the same floor to a few per cent. Score them instead against answers of increasing smoothness and one stops improving. Across six decades of noise Tikhonov's error falls with a fitted slope of 0.70 whether the answer is twice or four times as smooth, while truncation's rises to 0.94 — and at 10⁻⁶ noise Tikhonov's best is 38 times truncation's.

 -1-0.500.511.520eigenvalue of P⁻¹K1 − φ1φS never formedγ1smallest ν0.056furthest from φ, 1 − φ0.57MINRES steps11an exact Schur approximation, bought by changing Hthe golden ratio without S The matrix a constraint makes

Where the augmentation puts the cost

Add γAᵀA to the objective block of a saddle-point system and its Schur complement tends to I/γ, so the cheapest possible approximation becomes the right one and the golden-ratio spectrum arrives — within 7.6·10⁻⁶ at γ = 10⁶. MINRES falls from 21 steps to 6. The inner solve with the augmented block rises from 14 conjugate gradient steps to 43, their product does not fall at all, and the answer loses seven and a half digits on the way.

 10²10³10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹steps takenlargest relative error in a coefficientcarried factorrecomputedcarried + one correction+ a second correctionHouseholder QR, same rowsdrift of the factorafter 2875 stepsκ(A) of the window2·10⁴carried factor2.8·10⁻⁸recomputed5.8·10⁻⁹carried + one correction7.1·10⁻¹³+ a second correction3.7·10⁻¹²Householder QR, same rows1.1·10⁻¹²measured against the coefficients in exact rationalsthe refresh repairs the factor, not the answer When the problem arrives again

The repair the drift did not need

A sliding window's carried Cholesky factor drifts 3.9·10⁻¹⁴ from its data, and multiplying by κ(AᵀA) predicts eight lost digits in the coefficients, a stream conditioned at 10¹² losing the answer, and a periodic refresh of the factor as the default repair. Measured against coefficients computed exactly in rationals, all three come out differently. On a stream made ill-conditioned by scaling, the conditioning never reaches the coefficients. On a collinear stream, a freshly recomputed factor is as wrong as the drifted one. And one correction from the window's own rows reaches Householder's accuracy for a fraction of a refresh's cost.

 1611162126313610⁻²²10⁻¹⁹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹vertex, clique first then tail|entry| relative to the largestone rounding of the largest entrya bound that is provedPerron root11bracket, low11bracket, high11bracket width1.2·10⁻⁴smallest entry-1.5·10⁻²⁰entries below zero4every entry is positiveand the picture disagrees The matrix that is a graph

An eigenvector that must not change sign

Perron's theorem says the leading eigenvector of a connected nonnegative matrix is strictly positive. On a clique with a long tail, four of its thirty-six entries come back negative — and beside them is the only two-sided bound in these essays that is proved rather than estimated.

 unpreconditionedbest step20rule stops at7its error ÷ best1steps within 10%23truncated at τ = 0.032best step8rule stops at4its error ÷ best1steps within 10%6010203040506010⁻¹110¹steprelative errorrule stops: 7rule stops: 4plain CGLSpreconditionedbars: the steps within 10% of each run's bestthe rule reads the residual, not the window Methods that were designed apart

A stopping rule that follows the run it is given

A preconditioner that reaches the answer four times sooner leaves four steps within 10% of its best instead of sixteen, and a rule that stops by the residual ought to miss so narrow a window more often. Over forty draws of the noise it misses it less: the discrepancy principle stops at 1.030 times the preconditioned run's best against 1.073 times the plain run's. And past the edge it stops within a factor of 1.7 of a run whose own best is 5.5 times Tikhonov's — faithful to a run that has already failed.

 10141822263034384210⁻¹10⁻⁰.⁵110⁰.⁵grid points nrelative error against the continuous signalsampled kernel, hatsintegrated, hatsintegrated, spline0.1% noise, no λsampled kernel, hats, best0.13integrated, hats, best0.12integrated, spline, best0.12truncation of 64 points0.12same nodal unknowns, same databetter at representing the noise too Regularisation, and the answer that is chosen

A better discretisation is a weaker filter

A coarse grid's error has two sources — how well the discrete operator approximates the integral, and how well the grid's function represents the answer — and the grid essay could not separate them. Changed one at a time they separate: integrating the kernel against the hat functions takes a fifth off the 12-point error, reading the answer as a cubic spline takes 15 per cent more, and both roughly double the condition number on every grid. At 0.1% noise the spline discretisation's unregularised solve on 26 points reaches the best truncation of a 64-point grid to 0.3%. At 1% it is worse than the crude grid.

 4914192429343900.20.40.60.81decimal digits of the numbers the lattice is givenshare of trials recovering the relationa double has about this many digitsnumbers that are exactthe same numbers, measureda window with two edgescoefficients up to30exact, at 12 digits1exact, at 401doubles, at 121doubles, at 250doubles, at 400.13one edge is the relationand the other is the data Exact arithmetic, and what it costs instead

A relation among digits that were not there

A lattice finds the exact integer combination of several numbers that vanishes, and it needs enough digits of them to do it. Give it more digits than the numbers have and it finds a relation anyway — among the rounding, with the same confidence and no warning. Recovery runs 8 of 8 at twelve digits and 1 of 8 at forty.

 1357911131510⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1vertexrelative error against the exact answerthree routes, one numberworst, by elimination4.8·10⁻¹⁶worst, by spectrum10·10⁻¹⁶solve residual1.5·10⁻¹⁵Foster's sum15n − 115difference3.6·10⁻¹⁵the answer is a ratio of integersso the error is known The matrix that is a graph

A distance computed by a solve

Effective resistance is the one quantity in this field with no combinatorial route to it — it is defined by a linear system. On a small unweighted graph the answer is a ratio of two integers, so for once the error is known rather than estimated, and every resistance in a graph has to add up to a number fixed in advance.

 234567891010⁻⁴10⁻²1ADI steps krelative error, and max|r|²max|r|²the measured errora bound that is an identitysteps drawn9ratio, worst0.77spread of the ratio1error at k = 103.9·10⁻⁴its residual1.1·10⁻⁴four orders of errorand one constant Reduction, and what a model is for

Bracketing an error nobody can measure

The error of a low-rank Gramian factor is the one quantity a caller cannot compute, because computing it needs the Gramian the factor exists to avoid forming. Two numbers that can be computed sit either side of it — a rational factor known before the run, and a residual known after — and they stay a factor of four apart across a fourfold change of size.

 123456024681012moments Krank of the block Hankel12 eigenvalues insidethe ceiling K·ℓthe ranka ceiling with a knob on itprobes2eigenvalues inside12rank at K = 12rank at K = 612solves, at every K512one ceiling per probeand K of them per moment The eigenvalue problem that is not linear

A ceiling with a knob on it

A contour method returns at most as many eigenvalues as its probe block has columns, and the object that comes back does not distinguish that from having found everything. One line of the derivation multiplies the ceiling by a number the caller chooses, and it costs no extra solves at all.

 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 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 stalls at the same one per cent however far the sequence goes — while a fit started at the answer loses digits exactly as 2n² says it should.

 122028364452606876849210010⁻¹110¹grid points nrelative error against the continuous signalbest with no λ: n = 26no λeach grid's best λTikhonov, 64 points0.1% noise, 16 drawsbest grid with no λ26its error0.1396 points with its λ0.12best λ on fine grids0.0056each point is a median over the same drawsλ belongs to the problem, not to the grid Regularisation, and the answer that is chosen

Where the grid hands over to λ

An unregularised solve on a coarse grid comes within a tenth of the best Tikhonov answer on a fine one, and the pair of a grid and a λ was left unmeasured. Measured, the two do not trade. On every grid up to the best unregularised one no λ helps at all. On every grid of 40 points and more the best λ is the same to within a quarter of a decade — 3.2·10⁻² at 1% noise per sample, 10⁻³ at 0.01% — and the 96-point grid with it beats the best coarse grid by 7, 9 and 13 per cent. The grids between the two, given their own λ, land between them.

 least possible76minimum degree76worst of 300 tie-breaks81reverse Cuthill–McKee85natural order9920 unknownstie-breaks at the least0.44minimum degree ÷ least1every order searched, by the set already eliminatedthe greedy rule found the minimum Sparsity, and what elimination costs

The least fill there is

Finding the elimination order with the least fill is NP-hard, and that is a statement about the hardest graph and the largest size. On a graph of twenty vertices every one of the 20! orders can be searched at once, through the million sets of vertices already eliminated, and the least fill is a number. On the 4×4, 4×5 and 3×7 grids minimum degree finds it exactly. On eighty random sparse graphs of eighteen vertices it finds it on 53 and misses by at most 7.6 per cent, and on every one of the eighty some breaking of its ties finds it.

 10¹110¹skew of the starting basisdistance ÷ the distance to the nearest pointthe nearest lattice pointdashes: the skewed basis's orthogonality defectrounding in the skewed basisrounding in the reduced basisthe same three lines of arithmeticskew40defect there40worst, skewed40mean, skewed26mean, reduced1exact share, skewed0one lattice, one targetand two descriptions Exact arithmetic, and what it costs instead

Rounding a coordinate in the wrong basis

The nearest lattice point is found by writing the target in the basis and rounding each coordinate, which is three lines of arithmetic and is wrong. On a basis skewed by forty it lands a mean of 26 times too far and a worst of 40.02 — the basis's own orthogonality defect, to three figures — and the identical three lines on the reduced basis are exact at every target.

 10⁻³10⁻²10⁻¹110⁻¹⁹10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹1 − ρbackward errorLevinson, Toeplitzelimination, ToeplitzLevinson, any kindelimination, any kindat ρ = 0.999Levinson, any perturbation2.9·10⁻¹⁷Levinson, Toeplitz only6·10⁻¹²the ratio between them2·10⁵diagonal defect of the first0.97the number that is reportedand the number that is asked about Structure, and the solver that cannot see it

The number that cannot rank them

Levinson and Gaussian elimination are indistinguishable on the backward error a library reports — every one of ninety-six measurements between 1.16·10⁻¹⁷ and 5.73·10⁻¹⁷. The structured backward error separates them by up to a hundredfold, in whichever direction the point happens to give. Only the forward error ranks them, and only because this family's exact answer is known.

 38434853586368110¹10²10³10⁴e, where the skew is 2ᵉ + 12345orthogonality defect of the basis returneda double holds k exactlyan orthogonal basisthe invariant sees none of itfloat, at 2^521float, at 2^531.4float, at 2^701.2·10⁴residue at 2^701.2·10⁴exact, everywhere1determinant, always1every step was unimodularand the answer is 12,345 times worse Exact arithmetic, and what it costs instead

The knob and the rounding

The Lovász parameter is the number a lattice reduction is specified by, and moving it from 0.50 to 0.99 strengthens the proved bound from 16.00 to 1.83, costs 91 per cent more steps, and returns a basis with the same orthogonality defect. The one rounding nobody writes down decides everything: above 2⁵³ the reduction returns a basis 12,345 times worse than it should, with the determinant invariant equal to one throughout.

 10¹10³10⁵10⁷10⁹10¹¹10¹³10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹κ(B), the conditioning of the constraint blockrelative error, and feasibilitydashes: the method of weightingthe saddle-point routethe null-space routealong the bottom: how nearly every answer satisfies the constraintsfeasible and wrongκ(B)4.6·10¹²κ(B)·u0.001null space1.2·10⁻⁴saddle point0.0082weighting2.6feasibility10⁻¹⁵every constraint is satisfiedand the answer has no digits Least squares, and the road not to take

Feasible and wrong

A third constraint that nearly repeats the first takes the best route's answer from 2.96·10⁻¹⁵ to 1.16·10⁻⁴, and the other two routes to no correct digit at all. Every one of those answers satisfies every constraint to 10⁻¹⁵. The quantity a caller checks after a constrained solve is the one quantity here that says nothing.

 where each λ sitsoracle's share0.0037corner's share0.1corner's cost25and what a target costsbest fixed target0.0035its cost1estimate ÷ truth at the oracle0.9210⁻⁸10⁻⁶10⁻⁴10⁻²110⁻³10⁻²10⁻¹110¹10²10³10⁴λnoise part ÷ signal parttarget 0.0035oracle λ: share 0.0037corner: share 0.102solid: the share on this draw · dashed: the share a rule can estimatethe rule is a level set of the dashed curve Regularisation, and the answer that is chosen

A rule that has to be told how good its answer will be

The L-curve's corner reads a noise share of 0.10 to 0.21 across fifteen pairings of signal and penalty, and the share the best λ sits at runs from 0.0037 to 0.43 — a factor of a hundred and fifteen. A rule aimed at the right share is within a few per cent of the oracle on every one of them. The right share is about a third to four-fifths of the relative error that λ will achieve, which is the number the answer was wanted for.

All themes