The thread: Two routes to a number — page 8
A conductance the arcs do not measure
Symmetrising a directed Laplacian with respect to its walk recovers everything the arrows took — a real spectrum, a sweep cut, a Cheeger inequality. What it does not recover is the quantity: the inequality bounds the probability that a step of the walk crosses the cut, which on one graph here is three times the weight of the arcs that do.
The eigenvalue problem that is not linearThe number that moves when the problem does
Two quantities are offered as the condition number of one eigenvalue. One is unmoved to eight digits by a change of variable that is exact in both directions, and grows like the square root of the chain's length. The other is inflated by ten orders by that change of variable, and is ten times too large before anything has been done at all.
The arithmetic underneathNine steps of pessimism
A proved bound is 8 to 26 times the error it bounds, at every precision from 16 to 40 significand bits. A carried interval is (√2)ᵐ times too wide after m re-enclosures. The two cross between eight and nine, so the method everybody warns against is the tighter of the two for a short computation.
Neither sparse nor denseA quarter of the leaf
The leaf that stores a hierarchical matrix most cheaply had been read off a table of nine points, with the suggestion that it depends on the mean rank alone. Across six kernels at five tolerances — thirty cells — it does, once the mean rank is read in the right place. Plotted against the mean rank at a fixed leaf of 16, two cells a tenth of a rank apart want leaves of 8 and 16. Plotted against the rank of the blocks a halving would create, one rule — halve the leaf while that rank is below a quarter of the leaf — predicts the best leaf on 28 of the 30, and the two it misses are the two whose rank sits within three per cent of the threshold. The fractional power the last measurement expected to be rough is smoother than 1/r.
Methods that were designed apartA tail from Tikhonov and a corner from truncation
Below half the answer, conjugate gradients beat Tikhonov at a matched count of directions by up to 69 per cent, and the proposed measurement was the sharpness p of a roll-off between Tikhonov and truncation that matches the iteration there. Any p from 2 to 4 closes the gap to a tenth; truncation, the family's limit, reopens it to a third. But no p describes the iteration. Its filter has Tikhonov's slope exactly in its tail and a local sharpness of 2 to 5 on its shoulder, and a single fitted p is a compromise that drifts from 2.3 at the first step to 1.7 at the answer.
Exact arithmetic, and what it costs insteadWhat reading the next pivot buys
In a fraction-free elimination every pivot is paid for twice — it multiplies every entry of its own step and divides every entry of the next — and the rule that picks the smallest pivot entry left a median 20 per cent above the least arithmetic any row order reaches. A rule that charges two steps ahead brings the median matrix to within 2.5 per cent, and on one matrix of twenty-four costs 1.87 times the least, worse than the smallest pivot ever does. Charging three steps ahead finds the least of all 40,320 orders on thirteen matrices and is never more than 27 per cent above it. And none of it pays: choosing that way costs forty to two hundred and sixty times the elimination it chooses.
Eigenvalues, singular values, rankThe vector was what was wanted
Nobody who computes a matrix exponential wants the matrix. They want eᴬᵗb — one vector, the state of a system at a later time. Twenty matrix–vector products get it to sixteen digits on a hundred-by-hundred problem, without ever forming a hundred-by-hundred exponential, and the exponential that does get computed is twenty by twenty.
When the problem arrives againThe step the two rows owe
A sliding least-squares window can start each step's correction from a fresh solve or from the answer it already has. The answer it has is three orders worse on noisy data, because the exact answer moves by most of itself in a step. The proposal was a start that moves too: the previous answer plus the change the entering and leaving rows imply, two triangular solves from the factor the window keeps. Its start lands exactly where one correction of the carried answer lands — the update is that correction, computed from two rows instead of twenty-four — and one correction after it ends 2.9 to 440 times below the fresh start at κ(A) = 3·10⁶, and level with the carried answer when the data agree exactly.
The matrix that is a graphA finer invariant that hears less
The Laplacian spectrum fixes a graph's number of spanning trees and not the group those trees form, so the Smith normal form of the grounded Laplacian is a strictly finer integer invariant — and on the six-vertex pair the spectrum cannot separate, it does: ℤ₁₂ against ℤ₂ ⊕ ℤ₆. Over all 1,022 Laplacian-cospectral pairs of connected graphs on eight vertices it separates 435. The adjacency polynomial, a second spectrum rather than a finer one, separates all of them.
Neither sparse nor denseThe smaller cluster sets the rank
An oscillatory kernel block between two equal clusters needs a rank that grows without limit as they grow. Make the clusters unequal at the same separation ratio and the rank stops following the larger one: a target an eighth long against a source of four needs 8 columns where the square block of side four needs 33, and a target a third long against a source 130 wavelengths long needs 11. What decides the rank is the product of the two lengths over their distance — the Fresnel number, the count optics gives for the waves two apertures can exchange.
Least squares, and the road not to takeThe degree that is safe to overshoot
The rules that choose a Tikhonov parameter miss by factors of millions on one draw in twenty. Transplanted to the degree of a polynomial fit, in a basis orthonormal on the data, the same rules never cost more than 2.7 times the best degree's error in three hundred draws. The reason is the shape of the valley they search: six degrees too few costs from 44 to 16,000 times the best error, forty degrees too many costs about twice it. The one rule with a tail, the discrepancy principle, has its threshold half a standard deviation above the residual it is waiting for.
Randomised, and the guarantee that changes kindA fade made of drops
A one-nonzero sketch's median error fell by about forty per cent for every factor of ten in how far a coherent matrix had been mixed toward an incoherent one, and nothing explained the rate. Followed one draw at a time, no draw fades at that rate. Each holds its coherent error — as large as the singular value of the direction its hash lost — and then drops, within one to three decades of mixing, never faster than one decade of error per decade of mixing. The median's steady slope is where the drops happen to fall. Change the spectrum and they fall elsewhere: at a decay of 0.9 there is no slope, only a cliff.
Regularisation, and the answer that is chosenA third penalty on a flat floor
Two penalties at once were worth three per cent at most, and the explanation offered was that one penalty already does the work — which predicts that a third buys less still and that the best choice sits on a face of the parameter cube. The third buys a median of exactly nothing on all five signals and 0.66% on its best draw. But on twelve draws of forty the best triple does use all three, and on every one of them the nearest point with a penalty switched off is within that same 0.66%. The minimum is not on a face; it is on a floor so flat that where it lands is noise. Choosing the right single penalty is worth a factor of two.
Structure, and the solver that cannot see itWhere one step stops being enough
One step of iterative refinement took the squared Laplacian's circulant-wrap solve to elimination's accuracy at every size, and the account was that each step multiplies the error by the wrap's condition number times the rounding, so one step suffices while that product is small. Raised to higher powers, the band tests the account and half of it holds: each step does contract by about κ(wrap)·u. The other half fails. The fifth power at sixteen points needs three steps with κ(wrap)·u near 10⁻⁶, where the third power at 128 points needs one with thirty times more, because the first solve starts up to a thousand times further from the answer than κ(wrap)·u says.
Where the flop count stopped predicting the timeThe circle between two eigenvalues
A contour count's error is not approximately governed by the nearest eigenvalue; it is exactly one closed-form term per eigenvalue, and summing those terms reproduces the quadrature to a millionth at 1,720 radius and point pairs. Three things follow. The rate is the ratio of the two moduli the circle sits between, not a distance, so two circles 0.2 from their nearest eigenvalue converge three times apart. Ten digits cost about 21 points divided by log₁₀ of that ratio, 71 points with twelve eigenvalues inside and 3,476 with six. And the best circle is not halfway: at the geometric mean of two eigenvalues on one ray their two terms are equal and opposite, and ten digits cost 27 points where the midpoint needs 84.
Methods that were designed apartThe first step's filter, kept for the whole run
Conjugate gradients' first step applies a ramp — Tikhonov's slope up to a corner, then one — and the essay that found it proposed the ramp as a fixed method, predicting that it would match the iteration below half the answer better than any sharpened Tikhonov and lose the match near the answer. The first half holds by more than predicted: 0.044 from the iteration below half, where the best member of the family was 0.106. The second does not: near the answer the ramp is within 0.016, closer than any filter measured. And two numbers read off the iteration's own Ritz values — its tail's slope and its smallest Ritz value — reproduce it past the top as well, where every fixed filter falls ten to seventeen per cent below it.
When the index is a tupleA 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.
Eigenvalues, singular values, rankTwo matrices and one problem
Ax = λBx is what a finite element model, a structural vibration and a constrained optimisation actually produce, and it is not the one-matrix problem with a change of variables. Everybody is told not to form B⁻¹A because it is not symmetric. That is true, the departure from symmetry is about one, and it is not what decides the accuracy.
Elimination, and the swapA curvature direction the factors cannot refine
A direction of negative curvature read from Bunch–Kaufman's factors held 7·10⁻¹⁶ of the curvature that was there, and the bounded rule's held 14 per cent. The prediction was that a few steps of inverse iteration with the same factors would recover it from either. One step leaves both under a thousandth, and two put both on positive curvature, at the eigenvalue nearest zero — because a solve amplifies the smallest eigenvalue in magnitude, not the most negative. What recovers the curvature is the matrix, not its factors: Lanczos from either direction reaches ninety-nine per cent in six to nine products at every coupling, and power iteration from Bunch–Kaufman's direction has not reached a tenth after sixty.
The matrix that is a graphEach spectrum hears the other's pairs
Pairs of graphs with the same Laplacian spectrum share a spanning-tree count, so the critical group could only tell them apart by how that count factors — and did on two pairs in five. Turn the census round, to the 733 pairs of eight-vertex graphs with the same adjacency spectrum, and the tree count is free to differ. It does on 717 of them, by a median of six per cent. The critical group separates exactly those 717 and not one more: on all sixteen pairs whose counts agree, including a non-cyclic one, the two graphs have the same group. And the Laplacian spectrum separates all 733, as the adjacency spectrum separated every Laplacian pair.
Methods that were designed apartA corner chosen without the iteration
The ramp — conjugate gradients' first-step filter kept as a fixed method — matches the iteration's error at the same position, but every comparison placed it at the iterate's position, which needs the iteration. Placed instead by the iteration's own stopping rules, it was predicted to land within the same tenth of its best and earlier. The discrepancy principle does exactly that, earlier on 61 draws of 72 and dearer by a few hundredths on 71. The L-curve finds the ramp's corner as well as Tikhonov's and far better than the iteration's: twice the best on 26 draws against 44, worst 16 against 896. And GCV fails the ramp in a way it never fails the iteration — choosing a solution that discards three quarters of one direction, 696 times its best — until its first minimum from the regularised end is taken, after which the ramp is within a tenth of its best on 64 draws of 72 and never worse than 1.25.
Two errors, and whose fault they areColumns that steer a random start
A condition estimator whose first vector is random cannot be built against, and concentrating the hidden column did not hide it: its own entries steer the first sign vector onto it. Give the steering to other columns — each equal on both rows of every pair the hidden column alternates over — and the random start is fooled after all. The prediction was a factor of one over the square root of the number of steering columns, on a share of seeds that falls as they lose to the hidden column, and the block of two fooled as often. The factor is whatever the builder chooses; the share, at a fixed factor of one half, rises with every column added, from 9 per cent with four to 77 with thirty-four. And the block of two is not fooled as often: it is fooled on the square of the single start's share, and the block of four on its fourth power — independent guesses, which is the one thing that still works.
When the index is a tupleA 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.
Eigenvalues, singular values, rankAn eigenvalue with no value
If the second matrix of a pencil is singular then some of the eigenvalues are infinite, and that is not a degeneracy — it is the algebraic constraints of the model, one per constraint. What survives is a pair of numbers rather than one, and on the line those pairs live on, infinity is an ordinary point with an ordinary residual.