Where the answer stops being in the data

The previous essay establishes that the answer to an ill-posed problem is a choice, and that both standard methods make it by weighting the terms of one sum. It does not say where the weight should fall.

There is one quantity that answers that from the data alone — no knowledge of the true signal, no knowledge of the noise level, nothing but A and b. It is the discrete Picard condition, and it is the only thing in this field that is a measurement rather than a heuristic.

It also does not give the right answer, and the amount by which it is wrong is consistent enough to be a finding rather than an error.

The condition #

The filtered solution is Σₖ fₖ (uₖᵀb/σₖ) vₖ, so every term is a coefficient divided by a singular value. For that sum to mean anything, the coefficients have to fall faster than the singular values — otherwise the later terms grow without bound and the sum is dominated by whatever is smallest.

That is the Picard condition, and for an exact right-hand side it holds. Measured on the noise-free b: the ratio |uₖᵀb|/σₖ over the range where σ is above rounding spans less than four orders of magnitude across the whole spectrum, which is a bounded sum. The problem has a solution and the sum computes it.

Add noise and the picture changes in a specific place. The noise is not smooth — it has no reason to concentrate in the leading singular directions, and it does not — so its coefficients are roughly equal in every direction, at about ‖e‖/√n each. The signal’s coefficients fall exponentially. So below some index the coefficient is no longer the signal’s; it is the noise’s, and it stops falling.

Measured with 0.1% noise on 64 points:

At k = 20 the exact and noisy coefficients agree to two figures — the signal dominates there. By k = 34 the exact coefficient has fallen to 6.8·10⁻⁷ and the noisy one is 2.5·10⁻⁴, a factor of 370 apart: everything being measured at that index is noise. And the last column is the term’s own contribution to the sum, |uₖᵀb|/σₖ, which is 0.14 at the top and 31.3 at k = 38.

That last number is the whole problem in one figure. The term at k = 38 contributes thirty-one times more to the answer than the term at k = 20, and every part of it is noise.

Finding the crossing, and one way that does not work #

The crossing has to be located without knowing which coefficients are the signal’s, so it is found as the minimum of the smoothed coefficient curve: below the noise floor the curve cannot fall further, so its minimum is where the floor begins.

The smoothing is over a window of four either side and it is not decoration. A single |uₖᵀb| can be small by accident — the coefficient of a component the signal happens not to contain — and a crossing detected on one term is a crossing detected on an accident.

The first version used the obvious rule instead: the first index at which the smoothed curve stops falling. It returned 6 at every noise level from 1% to 0.001%.

A detector that is perfectly stable across four orders of magnitude of the thing it is supposed to be detecting is not a detector. What it had found was a shoulder in the signal’s own coefficient curve, at k ≈ 5, where the two smooth bumps stop contributing and the step takes over — a real feature of the signal and nothing to do with noise. The argmin has no such failure mode, because the floor is genuinely the smallest the curve gets.

That is worth recording because the failure looked like success. Six is a plausible truncation for this problem, the number came out of a defensible-looking rule, and only running the rule at four noise levels showed it measuring the wrong thing.

And it overshoots #

Now the finding. Measured at four noise levels, against the truncation that actually minimises the error — knowable only because the problem was constructed:

The crossing is later than the best truncation at every level. Not once, not by a random amount — by four to eleven indices, always in the same direction.

Which is right, and is obvious once measured and not before. The crossing marks where the data stops carrying signal at all. The last few components before it carry signal and noise in comparable amounts, and a component whose signal-to-noise is near one contributes more error than information to the sum — because the contribution is divided by σ, and σ down there is small enough to make a modest error into a large one.

So there are two boundaries and they are different indices:

The boundary of the information, which is the crossing, and which the data knows. The boundary of the usefulness, which is earlier, and which the data does not know.

A rule of thumb that finds the first and stops there has found something real and has answered a different question.

The floor is the noise, checked #

The crossing is only a measurement of the noise if the level it sits at is the noise level, so that is asserted rather than assumed. The noise is spread roughly equally over 64 directions, so each coefficient of it should be about ‖e‖/√n, and the smoothed coefficient at the crossing should be within an order of magnitude of that.

It is, at all four noise levels. Which is the check that distinguishes this detector from the one it replaced: the shoulder-finder returned 6 at every noise level and the coefficient there had nothing to do with ‖e‖.

What the exact right-hand side is for #

Three separate things in this essay need a b with no noise in it, and none of them could be done with measured data.

Establishing that the condition holds at all. Without the exact coefficients there is no way to say that the flattening is the noise rather than the problem — a right-hand side that violated the Picard condition before any noise was added would be an inconsistent system, and would look identical from the data.

Locating the true crossing. The gap of four to eleven indices is between two things, and one of them requires the answer.

And refusing a right-hand side that is pure noise. assertTheRegularisationAssertionsReject feeds the Picard machinery a random vector and requires it to report no usable crossing. A right-hand side that satisfies nothing must not be reported as satisfying something, and a detector that finds a crossing in noise would find one anywhere.

This is exact ground truth doing what it does elsewhere on this site — the Hilbert matrix’s rational inverse, the discrete Laplacian’s closed-form spectrum, the Toeplitz family’s tridiagonal inverse. What is unusual here is that the constructed problem is not a convenience: the entire field is about a quantity nobody has, and without one problem where somebody does, there would be nothing to say.

What this says about numerical rank #

Rank is a decision establishes that a floating-point matrix does not have a rank, that a numerical rank is a decision about a gap, and that the gap is worth printing beside it.

