Motivation
A camera does not observe each pixel separately: its point-spread function mixes intensities before noise is added. The periodic Fourier model makes this mixing particularly transparent, but a real boundary rule or a spatially varying blur may produce a matrix that is not diagonal in Fourier coordinates. We can still study a reconstruction without pretending that all matrices share Fourier eigenvectors.
The identity penalty in the earlier note discourages brightness as well as oscillation. A difference penalty instead expresses a preference for neighboring pixels to agree while leaving a constant image unpenalized. This change is useful, but it has a consequence: the measurement must determine every direction that the penalty ignores. Here we prove exactly when that happens and what can be recovered as the noise level tends to zero. All vectors and matrices below are finite and real; the result is not a continuum convergence theorem.
Definitions
Let be a specified imaging operator, a specified penalty operator, and the data. For set
For example, on a two-pixel image penalizes contrast but not mean brightness. The choice of includes the boundary convention. The choice of is a modeling assumption; its nullspace describes features that this penalty alone cannot distinguish. No positivity constraint is imposed here.
For exact data , call an -minimum solution if and is least among all exact solutions. It is a selected solution, not necessarily the physical image that generated the data.
Theorem/proposition
Theorem 1.4.1
(Existence, uniqueness, and stability with a seminorm penalty)
Assume and . Then has exactly one minimizer
If is the smallest eigenvalue of , data and produce minimizers satisfying
Conversely, if the common kernel contains a nonzero vector, a minimizer exists but is never unique.
Theorem 1.4.2
(The small-noise selection principle)
Under the same common-kernel hypothesis, let . There is exactly one -minimum exact solution . Suppose , and choose so that and as . Then
The hypotheses give a sufficient parameter rule, not a claim that every successful rule must satisfy it.
Both statements can be read through one stacked least-squares problem.
Concept lensAlgebraic
A seminorm penalty is ordinary least squares for a stacked operator
Put and . Then , the normal equation is , which is , and the common-kernel condition is exactly injectivity of , since means and . Uniqueness is therefore the familiar statement that a least-squares problem has one solution precisely when its matrix has independent columns. The constant is the smallest squared singular value of .
Proof sketch or proof idea
Proof
(The normal matrix decides uniqueness and sensitivity)
Write . For every ,
This is positive for every nonzero exactly when the two kernels intersect only at zero. In that case is positive definite, and expanding about gives . Thus the stationary point is the unique global minimum. Subtracting the two normal equations gives , and gives the stated stability bound. It may become large as decreases; fixed-parameter continuity alone does not prove recovery.
If the common kernel is nontrivial, write with . The range of is a closed finite-dimensional subspace. The orthogonal projection of onto that range has a preimage, and any such preimage minimizes the objective. Adding any common-kernel vector leaves its objective unchanged.
Proof
(Selection of the least-penalty exact solution)
First, an exact solution of least -norm exists: minimize the distance from zero to the affine subspace , which is closed in finite dimensions. If two distinct exact solutions have the same least -norm, their midpoint would have strictly smaller squared -norm unless their -images were equal. In the latter case their difference lies in both kernels, so they are equal after all.
Comparing the minimizer with the competitor , for which , yields
Consequently , while the residual tends to zero. The vectors and are bounded. Because the stacked map is injective, there is a constant with : minimize the continuous positive function on the unit sphere. Thus is bounded. Every convergent subsequence has an exact-solution limit whose -norm is at most ; uniqueness forces that limit to be . Boundedness and this unique cluster point imply convergence of the whole family.
Proof X-ray
What makes the limit proof work?
The limit proof uses its two parameter conditions at two different places. The single comparison inequality carries all the information. Its first consequence, residual , needs only ; it gives data consistency of every limit point, but controls nothing in . Its second consequence, , needs , and it does two jobs: it bounds the penalty, and in the limit it shows that a cluster point is no worse than in -norm.
Neither bound alone controls . The common-kernel hypothesis enters first through the coercivity constant , to turn bounded and into bounded ; finite dimension then supplies convergent subsequences. The proof closes by uniqueness of , the second use of the same hypothesis, now applied to two minimum-penalty solutions.
Worked examples
Worked example 1.4.3
(A two-pixel blur and a difference penalty)
Let , , , and . Write . Then and , giving
The first derivative equations give and . The reconstruction is . Exact inversion gives ; the difference penalty keeps the data's mean but deliberately reduces contrast. The reconstructed residual is , whose norm is . It need not be zero even though is invertible.
Worked example 1.4.4
(When the data leave a choice)
Let , and . Every exact solution has . Its least possible difference is zero, so . The kernels are the contrast and constant directions respectively, with zero intersection. For noisy scalar data , the unique regularized minimizer is for every positive : both terms can be made zero at once. If , this tends to . Here convergence holds for any positive parameter choice because both terms can vanish simultaneously; the first example shows that the reconstruction generally depends on the parameter. A physical image also gives exact data four, but this selection principle does not recover it.
Worked example 1.4.5
(A singular blur with a unique reconstruction)
Let , and . Here is singular: it annihilates the contrast direction . But is spanned by , so the kernels meet only at zero and the theorem still gives a unique minimizer. With , and , so
minimized at , : for every . The residual is the contrast of the data, which no image can produce through this .
The normal matrix has eigenvalue on and on , so , and . The stability bound is valid but not sharp here: the actual map is , with norm for every .
Common mistakes
Counterexample mode
A smoothness penalty need not determine brightness
Take and . Both operators annihilate . For every the optimal difference is , but the mean is arbitrary. Thus increasing the penalty cannot repair a direction that both the observations and the penalty ignore. Adding an independent mean measurement or an explicit mean constraint changes the problem and can remove this ambiguity.
The theorem's bounds concern perturbation of with , , and fixed. An incorrectly calibrated blur changes itself and requires a separate error analysis.
Common mistake
(Reading a small penalty as evidence of smoothness)
A small value of is not evidence that the true image is smooth; it records the model's preference. In the example with , the images and give the same exact datum . The reconstruction selects , with , whatever the photographed image was.
Common mistake
(Expecting an invertible blur to be fitted exactly)
With a penalty, does not solve even when is invertible. In the two-pixel example is invertible, yet leaves the residual . The residual is the price of the penalty; in general it disappears only in the limit with exact data.
Summary
Generalized quadratic regularization replaces the identity by a chosen operator . The common-kernel condition is exactly the uniqueness condition, and the normal matrix quantifies fixed-parameter sensitivity. As noise and the parameter vanish at compatible rates, the reconstruction converges to the exact solution with minimum penalty, which need not be the unknown physical image.
Exercises
Exercise 1.4.6
(Let and . Find for data , and explain the residual.)
Foundation
Solution(3)
- 1
Write the objective
.
- 2
Minimize coordinatewise
; the kernels and meet only at zero.
- 3
Explain the residual
The second measured coordinate is always predicted as zero; its residual is and cannot be fitted by any image.
Exercise 1.4.7
(For the two-pixel blur example, compute the minimizer for arbitrary . What happens to its contrast as ?)
Foundation
Solution(2)
- 1
Solve in mean–difference coordinates
The mean remains and , so .
- 2
Take the limit
The contrast tends to zero as . This does not say that the unknown image has zero contrast.
Exercise 1.4.8
(If for , for which real do the selection theorem's two parameter conditions hold?)
Foundation
Solution(3)
- 1
First condition
as requires .
- 2
Second condition
requires .
- 3
Combine
Both hold if and only if . The theorem applies for those values; it does not characterize convergence for values outside this range.
Exercise 1.4.9
(Let , and exact data . Identify the minimum-penalty exact solution and explain why a true image cannot be recovered from the datum alone.)
Core
Solution(3)
- 1
Describe the exact solutions
They are the vectors , with .
- 2
Minimize the penalty
The minimum of is attained uniquely at , so .
- 3
Interpret
All vectors have identical data. The model selects ; the observation provides no evidence that .