Motivation
A photograph contains variation at several distances. Two neighboring pixels may differ because they straddle an edge; two large regions may have different average brightness even when each is internally smooth. A representation that records only individual pixels hides this organization. The Haar transform records local averages and differences, then repeats the same operation on the averages. Each number has a definite location and scale, and the image can be recovered exactly before coefficients are discarded.
The word compression can describe two different operations. Changing coordinates in an invertible transform loses no information and does not itself reduce the number of numbers. Approximation begins when some coefficients are removed or quantized. Orthogonality is valuable because it makes the resulting error exactly measurable. The same property also reveals a limitation: an orthogonal transform preserves the total energy of white noise. Denoising requires a structural assumption about the image, rather than a hope that the transform alone eliminates error.
We work with finite arrays of power-of-two size. This restriction avoids padding and boundary ambiguities while making a complete algorithm possible.
Definitions
Definition 4.1.1
(Discrete Haar transform)
For a pair of values define the normalized average and difference
The average is normalized for length preservation; it is not the arithmetic mean. For an even-length vector apply this operation to disjoint adjacent pairs, retaining the average vector and detail vector. If , apply it again only to the average vector, until a single coarse coefficient remains. The ordered collection of that coefficient and every retained detail vector is the discrete Haar transform . We list details from coarse to fine. Other storage orders are possible, but must not be confused with a different mathematical transform.
Synthesis reverses the recursion, using and at each pair. Analysis and synthesis each use a number of arithmetic operations proportional to : the successive vector lengths form a geometric series. The same is true of the storage needed if each level's details are retained once.
For an image matrix of size , a separable full transform is . Equivalently, transform each column and then each row. A common two-dimensional pyramid instead performs one pairwise level in both directions and recursively transforms only its low-low block. At a level, the four blocks encode average-average, average-difference, difference-average, and difference-difference information. Both constructions are orthogonal; their recursive coefficient arrangements differ. The explicit two-by-two examples below coincide for the two constructions.
Definition 4.1.2
(Hard and soft thresholding)
For a coefficient vector , hard thresholding sets coefficients of magnitude at most to zero and retains the others. Soft thresholding uses . We can preserve the coarsest coefficient and threshold only the details; that choice retains the global mean. It must be stated explicitly, since thresholding every coefficient need not preserve brightness.
Theorem/proposition
Theorem 4.1.3
(Orthogonality, exact synthesis, and approximation error)
The finite Haar matrix is orthogonal: . Consequently synthesis is and
Among approximations with at most nonzero coefficients in this fixed basis, a best squared-error approximation retains coefficients of largest magnitude with their original values. Its squared error is the sum of squares of all discarded coefficients. Ties can give several best supports.
Theorem 4.1.4
(White Gaussian noise and a simultaneous threshold bound)
Suppose with independent noise entries distributed as , , and let be any real orthogonal transform. The transformed noise entries are again independent . For any collection of detail-coefficient indices fixed before observing the noisy data, and , setting
gives probability at least that all those noise coefficients have magnitude at most . This does not assert that all observed coefficients exceeding the threshold are signal, or that genuine coefficients below it are absent.
The second result describes a simultaneous noise event. It is not an optimal threshold-selection theorem and does not promise exact image recovery. A small real detail may be removed; a noisy estimate of a real coefficient may be biased. The confidence parameter describes the assumed Gaussian experiment, not certainty about the model itself.
Proof sketch or proof idea
Proof
(Products of orthogonal pair maps, and an exchange argument)
The pair matrix satisfies by direct multiplication. One level is a block diagonal collection of these matrices followed by a permutation, hence is orthogonal. Every later level applies another orthogonal map to the average coordinates and the identity to previously stored details. A product of orthogonal maps is orthogonal, proving exact synthesis and norm preservation. The two-dimensional claim follows by applying this argument to rows and columns, or by using the Frobenius norm identity for multiplication by an orthogonal matrix.
For a fixed retained support, squared error separates into one scalar term per coordinate. Each retained value is best set equal to its original coefficient, leaving the energy of the omitted entries. If a selected coefficient has smaller magnitude than an omitted one, exchanging them cannot increase error and strictly decreases it when their squared magnitudes differ. Repeating exchanges proves the largest-coefficient rule. This is optimality within one fixed orthogonal basis, not among every conceivable image representation.
Orthogonality is what removes the cross terms between discarded directions, so a proposed approximation can be scored by adding omitted coefficient energies without reconstructing the image. For a redundant or nonorthogonal system this identity generally fails, and the appropriate synthesis operator and stability bounds are needed instead. The second theorem also rests on orthogonality, now applied to a probability density.
Counterexample mode
Largest coefficients need an orthogonal basis
Claim: in any basis, keeping the largest coefficients is best, and the error equals the energy of the discarded ones. In take , and . Keeping the larger coefficient gives , with squared error , not the predicted . Keeping instead gives error , and discarding both gives error . Without orthogonality the cross terms remain, so coefficient magnitudes no longer score approximations; the hypothesis is the repair.
Proof
(Rotation invariance of the Gaussian density and a union bound)
The noise density is proportional to . An orthogonal change of coordinates preserves both squared norm and absolute Jacobian determinant, so the transformed density has the same factorized Gaussian form. This proves independence as well as equal variances; equal variance alone would not establish independence for general non-Gaussian noise.
For a scalar standard normal , its moment-generating function gives for by choosing the exponential parameter equal to . Apply the same bound to , then take a union bound over the coefficients. The resulting upper bound is . Independence is not needed for this last union-bound step, though it was part of the preceding distribution result.
Proof X-ray
Which hypothesis each step of the noise bound uses
The bound has three ingredients, and each hypothesis is used at exactly one of them. Orthogonality of enters through the density: and leave the factorized Gaussian form unchanged. Gaussianity is what upgrades the statement “uncorrelated with equal variances”, which any orthogonal map gives for white noise of finite variance, to “independent ”. The tail estimate uses only that each transformed coordinate is , through its moment-generating function with the exponential parameter chosen equal to .
The union bound is the step that sets the threshold, and it needs no independence at all: the probability that some coefficient exceeds is at most the sum of the marginal probabilities. This is why grows only like . The requirement that the indices be fixed before the data are seen is used here as well. If the collection were chosen after looking, for example as the coefficients with the largest observed values, the event would no longer be a fixed union of marginal events, and the calculation would not apply.
Worked examples
Worked example 4.1.5
(A complete four-pixel transform)
For , first-level averages are and details are . Transforming the averages gives coarse average and coarse detail . Thus our coefficient order is . Its squared norm is , matching . Keeping only the two coarse coefficients reconstructs . The squared error is four, exactly the energy of the discarded fine details. The coarse approximation replaces each pair by its arithmetic mean even though the stored average coefficients themselves use square-root normalization.
Worked example 4.1.6
(An explicit two-dimensional image)
Take . Applying the pair matrix in both directions gives
The top-left coefficient is the sum of all pixels divided by two. Its relation to the mean is therefore six versus three. The upper-right coefficient compares columns and the lower-left compares rows under our convention. Preserve the coarse coefficient and soft-threshold the other three with . The result is and . The mean stays three and the squared error is eight. Reversing row and column naming would not change the calculation, but would mislabel the directional details.
Worked example 4.1.7
(A probabilistic threshold is not a signal detector with certainty)
Suppose , , and . The stated bound gives . With probability at least , all eight transformed noise entries lie inside that interval. If a true detail is two and its noise is zero, thresholding removes it despite this favorable event. Conversely, a large observed coefficient can contain both signal and noise. The event controls the noise simultaneously; it does not label each observed coefficient as true or false. Soft thresholding a retained detail also subtracts the threshold from its magnitude, introducing deliberate shrinkage.
Soft thresholding is the unique scalar minimizer of . Splitting into positive, negative, and zero cases gives the stated formula, with a subgradient interval handling zero. Coordinatewise application therefore solves the coefficient-domain separable penalized problem. Because the transform is orthogonal, transforming back gives the corresponding image minimizer with an penalty on its coefficients. If only details are penalized, the coarse coordinate is left unchanged.
Concept lensAnalytic
Energy preservation and denoising are different statements
For a vector of length with independent noise of variance , the expected total squared norm is before and after an orthogonal transform; for an image it is . Denoising becomes possible when the signal occupies a relatively small or structured collection of coefficients, allowing other coefficients to be suppressed. The benefit comes from that image structure and the decision rule, not from a reduction of noise energy during the invertible coordinate change.
Common mistakes
Counterexample mode
A shift need not shift the coefficients neatly
The vector has zero finest-scale Haar differences. Its one-pixel circular shift has two nonzero finest differences. Thus the decimated transform is not translation invariant, even though both transforms preserve energy and reconstruct exactly. A location change can redistribute coefficients across scales. Using an undecimated construction can improve shift behavior but introduces redundancy and changes the exact approximation identities.
Hard thresholding is discontinuous at the threshold: moving a coefficient from just below to just above it can create a finite output jump. Soft thresholding is continuous and nonexpansive, since its piecewise linear slope lies between zero and one. Neither property supplies a complete statistical risk comparison.
Common mistake
(Reading the coarse coefficient as the mean brightness)
The normalized average is times the arithmetic mean of the pair, and the factor compounds across levels: a vector of length has coarse coefficient times its mean. For the coarse coefficient is while the mean is ; for the two-by-two image above it is while the mean is . A display that rescales the coarse image for brightness should work on a copy and must not overwrite the stored normalized coefficients.
Common mistake
(Treating uncorrelated noise as independent)
White noise with covariance keeps covariance under an orthogonal transform, so its coefficients stay uncorrelated. They need not stay independent. If are independent and equal to with probability each, the pair coefficients and are uncorrelated, yet in every outcome exactly one of them is zero. The independence statement in the noise theorem uses the Gaussian density. The union-bound step survives correlation, provided each coefficient still satisfies the Gaussian tail bound.
Common mistake
(Testing exact reconstruction after a lossy step)
Boundary extension, unequal dimensions, quantization and coefficient ordering must be documented in software. An exact reconstruction check should use unmodified coefficients before any thresholding or quantization; otherwise an indexing error can be mistaken for intended approximation error.
Summary
Finite Haar analysis is an orthogonal recursive algorithm with exact synthesis and linear arithmetic cost. Separable row-column analysis extends it to image arrays, while recursive low-low analysis gives a multilevel image pyramid. Orthogonality converts approximation error into discarded coefficient energy and preserves Gaussian white-noise distribution. Thresholding introduces a model-based lossy decision, with explicit stability, bias, and detection limitations.
Exercises
Exercise 4.1.8
(Transform in the stated coarse-to-fine order. Keep the coarse coefficient alone and calculate the reconstruction and squared error.)
Foundation
Solution(3)
- 1
Compute the first level
The pairs and give averages and details .
- 2
Compute the coarse level
The averages give coarse average and coarse detail , so the coefficients are .
- 3
Reconstruct and measure the error
Keeping only the coarse value gives first-level averages and then . The squared error is , equal to the two omitted squared details; the zero coarse detail contributes nothing.
Exercise 4.1.9
(For a two-by-two constant image with every entry equal to , compute every coefficient. Explain the normalization relating the coarse coefficient to mean brightness.)
Foundation
Solution(2)
- 1
Compute the coefficients
Here : every difference vanishes, and the coarse coefficient is the pixel sum divided by .
- 2
Relate it to the mean
Orthogonality requires the squared norm to match four pixels of value . The coarse coefficient is twice the mean here. For an image the normalized constant basis image has entries , so the fully coarse coefficient is times the mean.
Exercise 4.1.10
(Prove soft thresholding is nonexpansive on the real line. Deduce that orthogonal analysis, coordinatewise soft thresholding with fixed thresholds, and synthesis together are nonexpansive in Euclidean norm.)
CoreProof
Solution(3)
- 1
Use the piecewise structure
On each of the three intervals separated by and , is nondecreasing with slope or , and the pieces join continuously.
- 2
Compare two arguments
Key step
For , split at any breakpoints it contains. On each piece the output increases by between zero and the input increase, so .
- 3
Pass to vectors
∎Squaring the scalar inequality for each coordinate and summing gives . Analysis and synthesis are orthogonal and preserve the norms on both sides, so the composition is nonexpansive.
Exercise 4.1.11
(If , and , write the simultaneous threshold exactly. Explain what changes in the probability proof when transformed errors are correlated but each still satisfies the same scalar Gaussian tail bound.)
Core
Solution(3)
- 1
Evaluate the threshold
.
- 2
Examine the union bound
The union bound uses only the marginal tail of each coefficient, so correlation does not invalidate it. For a single coefficient there is no dependence to discuss.
- 3
State what is lost
For a larger collection with the same marginal tails, the same simultaneous bound holds even with dependence. What is lost is the separate claim that the transformed coefficients are independent, which needs the orthogonal Gaussian setting.