This field is the case where there is no gap, and the Picard picture is what replaces it. A matrix with a rank has a cliff in its singular values and a threshold anywhere in the cliff gives the same answer. A matrix like this one has no cliff, and what decides the truncation is not the matrix at all — it is the right-hand side, through the coefficients uₖᵀb, and the noise in it.

Which is a genuinely different statement. The rank of a matrix, however decided, is a property of the matrix. The right truncation here changes with the noise level of the data, on the same matrix: 21 at 1% and 38 at 0.001%. Two people with the same operator and differently-measured data should truncate differently, and neither of them is looking at a rank.

The two boundaries, as a signal-to-noise statement #

The gap has a clean reading and it is worth having, because “the crossing overshoots” sounds like a defect in the detector rather than a fact about the problem.

Term k contributes (uₖᵀb/σₖ)vₖ to the answer. Split the coefficient into its signal part sₖ and its noise part eₖ, and the term contributes sₖ/σₖ of signal and eₖ/σₖ of error. Keeping the term is worth doing when the first is larger than the second, which is when

|sₖ|  >  |eₖ|

— a comparison that has nothing to do with σₖ, since it divides both. So the right truncation is where the signal’s own coefficient falls below the noise’s.

The crossing, by contrast, is where the total coefficient stops falling, which happens when the noise part starts to dominate the total — that is, when |eₖ| exceeds |sₖ| by enough to flatten the curve. Detecting a flattening needs the noise to be several times the signal, not merely equal to it, and the difference between “equal” and “several times” is the four to eleven indices in the table.

Both boundaries are therefore about the same crossing of the same two quantities, measured with different sensitivity. One is available and blunt; the other is sharp and requires knowing sₖ, which is knowing the answer.

Where this leaves the practical advice #

Three positions are defensible and the field takes the third.

Use the crossing. It is computable, it is a genuine measurement, and it costs a factor of about 1.15 in error on this problem at 0.1% noise. That is not nothing and it is not much.

Correct it by a fixed amount. Subtract five, say. The gaps are +11, +4, +8, +7 — consistent in direction and not in size — so a fixed correction is right on average and wrong at every individual noise level, and there is no reason to expect the average to transfer to another problem.

Or use the crossing as a bound and choose inside it by some other rule. Which is what any real code does, and is why the next essay exists: the crossing says where the search should stop and something else has to say where inside it to land.

The essay reports the bias rather than subtracting it, for the reason this collection reports the looseness of the conjugate gradient bound and the 5.43× slack in the randomised one rather than tuning either. A correction fitted on one problem is a fact about that problem wearing the clothes of a method.

Why the crossing moves and the singular values do not #

One more reading of the table, because it is the sentence a practitioner needs.

The singular values are fixed. They are a property of the blur, they do not depend on what was measured, and they are the same at every row of the table. What moves across those rows is the noise floor, and it moves because the measurement got better.

So the number of usable components is not a property of the instrument’s optics. It is a property of the optics and the exposure, and buying two more digits of measurement precision buys about six more usable singular directions here — 32 at 0.1% noise and 45 at 0.001%.

That is the practical content of the Picard picture and it is why it is worth plotting even though it overshoots. A reader who sees σ falling exponentially and concludes that the problem is hopeless has read half of it; the other half is |uₖᵀb|, and where those two curves separate is a decision that was made when the data was collected rather than when the solve was written.

The gate this field does not have #

Worth being explicit about a limitation, because the site’s habit is to state where a claim was checked.

Every number in this essay is measured on one problem: one blur width, one signal, one noise distribution, one seed. The seeds are fixed so the figures are byte-identical on every build, which is this collection’s rule everywhere — but a fixed seed is not the same as a claim about typical behaviour, and the randomised field is the site’s standing reminder that one draw is an anecdote.

The overshoot’s direction is argued from the mechanism above and would hold on any problem where the noise is spread evenly over the singular directions. Its size — four to eleven indices — is a measurement on this problem, and nothing here establishes that it transfers. acrossSeeds exists in this site’s library and this field does not use it, which is a shortfall recorded rather than concealed.

What the figure draws that the table cannot #

Three curves on one pair of axes, and the arrangement is the argument.

Plotted alone, the singular values are a straight line on a logarithmic axis falling to rounding — alarming and uninformative, since every ill-posed problem’s do. Plotted alone, the noisy coefficients are a curve that falls and then flattens, which could be anything.

Plotted together with the exact coefficients between them, the picture says the thing no single curve does: the exact coefficients fall faster than σ and the noisy ones do not, and the index where the second stops tracking the first is the index where the problem stops being solvable. Two of those three curves are unavailable in practice and the figure needs all three, which is the whole reason this field’s problem is constructed rather than measured.

The two vertical lines are the essay. One is where the data says to stop; one is where stopping is actually best. Everything between them is a component that can be resolved and should not be kept.

What is left #

Choosing λ rather than K, which is the next essay. The Picard crossing is a truncation index; Tikhonov’s parameter is continuous, and the three published rules for choosing it use different information and get different answers.

Correcting the overshoot. The gap of four to eleven is consistent in direction and not in size, and nothing here turns it into a rule. A correction would have to know how the signal’s coefficients decay relative to the noise’s, which is most of the way to knowing the answer — so the honest position is that the crossing is a bound rather than an estimate, and the essay reports the bias rather than subtracting it.

And correlated noise. Everything above assumes the noise is spread equally over the singular directions, which is what makes the floor flat. Noise with structure — a systematic instrument error, a drift — concentrates in particular directions and does not produce a flat floor at all, so the crossing is not a crossing and the whole detector has nothing to detect. That is the realistic case and it is not measured here.