E10 Haar localization and annihilating differences
On this page · Permalink · Source line 3183
The adjacent difference detector is local in the sample domain. Wavelet coefficients and higher differences give related multiscale packets. In the Haar subsections the signal is defined on \({\mathbb R}\). Here the step convention is \(H_\tau(t)={\mathbf 1}_{[\tau,\infty)}(t)\), whose restriction to \((0,1)\) agrees with the preceding interval step. A chosen extension beyond the observation interval must use this half-line step convention, and the smooth extension must satisfy the stated Lipschitz hypothesis on every displayed wavelet support.
E10.1 Haar coefficient separation
On this page · Permalink · Source line 3187
Let
and let \(\psi_{j,k}\) be the normalized Haar wavelet supported on \(I_{j,k}\), positive on the left half and negative on the right half.
Theorem E10.1: Smooth Haar coefficient bound
If \(s\) is Lipschitz with constant \(M\), then
Read proof · Visual guide: Haar sees a jump only through its position in the support · Read statement and proof side by side · Permalink · Source line 3197 · Claim record · Lean coverage · Code · Worked examples
Proof of Theorem E10.1
Let \(L=2^{-j}\) and let \(a\) be the left endpoint of the support. Pair every point \(t\in[a,a+L/2]\) with \(t+L/2\). Then
The integrand has magnitude at most \(ML/2\), and the integration interval has length \(L/2\). The result is \(ML^{3/2}/4\).
Back to statement · Read statement and proof side by side · Permalink · Source line 3206 · Claim record · Lean coverage · Code · Worked examples
Theorem E10.2: Exact Haar coefficient of a step
Let \(\tau\in I_{j,k}\), let \(L=2^{-j}\), and write
Then
Every Haar coefficient whose support does not cross \(\tau\) is zero.
Read proof · Visual guide: Haar sees a jump only through its position in the support · Read statement and proof side by side · Permalink · Source line 3218 · Claim record · Lean coverage · Code · Worked examples
Proof of Theorem E10.2
Away from the jump, the step is constant on the support and the Haar wavelet has zero mean. When the jump lies in the support, integrate the positive and negative halves directly. If \(u\leq1/2\), the magnitude is \(|a|uL^{1/2}\). If \(u\geq1/2\), it is \(|a|(1-u)L^{1/2}\).
Back to statement · Read statement and proof side by side · Permalink · Source line 3236 · Claim record · Lean coverage · Code · Worked examples
Corollary E10.3: Scale separation
Suppose \(f=s+aH_\tau+\eta\), where \(s\) is \(M\) Lipschitz and \(\|\eta\|_\infty\leq\varepsilon\). If the jump lies at relative distance at least \(\rho\) from both ends of \(I_{j,k}\), then
A wavelet support without a jump satisfies
Thus a threshold gap exists whenever
Read proof · Visual guide: Haar sees a jump only through its position in the support · Read statement and proof side by side · Permalink · Source line 3240 · Claim record · Lean coverage · Code · Worked examples
Proof of Corollary E10.3
Combine Theorem E10.1 and Theorem E10.2. The noise coefficient is at most
The final inequality makes the lower bound on a jump support larger than the upper bound on a smooth support.
Back to statement · Read statement and proof side by side · Permalink · Source line 3267 · Claim record · Lean coverage · Code · Worked examples
E10.2 Two shifted grids
On this page · Permalink · Source line 3284
A jump on a dyadic boundary can be invisible to a wavelet at that scale. One additional grid removes this exact alignment.
Theorem E10.4: Half cell shift guarantee
Fix a cell length \(L>0\). Consider the grid with boundaries \(kL\) and the grid with boundaries \((k+1/2)L\). Every point \(\tau\in{\mathbb R}\) lies in a cell of at least one grid at distance at least \(L/4\) from both cell boundaries.
Read proof · Visual guide: Two half-shifted grids remove exact alignment failure · Read statement and proof side by side · Permalink · Source line 3288 · Claim record · Lean coverage · Code · Worked examples
Proof of Theorem E10.4
Reduce \(\tau\) modulo \(L\) and write its representative as \(x\in[0,L)\). If
then the distance from \(x\) to both boundaries of its cell in the original grid is at least \(L/4\). If \(x<L/4\) or \(x>3L/4\), then \(x\) lies in the cell of the shifted grid bounded by \(-L/2\) and \(L/2\), or in its translate, at distance at least \(L/4\) from both shifted boundaries. One of the two grids therefore has the required property.
Back to statement · Read statement and proof side by side · Permalink · Source line 3292 · Claim record · Lean coverage · Code · Worked examples
Corollary E10.5: Alignment free two grid Haar detection
Assume the support length \(L\) is smaller than the minimum jump separation. Analyze the signal with Haar wavelets on the original grid and on the half shifted grid. Every jump appears in a support with \(\rho\geq1/4\) in one of the two systems. Therefore a threshold gap exists independently of alignment whenever
Read proof · Visual guide: Two half-shifted grids remove exact alignment failure · Read statement and proof side by side · Permalink · Source line 3300 · Claim record · Lean coverage · Code · Worked examples
Proof of Corollary E10.5
Apply Theorem E10.4 and then Corollary E10.3 with \(\rho=1/4\). The separation assumption prevents a selected support from containing two jumps.
Back to statement · Read statement and proof side by side · Permalink · Source line 3309 · Claim record · Lean coverage · Code · Worked examples
E10.3 Higher differences
On this page · Permalink · Source line 3320
Let
Then
Theorem E10.6: Polynomial annihilation and boundary support
Let \(x\) be a sequence that agrees with a polynomial of degree at most \(d\) on each interval of a finite partition of \({\mathbb Z}\). Then
whenever the complete stencil
lies inside one polynomial piece. Hence \(\Delta^{d+1}x\) is supported in a band of at most \(d+1\) addresses before each breakpoint.
Read proof · Visual guide: Higher differences annihilate polynomial interiors · Read statement and proof side by side · Permalink · Source line 3334 · Claim record · Lean coverage · Code · Worked examples
Proof of Theorem E10.6
The \((d+1)\)st forward difference of a polynomial of degree at most \(d\) is zero. The only stencils for which this argument does not apply are those crossing a breakpoint.
Back to statement · Read statement and proof side by side · Permalink · Source line 3346 · Claim record · Lean coverage · Code · Worked examples
Proposition E10.7: Noise amplification by differences
If \(\|\eta\|_\infty\leq\varepsilon\), then
Therefore no false response above \(2^{d+1}\varepsilon\) can occur on a stencil lying inside one polynomial piece.
Read proof · Visual guide: Higher differences annihilate polynomial interiors · Read statement and proof side by side · Permalink · Source line 3350 · Claim record · Lean coverage · Code · Worked examples
Proof of Proposition E10.7
The absolute values of the binomial coefficients in \(\Delta^m\) sum to \(2^m\).
Back to statement · Read statement and proof side by side · Permalink · Source line 3360 · Claim record · Lean coverage · Code · Worked examples
Corollary E10.8: Robust breakpoint bands
Assume every true breakpoint produces at least one response of magnitude \(\rho\) in its \((d+1)\)st difference band. If
then thresholding at any level between \(2^{d+1}\varepsilon\) and \(\rho-2^{d+1}\varepsilon\) detects a nonempty cluster near every breakpoint and creates no cluster away from the breakpoint bands.
Read proof · Visual guide: Higher differences annihilate polynomial interiors · Read statement and proof side by side · Permalink · Source line 3364 · Claim record · Lean coverage · Code · Worked examples
Proof of Corollary E10.8
Use Theorem E10.6 and Proposition E10.7. Noise cannot cross the threshold away from a breakpoint. At a response of magnitude \(\rho\), the perturbed magnitude remains at least \(\rho-2^{d+1}\varepsilon\), which is above the threshold.
Back to statement · Read statement and proof side by side · Permalink · Source line 3372 · Claim record · Lean coverage · Code · Worked examples