Conjugate gradients on an ill-posed problem at 1.0% noise
At its defaults it draws conjugate gradients on an ill-posed problem at 1.0% noise. Two curves against the step count on a logarithmic vertical axis. The relative residual falls at every one of the 120 steps without exception. The error against the true signal falls to 0.1426 at step 20 and then climbs, reaching 6.02 by the end — 42.2 times its best value.
semiconvergence-curve is one function in lib/figures/krylovreg.js —
iterative regularisation — a step count as the parameter, and the filter it applies. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
Two curves against the step count on a logarithmic vertical axis. The relative residual falls at every one of the 120 steps without exception. The error against the true signal falls to 0.1426 at step 20 and then climbs, reaching 6.02 by the end — 42.2 times its best value.
precond: "fast", show: "count"
The arguments are the ones A count that marks the edge and not the pace passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Median over 12 draws of the effective dimension a truncated preconditioned run's best iterate carries per step, against the number of directions its preconditioner divides, for three Gaussian blurs of width 1.5, 2.5 and 4 grid points. Each curve starts at zero directions, the unpreconditioned run, and stops at the first cutoff where fewer than half the run lands on the unpreconditioned run's arc, which is ringed. The narrow blur leaves the arc at 33 directions and a stride of 5.71, the collection's blur at 22 and 3.44, the wide blur at 15 and 2.41. The answers' own effective dimensions are 32.2, 23.2 and 14.7.
precond: "fast", show: "arcs"
The arguments are the ones A count that marks the edge and not the pace passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The relative error of each iterate of conjugate gradients with no preconditioner, on a logarithmic vertical axis, against the effective dimension the iterate carries, for Gaussian blurs of width 1.5, 2.5 and 4 grid points on one draw of the noise, each drawn up to its own best step. The narrow blur's run ends at 33.1 after 17 steps at an error of 0.0968; the middle one at 24.0 after 20 steps at 0.1426; the wide one at 12.8 after 11 steps at 0.1566.
precond: "fast", show: "countarc"
The arguments are the ones A count that marks the edge and not the pace passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Six curves, for Gaussian blurs of width 1.5, 2.5 and 4 grid points at 1% and 0.1% noise, each a median over 12 draws. Across: the number of directions a truncated preconditioner divides, divided by the effective dimension of the unpreconditioned run's best iterate. Up: the share of the preconditioned run's iterates, up to its own best, that land on the unpreconditioned run's arc. The six arcs run from 14.7 to 45.2 in effective dimension. Every curve first falls below one half between 0.95 and 1.03 on this axis.
precond: "fast", show: "multiple"
The arguments are the ones A count that marks the edge and not the pace passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
For three Gaussian blurs of width 1.5, 2.5 and 4 grid points: the best error a truncated preconditioned run reaches divided by the unpreconditioned run's best on the same draw, worst over 24 draws, against the multiple of the discrepancy principle's own λ at which the cutoff is set, on logarithmic axes. At half that λ the worst draw is 1.181 times the floor, on the narrow blur. At λ itself the worst draw on any of the three is 1.063 times it. The median step at which the halved and the unhalved runs are best is 5 against 6, 7 against 8.5, 6 against 7 on the three blurs.
precond: "fast", show: "multiple", noise: 0.001
The arguments are the ones A count that marks the edge and not the pace passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
For three Gaussian blurs of width 1.5, 2.5 and 4 grid points: the best error a truncated preconditioned run reaches divided by the unpreconditioned run's best on the same draw, worst over 24 draws, against the multiple of the discrepancy principle's own λ at which the cutoff is set, on logarithmic axes. At half that λ the worst draw is 1.082 times the floor, on the narrow blur. At λ itself the worst draw on any of the three is 1.035 times it. The median step at which the halved and the unhalved runs are best is 8.5 against 13, 12 against 15, 10 against 8.5 on the three blurs.
What it checked while drawing
Every figure above checked its own claims on the way to being drawn, and a claim that failed
would have stopped the picture rather than shipped a wrong one. Those checks used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
394 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
the residual does not rise at step 1 — checked 120 times
and fall with the singular value at index 1 — checked 63 times
the iterate is the stable closed form to rounding at step 1 — checked 39 times
below λ² the best iterate is the first, at α = 0.0001 — checked 6 times
the rule separates the constructions at σ = 1.5, 0.01 — checked 6 times
the three edges separate at σ = 1.5, 0.01 — checked 6 times
the σ = 1.5, 0.01 edge is where the count reaches the answer — checked 6 times
Tikhonov's noise exceeds the iteration's at σ = 1.5, 0.01 — checked 6 times
and the error that step can reach rises, at α = 0.00001 — checked 5 times
and the σ = 1.5 blur leaves it where the count reaches the arc's top — checked 3 times
at σ = 1.5 the unhalved cutoff's worst draw is near the floor — checked 3 times
on σ = 1.5 the shifted mismatch grows as the shift falls — checked 3 times
the completion's rises at offset 2 — checked 3 times
the σ = 1.5 run leaves the arc inside the sweep — checked 3 times
a blur width the count is compared across
a blur width the family is compared on
a blur width the filters are compared on
a blur width the rule is compared across
a blur width the shift is compared across
a blur width these runs are measured on
a comparison of filters this figure draws
a coordinate the filters are compared in
a cutoff far below the rule's λ costs the answer
a fraction of the answer the iterate is taken at
a fraction of the answer's dimension to compare at
a fraction the family is compared at
a Landweber run short enough to execute step by step
a Landweber view this figure draws
a multiple of λ the cutoff could be
a narrower blur supports an answer of more effective dimension
a noise level small enough to be noise
a noise level the fast-transform runs are calibrated over
a noise level the problems are drawn at
a noise level the six problems are measured at
a number of draws the dense sweeps are affordable at
a preconditioner view this figure draws
a run long enough for the slowest of the three to turn
a run long enough to see both curves turn
a run long enough to see the curve turn
a sharpness at least Tikhonov's
a sharpness the family is drawn at
a shift that is a shift
a shifted approximation does not beat the plain run
a size the dense products are affordable at
a size the dense reference solve is affordable at
a size the dense SVD is affordable at
a size the SVD-applied preconditioner is affordable at
a smoothing view this figure draws
a transform the blur is approximated on
a truncated run that reaches the floor reaches it sooner
a truncation level below the largest eigenvalue
a truncation level the spectrum is drawn at
a truncation level the stop is drawn at
a view of the fast-transform preconditioner this figure draws
a way of making the approximation invertible
a λ rule the cutoff is read off
above the edge nearly every iterate lands on the arc
an offset the comparison is drawn at
and above it the preconditioned run reaches the plain run's floor
and at the smallest τ the run's own best has walked away
and below it most of the run misses it
and below the oracle's λ² the best iterate is the first
and each run has a window of good steps
and even Landweber's error has turned by ten million steps
and far above it does not
and is the worse of the two as a λ rule on the median draw
and Landweber needs at least as many steps to reach it
and Landweber sits within a quarter of Tikhonov at the matched λ everywhere
and less bias on every problem
and past the edge the best iterate carries more dimension than the arc holds
and pushes the largest eigenvalue less far
and running past the minimum costs a real factor
and stays within 10% of it over at least as wide a ratio of steps
and the better of the two as a cutoff rule on the worst
and the completion loses to it
and the cosine run's edge sits below the oracle's λ, within a factor of four
and the cutoff below the edge strides further still
and the fast shift well before it
and the first step's residual never reaches the noise at any cutoff tried
and the L-curve's below it
and the narrow blur's answer carries nearly twice the wide one's
at a half the discrepancy principle's cutoff is above the edge
at a longer stride
at the edge τ the rule stops nearer its run's best than on the plain run
at the fast shift's edge its error at the ends is more than twice the exact shift's
at the same best error
at the top Tikhonov carries more noise than the iteration on every problem
because the coefficients bottom out well down the ordering
because the preconditioner has largely stopped preconditioning
enough draws for a median
enough draws for a median and a worst case
enough draws for a median of medians
enough draws for a worst case
enough draws for a worst case to mean something
enough noise for the stopping step to matter
enough shifts to show where the best step reaches one
enough steps for the error to turn and keep rising
Jacobi needs a symmetric matrix
Landweber's factors are weights, inside [0, 1]
near the top every problem's ratio is within eight per cent of one
no shift of the cosine approximation beats the plain run
offsets wide enough to show a trend
past its edge the fast shift fails far worse than either of the others
past the end of the arc, where the answer is not
several shifts below the oracle's λ²
some truncation keeps the run's best near the plain floor
the badge fits between the two Landweber curves
the best ωk agrees across the step lengths
the CGLS description leaves rounding inside the run
the cosine approximation differs from A by more than 10⁻³ only near its ends
the discrepancy principle chooses λ above the oracle's
the error has an interior minimum
the exact shift leaves the arc near the answer's dimension
the first preconditioned step is the Tikhonov solution at λ² = α, scaled
the fourier approximation differs from A by more than 10⁻³ only near its ends
the general form's best λ is inside the grid it is searched on
the plain run's error turns inside the run
the printed form of the filter has drifted by the last step
the reading places the cutoff far below anything that works
the rule stops somewhere on both runs
the run well above the edge is on the plain run's arc
the split beats the plain run once there is an offset
the split's best error is flat in the offset
the stride rises with the cutoff
the three blurs leave the arc at different strides
the three rules' cutoffs are ordered as their λ are
the two iterations reach the same best error to within 2%
truncated, the cosine approximation reaches the plain floor
truncated, the fourier approximation reaches the plain floor
truncation leaves more directions below 10⁻³ than the shift
which costs its run a real factor
while between the ends the two agree
while conjugate gradients' description has expired by step 40
while the CGLS factors at their own best step go above one
while the rule stays nearer its run than the run stays to Tikhonov
whose window is narrower
Against the rule
It draws a decomposition and prints its residual. It calls
cgls,
and every figure above carries the badge — which residualcheck verifies by looking
for it in the emitted SVG rather than by finding the call that builds one. A badge that is
constructed and then left out of the body is the failure that check exists for.
Across the library: the rule bites on 217
of 397 generators —
199 print a residual and
18 are exempt with a published reason;
180 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
A count that marks the edge and not the pace
The number of directions a truncated preconditioner divides is counted for free when it is built, and it was proposed as a stand-in for the stride it buys. On three blurs it is not one — the runs leave the answer at strides of 5.71, 3.44 and 2.41. What the count does predict is the edge: on all three blurs, at two noise levels, a run stops landing on the answer's path within five per cent of the point where the count reaches the answer's own effective dimension. And the halved cutoff rule, measured on one blur, crosses that line on the narrowest.
Methods that were designed apartA parameter that counts steps
The regularisation field's knob is a positive real number chosen by one of three rules. The iterative field's is an integer nobody called a knob — where to stop. On the same problem the best step is 20 and the best λ is 0.025, and they reach 0.1426 and 0.1406.
Methods that were designed apartA preconditioner that arrives past the answer
On a system that is solved to convergence a preconditioner changes how fast the answer arrives and not what it is. On a problem regularised by stopping it changes where every step lands. Conjugate gradients preconditioned by AᵀA + αI reaches its best answer in one step at α = 10⁻³, and at α = 10⁻⁶ its best answer is its first step, with an error of 1.35 against the unpreconditioned run's 0.1426 — while the count of eigenvalues it has clustered at one rises from 22 to 32.
Methods that were designed apartA step that is not a unit of work
Landweber's iteration reaches conjugate gradients' best answer on the same deconvolution — 0.1414 against 0.1426 — at step 1,778 instead of step 20, and at 0.1% noise at step 56,234 instead of 44. Each step costs the same two products. And within 10% of its best it runs from step 7 to step 6,310, where conjugate gradients runs from 4 to 26: the slow method is the one that forgives a late stop.
Methods that were designed apartA 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.
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.
Methods that were designed apartAn expiry date the noise does not move
The polynomial description of conjugate gradients leaves the level of rounding at step 17 or 18 on this operator, at every noise level from 10% to 0.1%. The step worth stopping at moves from 3 to 44 across the same range. They coincide at about 1% noise, which is where the coincidence was first read, and it is a fact about the noise rather than about the method.
Methods that were designed apartOne arc, and what each filter pays to be on it
Conjugate gradients and Tikhonov stop at the same effective dimension, and that could have meant two curves crossing once or one curve. It is one curve over a stretch — on six problems, Tikhonov and truncation reach the iteration's error at the iteration's dimension to within 7.2 per cent from 0.7 of the answer to its top — and the two separate on either side. But the curve is shared by a trade, not by an identical answer: at the same dimension Tikhonov carries 22 to 42 per cent more noise than the iteration and up to five per cent less bias.
Methods that were designed apartThe overshoot was the lead
Past its best, conjugate gradients' error rose more slowly than Tikhonov's at the same effective dimension — on the narrow blur at 0.1% noise Tikhonov was 2.35 times worse at 1.3 of the answer — and the reading was that the iteration spends its dimension where the data has content. Count admitted directions instead of summing factors, so that a factor of 1.81 counts once, and the lead is gone: 0.96 on that problem, and within 0.17 of one on all six from 1.1 to 1.3. Tikhonov now carries less noise than the iteration there. Below half the answer, where the three filters also disagree, the count changes nothing.
Methods that were designed apartThe parameter neither knob is
A preconditioned run has a cutoff and a step count, and neither is the regularisation parameter. The parameter is the effective dimension of the iterate: every cutoff that works puts its own best at 23.7 to 24.3 of it, where the unpreconditioned run's best sits at 23.2, and what the cutoff buys is the rate — 1.27 of it a step with no preconditioner and 3.53 with one. The edge is where a single stride is longer than the distance left.
Methods that were designed apartThe rule that is wrong in the right direction
The preconditioner's cutoff is not a new parameter. It is the regularisation parameter this field already knows how to choose, halved — and the rule criticised for choosing λ a factor of two or three too large is the one whose cutoff keeps the floor on every draw, where the rule that chooses λ to within 3% has a worst draw two hundred times off it.
Methods that were designed apartThe shift had an edge, and the approximation moved it
A fast-transform preconditioner made invertible by a shift was recorded as never reaching the unpreconditioned floor, and predicted to sit off the answer's path at every shift. At a large shift it sits on the path and reaches the floor to a tenth of a per cent. It has an edge like the truncated one — but on the exact operator that edge is where the shift's own effective dimension reaches the answer's, 1.02 to 1.05 of it on six problems, and on the fast approximation it arrives at 0.49 to 0.77. The difference is sixteen samples at the ends of the signal, where the approximation is wrong and a shift divides the error by α.
Two errors, and whose fault they areThe zero you are allowed to write
A deflation criterion sets a subdiagonal entry to zero because it is small. A drop tolerance discards an entry of a factor because it is small. A truncation discards a singular value because it is small. Three fields, three vocabularies, no shared arithmetic — and plotted as work saved against error accepted, one curve.
Methods that were designed apartWhat a cheap preconditioner has to leave alone
A blur approximated by a matrix the cosine transform diagonalises agrees with the operator everywhere but its first and last seven rows. Made invertible by a shift, as the exact preconditioner was, it never reaches the unpreconditioned run's floor — at α = 10⁻³ its best iterate is 0.749 against 0.143. Made invertible by leaving every eigenvalue below τ alone, it reaches 0.141 in five steps instead of twenty, and the smallest τ that keeps the floor sits at a third to a half of the Tikhonov oracle's λ at three noise levels.
Regularisation, and the answer that is chosenWhere the answer stops being in the data
The Picard condition finds the index where a noisy right-hand side stops carrying signal, from the data alone, with no knowledge of the answer. It lands at 32 where the truncation that actually minimises the error is 28 — and at 45 where the best is 38. It overshoots at every stop from 10% noise to 0.0001%, and it overshoots for a reason. The best truncation walks up the spectrum in a straight line, six or seven indices a decade; the crossing climbs in jumps of 11, 0, 8, 5 and 1.