Motivation
A captured image may be sharp in some regions and blurred by motion or defocus in others. Sharpening is an inference problem: the observed pixels alone need not determine the original scene, and a small measurement error can become a large reconstruction error. A matrix model lets us separate a known forward process from the assumptions used to reverse it.
This unit uses small grayscale examples in linear intensity and is not a complete imaging pipeline. Geometric warping and HDR acquisition in the earlier units address different parts of the imaging process; here we study inversion of a specified blur.
Forward blur and identifiability
Definition 2.1.1
(A linear observation model)
Let be an unknown image, a known blur and sampling operator, and the measurement with error . A candidate reconstruction has data residual . The residual measures consistency with this model, not necessarily error from the unknown .
When has a nonzero null vector , images and give the same noiseless observation. No algorithm using only can distinguish them without additional information. Even if is invertible, a small singular value means some image variations are weakly observed: reversing their attenuation magnifies error. The operator must include a boundary convention, sampling and units; an inaccurate forward model can make a seemingly precise answer unreliable.
Counterexample mode
Equal observations can hide different images
Let . Both and produce . Their difference lies in the null space. Thus zero residual does not identify the original image; a reconstruction rule can choose one solution but cannot recover information absent from the measurement.
Quadratic regularization
Theorem 2.1.2
(A unique regularized estimate)
For a fixed , observation and , minimize
The unique minimizer satisfies
Proof
(Positive definiteness and completing the square)
Put . For every nonzero vector ,
so is positive definite, even if is singular. In particular forces and hence , so is invertible and the normal equation has exactly one solution.
Expanding and using gives, for every ,
The last term is strictly positive for . Hence is the unique global minimizer, and any minimizer must satisfy the normal equation.
Proof X-ray
Why the penalty makes the system invertible
The hypothesis is used in exactly one place: to turn the merely nonnegative quantity into a strictly positive quadratic form. Without it, is singular whenever has a null vector, the normal equation has a whole line or plane of solutions, and the minimizer is not unique; the matrix of the previous counterexample is such a case.
The one non-obvious move is the identity . It replaces a calculus argument by an algebraic one: the cross term cancels because solves the normal equation, so no second-derivative test is needed. The argument closes because a positive definite form vanishes only at . Uniqueness is a property of this objective, not necessarily of the unknown physical image.
A large favors small norm more strongly and can remove real contrast; too little regularization can amplify noise. Other penalties express different assumptions, such as a preference for smoothness or sparse gradients. If the penalty is , uniqueness requires ; a gradient penalty has a nontrivial null space, so its mere presence is not enough. Nonnegative or bounded pixel values require an explicitly constrained problem; the unconstrained formula does not enforce them.
Concept lensAlgebraic
Regularization as an enlarged least-squares system
Stack the data and the penalty: . This is an ordinary least-squares problem whose normal equation is exactly . Its coefficient matrix has trivial null space for every , because forces . The penalty is thus extra equations asserting that is near , weighted by .
Common mistake
(A smoothness penalty does not by itself give uniqueness)
Take and the difference penalty . Both and the penalty depend only on , so and have exactly the same cost. The minimizer is not unique because , so . The penalty must act on the directions that cannot see.
Two-pixel blur worked out
Worked example 2.1.3
(Inversion and a regularized answer)
Take
The equal-value direction has eigenvalue , while the difference direction has eigenvalue . The exact inverse gives : it fits perfectly but has a negative pixel. With ,
so the regularized solution is . The penalty has reduced the contrast but has not guaranteed nonnegative values. If is perturbed by , the unregularized inverse changes by : the difference-mode error doubles.
Worked example 2.1.4
(The same estimate mode by mode)
Because is symmetric, use the orthonormal vectors and , with eigenvalues and . For the coordinates are . The regularized estimate multiplies each coordinate by ; with these factors are and . Therefore
in agreement with the matrix computation. The mode with the smaller response is amplified by instead of the unregularized factor , which is why the difference-mode noise grows less.
Worked example 2.1.5
(A singular blur: the penalty picks the shortest solution)
For and , every image fits exactly. Here and , so the normal equation is
By symmetry with , that is . As this tends to , the exact solution of smallest norm (norm , against for ). The penalty chooses among indistinguishable images; it does not recover the true one.
Common mistake
(Choosing the penalty by the smallest residual)
The residual cannot choose . For the two-pixel blur with the noisy measurement , the exact inverse has residual , yet it is away from the noise-free reconstruction . Taking always shrinks the residual, so minimizing it alone selects the least regularized, most noise-sensitive estimate.
Frequency interpretation and assumptions
On a finite periodic grid, a spatially invariant circular blur is diagonal in the discrete Fourier basis. With transform , write . The diagonal entries are the blur response under the chosen transform convention. Inverting divides by only where it is nonzero; a zero response removes that frequency, and a small response can strongly magnify noise. Circular boundaries are part of this claim: cropping, spatially varying blur and a different edge rule need a different operator.
Proposition 2.1.6
(Regularized estimate in the frequency domain)
Let be unitary, with complex entries , and . Write and for the transforms of the minimizer of and of the data. Then, frequency by frequency,
Proof
(Diagonalizing the normal equations)
The normal equations are with . Since , we get . Multiplying the equation on the left by gives . Each diagonal entry is positive, so dividing coordinatewise gives the stated formula.
The conjugate appears because the adjoint of a complex multiplier is multiplication by . The denominator is positive even when , but the corresponding estimate then comes from the penalty and is zero; it is not recovered data. For a real image, consistent conjugate-symmetric transform conventions return a real reconstruction up to numerical rounding.
Choosing and assessing a model
A held-out measurement, a known noise bound or a documented choice of prior can help choose ; a visually pleasing image alone does not establish accuracy. Compare the predicted observation with , inspect sensitivity to and the boundary model, and record whether intensity constraints were imposed. A residual much smaller than the expected noise level can indicate fitting noise, but it is not by itself a proof of overfitting. If the blur kernel is unknown, estimating it and the image together is a different, generally more ambiguous problem.
Exercises
Quick check
(For the two-pixel blur above, compute and explain the effect of an inverse on a measurement error of .)
The vector is the difference direction.
Solution · Answer
. Inversion doubles this mode, changing the stated measurement error to .
Quick check
(For the same and , verify that solves the normal equations when . Is it a nonnegative image?)
Multiply the matrix by the vector.
Solution · Answer
Multiplication gives . The second component is negative; nonnegativity was not part of the objective.
Quick check
(In the unitary frequency formula, what is the estimate when ? Why does it not prove that the true frequency coefficient was zero?)
Substitute into the formula.
Solution · Answer
The formula gives . The observation contains no contribution from that mode, so the zero is selected by the penalty; the true coefficient could have been different.
Exercise 2.1.7
(Let and . Describe all exact solutions and find the minimizer of for .)
Core
Solution(3)
- 1
Describe the exact solutions
equals exactly when , with free. All exact solutions are for arbitrary .
- 2
Write the objective in coordinates
which separates into a function of and the term .
- 3
Minimize each coordinate
Setting that derivative to zero gives . The unique minimum is .
Because: The term is minimal only at , and the part is a strictly convex quadratic with derivative .
Further study
Blind deblurring, nonquadratic priors, constrained optimization, nonuniform noise and physical sensor models require additional analysis. This unit does not supply a production deblurring implementation or guarantee that its assumptions hold for a particular photograph.