Motivation
A blurred photograph is not simply an original image with some details erased at random. A measurement device mixes nearby intensities, then introduces noise. Restoration asks which image could have produced the measurement. The forward calculation is often easy; reversing it can amplify a small measurement error into a large oscillation. We therefore need to distinguish an algebraic inverse from a stable reconstruction rule.
This note develops a finite-dimensional model. Periodic boundaries make its spectral structure exact and transparent. They do not assert that real photographs wrap around at their edges. Before applying the model to data, one must decide how boundaries, sampling, and the noise distribution should be represented. The calculations here explain a mathematical mechanism rather than prescribe a universal imaging pipeline.
The key question is what happens to each independently observable direction. Fourier coordinates answer this for translation-invariant blur. Haar coordinates provide a different organization: a global average together with localized differences. Neither change of coordinates creates information missing from the observation. Their usefulness comes from exposing where the data are reliable and where an additional modeling assumption enters.
Definitions
Represent a one-dimensional image by , with indices interpreted modulo . Two-dimensional images use the same definitions in each coordinate. Let be a blur kernel and define circular convolution by
Here is the observed image and is an unknown error. If and , the blur preserves constant images and replaces each intensity by a weighted average. These assumptions describe a useful class of kernels, but the algebra below needs only the stated convolution formula. Negative intensities may appear in intermediate linear calculations even when the physical signal is nonnegative.
The unitary discrete Fourier transform is
Its inverse uses the positive exponential with the same factor. Define the transfer function . Notice that is the unnormalized transform of the kernel: this convention makes . The transform preserves the Euclidean norm, so spatial error and spectral error have the same total squared magnitude. Real images have conjugate-symmetric Fourier coefficients.
For , quadratic Tikhonov restoration minimizes
The first term measures agreement with the data. The second penalizes large reconstructed energy. Its use is a modeling choice, not a consequence of the measurement equation. A derivative penalty instead uses , where . Its nullspace consists of constants, so it treats overall brightness differently from oscillation.
Theorem/proposition
Theorem 1.1.1
(Fourier diagonalization and the obstruction to inversion)
Circular convolution satisfies . It is invertible exactly when every is nonzero. In that case an observation perturbation obeys
and the bound is attained in a Fourier direction of smallest transfer magnitude.
Theorem 1.1.2
(Quadratic regularization is uniquely solvable and stable)
For any real matrix , any , and , has the unique minimizer
For circular convolution its Fourier coefficients are
The map from data to minimizer has Euclidean operator norm at most .
The final bound measures sensitivity to changes in data for fixed . It does not bound the reconstruction's error relative to an unknown true image. Choosing a large parameter reduces sensitivity but may also suppress genuine image structure. Accuracy requires discussing both noise and the approximation introduced by the penalty.
If an error estimate is available, a useful diagnostic compares the residual with that scale. A residual far below the expected measurement error can indicate fitting noise, while a much larger residual can indicate excessive regularization or an inaccurate forward model. This diagnostic does not uniquely determine the parameter without further assumptions. In particular, a noise bound gives no bound on an invisible component of the true image. When comparing reconstructions, record both the parameter and the resulting residual, and check whether image structures persist across a reasonable parameter range. Parameter sensitivity is part of the result, rather than an inconvenience to hide after selecting a visually attractive image. The noise estimate itself should come from the measurement process, not from the desire to justify a particular reconstruction.
Proof sketch or proof idea
Proof
(Diagonalization and the worst direction)
Substitute the convolution formula into the Fourier sum and write :
Periodic indexing lets run through a full period for each fixed . Thus with the unitary transform , so is invertible exactly when every diagonal entry is nonzero, and then . Since preserves norms,
with equality when is supported on an index of smallest . For real data one can use the matching real sine and cosine subspace instead of a complex basis vector.
Proof
(Positive definiteness and the gain bound)
The gradient of is . For every nonzero vector ,
Thus the normal matrix is positive definite, is strictly convex, and the stationary point is the unique global minimum. Diagonalization gives the spectral formula. More generally a singular value of produces a reconstruction gain . The inequality gives , which proves the stability bound, including .
Proof X-ray
Why adding a penalty repairs this inverse
Both proofs reduce a matrix question to scalar ones, and the second differs from the first in exactly one place. Exact inversion divides by ; the regularized rule multiplies by . The essential move is the term , present in every direction: it makes the Hessian positive definite even when has invisible directions, so existence and uniqueness need no assumption on at all. The gain bound then comes from a one-line inequality, , whose equality case is the most amplified mode; very weak modes are not amplified but suppressed. Replacing by a derivative matrix changes the required hypothesis: uniqueness then needs . A smoothness penalty cannot identify a constant image if the measurement also annihilates constants.
To see the bias explicitly in a noiseless Fourier mode, insert . The reconstructed coefficient is . A weakly transmitted component is deliberately attenuated. If , no choice of parameter recovers its unknown value from these data alone. Regularization supplies a selected answer, not a proof that the selected answer was photographed.
A derivative penalty changes the filter so that the average brightness is no longer shrunk, but uniqueness then needs the blur to see constants.
A path to generalization
Penalizing differences instead of intensities
A derivative penalty changes the filter so that the average brightness is no longer shrunk, but uniqueness then needs the blur to see constants.
Replace by . The shift in becomes multiplication by , so has symbol , of squared magnitude , and the minimizer has coefficients
At the penalty vanishes, so the mean is not shrunk; a unique minimizer now requires , the condition that does not annihilate constants. Low frequencies are penalized weakly and high frequencies strongly, rather than all equally.
Worked examples
Worked example 1.1.3
(A blur that loses an alternating pattern)
Take and . Then . At the transfer is zero. The alternating vector is therefore invisible: both it and the zero vector produce zero observations. A constant background can be added to make two distinct nonnegative images with the same data. Positivity alone does not restore uniqueness. This is a failure of identifiability before any numerical algorithm is chosen.
Worked example 1.1.4
(Quantifying amplification and shrinkage)
Suppose a spectral direction has real transfer . A measurement error of becomes an error of under exact inversion. With , the regularized gain is , so the same error becomes . A true coefficient equal to one, observed noiselessly as , is reconstructed as . The reduction in noise amplification has a visible price: half the true coefficient is removed. Reporting only the smaller noise term would hide the bias.
Worked example 1.1.5
(Haar coordinates separate brightness and detail)
For , define and . The inverse is , , and . To keep the average while shrinking detail, minimize for an observed detail . On positive and negative half-lines, differentiation gives the soft-threshold rule . At zero the left and right slopes straddle zero exactly when . With and , the detail halves, producing while preserving the mean.
Repeated Haar pairing applies this construction to adjacent pairs, then to their averages. For a vector of power-of-two length it gives an orthonormal multiscale basis. Fine detail coefficients compare nearby pixels; coarser coefficients compare averages over longer intervals. This makes localized edges more economical than a description using many global sinusoids. It does not mean every image is sparse, and a shifted edge can change many coefficients in a decimated Haar transform.
Concept lensAnalytic
An inverse problem is a collection of scalar decisions
In singular-vector coordinates, each quadratic restoration problem asks how strongly to trust one measured coefficient. Fourier analysis identifies those coordinates explicitly for periodic convolution. Haar analysis instead chooses coordinates in which a structural prior, such as many small local differences, may be plausible. The first diagonalizes the measurement operator; the second can simplify the image model. These are distinct reasons for using a transform.
For derivative Tikhonov restoration, periodic differences have spectral squared magnitude . When is convolution, replace the denominator by . At the constant mode the penalty vanishes. A normalized blur has , so this coefficient remains observable and the joint-nullspace condition holds. If both terms vanish at a mode, the formula is undefined there and the minimizer is not unique; one must state a convention or obtain additional information.
Common mistakes
Counterexample mode
A smaller residual need not mean a better image
Let with , true image zero, and data consisting entirely of noise. Exact inversion has residual zero but error . The zero reconstruction has residual and error zero. A residual measures agreement with observations, including their error; it does not measure agreement with an unavailable ground truth.
The next three mistakes concern the forward model rather than the solver.
Common mistake
(Using the unitary transform of the kernel as the transfer function)
The transfer function is the unnormalized sum . For and , the unitary transform of at is , whereas . Inserting the unitary coefficients would scale every mode by and make a constant-preserving blur appear to halve all intensities.
Common mistake
(Treating a small transfer value like a zero one)
A zero transfer value destroys uniqueness: no parameter recovers that coefficient. A small nonzero value preserves uniqueness but with severe sensitivity, such as the gain at in the amplification example. The two cases need different conclusions: the first is a statement about information, the second about stability.
Common mistake
(Blaming the solver for a wrap-around artifact)
Circular convolution does not justify wrapping a bright right edge around to a dark left edge. With on and , the model predicts : brightness from the right edge appears at the left. If the camera did not see this, the discrepancy is a forward-model error rather than a failure of the reconstruction solver.
The simple quadratic fidelity is appropriate to a particular error geometry. Impulsive errors may call for a different fidelity, and signal-dependent counting noise requires a different likelihood. Nonnegativity constraints, when justified, also change the optimization problem; the unconstrained Fourier formula need not satisfy them. A visually pleasing result is useful evidence for further investigation, but it is not a substitute for checking assumptions and numerical quantities.
Summary
Periodic convolution is diagonal in Fourier coordinates. Vanishing transfer values make information inaccessible, and small values make exact inversion sensitive. Quadratic regularization replaces division by a bounded filter, with an explicit bias. Haar averages and differences offer a complementary multiscale image representation and lead naturally to thresholding. The boundary convention, penalty, and fidelity are parts of the mathematical model and should be reported with the reconstructed image.
Exercises
Exercise 1.1.6
(For a real normalized blur kernel, prove and . Explain why the regularized reconstruction of real data remains real.)
FoundationProof
Solution(3)
- 1
Evaluate at zero frequency
At every exponential equals one, so .
- 2
Conjugate the transfer sum
.
Because: The kernel entries are real.
- 3
Apply the filter to real data
∎Real data satisfy . The filter takes conjugate values at and , so the reconstructed coefficients keep that symmetry and the inverse transform is real. Numerical roundoff may leave negligible imaginary parts, but they are absent in exact arithmetic.
Exercise 1.1.7
(Let and replace the identity penalty by . Find the minimizer of . Then replace by and describe all minimizers.)
Core
Solution(3)
- 1
First penalty
The objective is , minimized only at . The measurement and penalty nullspaces intersect only at zero.
- 2
Second penalty
The objective is , so and is arbitrary.
- 3
Compare
In the second case both operators ignore the second direction; optimization cannot manufacture the missing condition.
Exercise 1.1.8
(A periodic blur has a mode with . For , compute the noiseless shrinkage factor and the magnitude of the reconstruction gain. Distinguish these two quantities.)
Foundation
Solution(3)
- 1
Shrinkage
The noiseless shrinkage is .
- 2
Gain
The gain from observed to reconstructed coefficient has magnitude .
- 3
Distinguish
Shrinkage compares the reconstruction with the true coefficient; gain compares it with the measured coefficient. They differ by the forward transfer factor .
Exercise 1.1.9
(Compute the two-pixel Haar coefficients of . Preserve the average and soft-threshold the detail by . Reconstruct the vector and verify its mean and squared reconstruction error.)
Foundation
Solution(3)
- 1
Transform
.
- 2
Threshold
Soft thresholding gives detail ; the average stays .
- 3
Reconstruct and check
The inverse gives and , so . Both vectors have mean two, and the squared error is . This calculation concerns a specified deterministic vector; it does not by itself establish a statistical risk guarantee.