Wavelet transforms and nonlinear approximation

For any real $u,v$, the two outputs of one Haar pair satisfy $((u+v)\mathrm{/}\sqrt{2}{)}^2+((u-v)\mathrm{/}\sqrt{2}{)}^2=u^2+v^2$ by expansion and cancellation of the cross terms. Thus the pair map has matrix $2^{-1\mathrm{/}2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$ whose transpose times itself is the identity; applying it to disjoint coordinate pairs preserves the squared Euclidean norm.

At stage $r$, the approximation coordinates are replaced by their pair-map outputs, with the second outputs recorded as $d^{(r)}$ and the first outputs passed to stage $r+1$. Therefore the map from the original vector to all stored stage outputs is a composition of the orthogonal pair maps and a coordinate permutation. It is orthogonal; hence its transpose is its inverse and it preserves squared norm.

Fix row types $a,b\in \{h,g\}$ and row indices $k,\mathrm{\ell }\in \{0,\dots ,N\mathrm{/}2-1\}$. A coordinate can contribute to both rows only when $2k+j\equiv 2\mathrm{\ell }+r(\mathrm{m}\mathrm{o}\mathrm{d}N)$ for taps $j,r\in \{0,\dots ,L-1\}$. Hence the row inner product is the sum of $a_j{b}_r$ over such pairs. The difference $j-r$ lies in $[-L+1,L-1]$, whose width is $2L-2<N$; so at most one representative of the congruence class modulo $N$ occurs. Since $N$ and $2(\mathrm{\ell }-k)$ are even, that representative, when present, is $2s$ for an integer $s$. The inner product is therefore the filter correlation ${\sum }_j{a}_j{b}_{j-2s}$, which equals $1$ exactly for the same filter and $s=0$, and equals $0$ otherwise by [F1]. In the same-filter case $s=0$ forces $k=\mathrm{\ell }$, because $k,\mathrm{\ell }$ lie in a complete residue system modulo $N\mathrm{/}2$. Thus the $N$ rows are orthonormal.

A square real matrix with orthonormal rows satisfies $W{W}^T=I_N$; hence it is invertible with inverse $W^T$, so also $W^{T}W=I_N$. It follows that $\mathrm{\parallel }Wx{\mathrm{\parallel }}_2^2=x^T{W}^{T}Wx=\mathrm{\parallel }x{\mathrm{\parallel }}_2^2$. A multilevel transform is a composition of these one-level orthogonal maps and coordinate permutations; composing their transposes in reverse order gives its inverse and preserves norm.

Write $r=\sqrt{3}$. Direct addition gives $\sum h_j=8\mathrm{/}(4\sqrt{2})=\sqrt{2}$. The numerator of $\sum g_j$ is $(1-r)-(3-r)+(3+r)-(1+r)=0$, and the numerator of $\sum j{g}_j$ is $-(3-r)+2(3+r)-3(1+r)=0$. Thus $g$ has the required zero sum and two vanishing moments.

With denominator $32$, the numerator of $\sum h_j^2$ is $(4+2r)+(12+6r)+(12-6r)+(4-2r)=32$, so the zero-shift autocorrelation is $1$. The only possible nonzero even-shift autocorrelation of a four-tap filter is at shift $2$ or $-2$; at shift $2$ its numerator is $(3-r)(1+r)+(1-r)(3+r)=2r-2r=0$, and the shift $-2$ sum is the same by reindexing. Reversal with alternating signs gives $\sum g_j^2=1$ and $\sum g_j{g}_{j-2}=h_3{h}_1+h_2{h}_0=0$.

For the cross-correlation ${\sum }_j{h}_j{g}_{j-2s}$, only $s=-1,0,1$ can have overlapping taps. These sums are respectively $h_0{g}_2+h_1{g}_3=h_0{h}_1-h_1{h}_0=0$, $h_0{g}_0+h_1{g}_1+h_2{g}_2+h_3{g}_3=0$ by pairwise cancellation, and $h_2{g}_0+h_3{g}_1=h_2{h}_3-h_3{h}_2=0$. For all other integers $s$ the supports do not overlap, so the sum is zero. Together with steps 1.1 and 1.2 this verifies every condition in [F2].

Fix one cell $I$ of length $h$ and put ${\bar{f}}_I=h^{-1}{\int }_{I}f$. Expanding both sides gives ${\int }_I\mathrm{\mid }f(x)-{\bar{f}}_I{\mathrm{\mid }}^{2}dx=\frac{1}{2h}{\int }_I{\int }_I\mathrm{\mid }f(x)-f(y){\mathrm{\mid }}^{2}dydx,$ because each side equals ${\int }_I{f}^2-h^{-1}({\int }_{I}f{)}^2$.

For $x,y\in I$, [F3] and [F2] give $\mathrm{\mid }f(x)-f(y)\mathrm{\mid }\le M_1\mathrm{\mid }x-y\mathrm{\mid }\le M_{1}h$. Hence the double integral in step 1.1 is at most $h^2{M}_1^2\cdot h^2$, so ${\int }_I\mathrm{\mid }f-{\bar{f}}_I{\mathrm{\mid }}^2\le h^3{M}_1^2\mathrm{/}2$.

There are $1\mathrm{/}h$ cells with disjoint interiors. Summing their squared errors gives $\mathrm{\parallel }f-P_{J}f{\mathrm{\parallel }}_2^2\le h^2{M}_1^2\mathrm{/}2$. Taking nonnegative square roots proves the stated bound.

Since $U^{T}U=I_N$, $x=U^{T}c$. Orthogonality gives $\mathrm{\parallel }x-U^T{P}_{S}c{\mathrm{\parallel }}_2^2=\mathrm{\parallel }{U}^T(c-P_{S}c){\mathrm{\parallel }}_2^2=\mathrm{\parallel }c-P_{S}c{\mathrm{\parallel }}_2^2={\sum }_{i\mathrm{\notin }S}\mathrm{\mid }{c}_i{\mathrm{\mid }}^2\mathrm{.}$ This proves the exact discarded-tail identity.

Minimizing the tail is equivalent to maximizing ${\sum }_{i\in S}\mathrm{\mid }{c}_i{\mathrm{\mid }}^2$ among sets with at most $m$ indices. A maximizing set can include no zero coefficient while omitting a nonzero one; and if it includes $j$ while omitting $i$ with $\mathrm{\mid }{c}_i\mathrm{\mid }>\mathrm{\mid }{c}_j\mathrm{\mid }$, replacing $j$ by $i$ strictly increases that sum. Since the index set is finite, a maximizing set exists, and every set of $m$ largest absolute coefficients is maximizing; when fewer than $m$ coefficients are nonzero, adding zero coordinates changes no error. By [F2], $H_m$ is one such set, proving optimality including ties and the endpoints $m=0,N$.

Since $x=Vc$, the retained approximation is $V{P}_{S}c$, so the residual is $V(c-P_{S}c)=V{P}_{S^c}c$.

Apply [F1] to $z=P_{S^c}c$. By [F2], $\mathrm{\parallel }{P}_{S^c}c{\mathrm{\parallel }}_2^2={\sum }_{i\mathrm{\notin }S}\mathrm{\mid }{c}_i{\mathrm{\mid }}^2$. This gives both inequalities. If $S$ is the full index set, both sides are zero; if $S$ is empty, the same calculation uses $z=c$.

Since $s>0$, $p<2$, and [F1] gives ${\sum }_{n=1}^N\mathrm{\mid }{c}_n{\mathrm{\mid }}^p=\mathrm{\parallel }c{\mathrm{\parallel }}_{b_{p,p}^s(J)}^p$. Arrange the absolute coefficients in nonincreasing order $b_1\ge \cdots \ge b_N\ge 0$. For each $n$, $n{b}_n^p\le {\sum }_{r=1}^n{b}_r^p\le \mathrm{\parallel }c{\mathrm{\parallel }}_{b_{p,p}^s(J)}^p$, so $b_n^2\le \mathrm{\parallel }c{\mathrm{\parallel }}_{b_{p,p}^s(J)}^2{n}^{-2\mathrm{/}p}$.

By [F2], the squared best m-term error is ${\sum }_{n=m+1}^N{b}_n^2$. Because $2\mathrm{/}p>1$, the decreasing function $t^{-2\mathrm{/}p}$ satisfies ${\sum }_{n=m+1}^N{n}^{-2\mathrm{/}p}\le {\int }_m^{\mathrm{\infty }}{t}^{-2\mathrm{/}p}dt=\frac{p}{2-p}{m}^{1-2\mathrm{/}p}\mathrm{.}$ Combining this with step 1.1 and taking square roots gives a factor $m^{1\mathrm{/}2-1\mathrm{/}p}=m^{-s}$, since $1\mathrm{/}p=s+1\mathrm{/}2$. When $m=N$, the actual error is zero by retaining every coefficient, so the bound still holds.

Expanding the recursion shows that the detail row at stage $\mathrm{\ell }$, translated to its first input index, has taps at indices $t=2^{\mathrm{\ell }-1}r+{\sum }_{v=1}^{\mathrm{\ell }-1}{2}^{v-1}{s}_v$, where each of $r,s_1,\dots ,s_{\mathrm{\ell }-1}$ ranges over $\{0,1,2,3\}$; each tuple contributes $g_r{\prod }_{v=1}^{\mathrm{\ell }-1}{h}_{s_v}$ at that index, and the effective coefficient at $t$ is the sum of these products over all tuples with that index. This follows by substituting the low-pass sum at each earlier stage into the current high-pass sum. The largest such index is $3(2^{\mathrm{\ell }}-1)$, so the row is supported in at most $3(2^{\mathrm{\ell }}-1)+1$ consecutive locations. Because $\mathrm{\ell }\le J-2$, this number is $3\cdot 2^{\mathrm{\ell }}-2\le 3\cdot 2^{J-2}-2<N$, so the locations are distinct modulo $N$.

Regard the effective taps in step 1.1 before reducing their input positions modulo $N$. A low-pass stage maps an affine input sequence $p(n)=\alpha +\beta n$ to an affine sequence: ${\sum }_{s=0}^3{h}_{s}p(2k+s)=2\beta k\sum h_s+\alpha \sum h_s+\beta \sum s{h}_s$, which is affine in $k$. Repeating this argument keeps the coarse sequence affine. The next high-pass stage applied to an affine sequence $A+Bk$ gives $A\sum g_s+B(2k\sum g_s+\sum s{g}_s)=0$ by [F2]. Therefore the effective detail tap row has zero sum and zero first moment. After summing all tuple contributions at each lifted location, periodic reduction assigns the resulting effective coefficients to residues. Step 1.1 confines these locations to one interval of fewer than $N$ consecutive integers, so reduction modulo $N$ is injective on that interval and the row lifts back to the same interval.

By [F3], each row of the full multilevel analysis matrix has squared Euclidean norm $1$. If its support has $S$ locations with coefficients $z_1,\dots ,z_S$, then $({\sum }_{i=1}^S\mathrm{\mid }{z}_i\mathrm{\mid }{)}^2\le S{\sum }_{i=1}^S\mathrm{\mid }{z}_i{\mathrm{\mid }}^2=S$, since $S{\sum }_i\mathrm{\mid }{z}_i{\mathrm{\mid }}^2-({\sum }_i\mathrm{\mid }{z}_i\mathrm{\mid }{)}^2={\sum }_{i<j}(\mathrm{\mid }{z}_i\mathrm{\mid }-\mathrm{\mid }{z}_j\mathrm{\mid }{)}^2\ge 0$. Hence its ${\mathrm{\ell }}^1$ norm is at most $\sqrt{S}$. The detail block at stage $\mathrm{\ell }$ has the length of the current approximation after downsampling, namely $N\mathrm{/}{2}^{\mathrm{\ell }}=2^{J-\mathrm{\ell }}$ rows. This and the affine cancellation from step 2.1 establish every clause of the Statement.

Fix a detail row at stage $\mathrm{\ell }$ and lift its fewer-than-$N$ periodic support to a consecutive interval of integer indices. Periodicity makes the wrapped samples equal to $f(n\mathrm{/}N)$ at these lifted indices. Let $c$ be the midpoint of the support interval in physical coordinates. Its length is at most $3\cdot 2^{\mathrm{\ell }}\mathrm{/}N=3\cdot 2^{-j}$, so every support point is within $3\cdot 2^{-j}$ of $c$. The row's affine cancellation from [F1] removes the degree-one Taylor polynomial of $f$ at $c$ from the coefficient sum.

By [F3], each remaining Taylor remainder is bounded by $\frac{1}{2}{M}_2(3\cdot 2^{-j}{)}^2$. The row coefficient is the sum of these remainders weighted by $2^{-J\mathrm{/}2}$ times the detail-row entries. Using the ${\mathrm{\ell }}^1$ bound $\sqrt{3\cdot 2^{\mathrm{\ell }}}$ from [F1] gives $\mathrm{\mid }{d}_{j,k}\mathrm{\mid }\le 2^{-J\mathrm{/}2}\sqrt{3\cdot 2^{\mathrm{\ell }}}\frac{9M_2}{2}{2}^{-2j}=\frac{9\sqrt{3}}{2}{M}_2{2}^{-j\mathrm{/}2}{2}^{-2j},$ because $\mathrm{\ell }=J-j$. This is the asserted estimate.

Here $1\mathrm{/}p=s+1\mathrm{/}2$, so the coefficient norm's scale weight is $1$ by [F4]. Orthogonality [F3] gives $\mathrm{\parallel }x{\mathrm{\parallel }}_2^2=N^{-1}{\sum }_{n=0}^{N-1}\mathrm{\mid }f(n\mathrm{/}N){\mathrm{\mid }}^2\le M_0^2$, and therefore each of the four coarse coefficients has magnitude at most $M_0$.

At scale $j$, [F1] and [F2] imply ${\sum }_{k=0}^{2^j-1}\mathrm{\mid }{d}_{j,k}{\mathrm{\mid }}^p\le 2^j(9\sqrt{3}{M}_2\mathrm{/}2{)}^p{2}^{-5jp\mathrm{/}2}=(9\sqrt{3}{M}_2\mathrm{/}2{)}^p{2}^{-jp(2-s)},$ because $1-p(5\mathrm{/}2)=-p(2-s)$. Summing over the finite range $2\le j\le J-1$ and bounding by the infinite geometric series gives the first displayed estimate. Its ratio is $2^{-p(2-s)}<1$ since $0<s<2$.

Apply [F5] to the finite orthogonal coefficient vector of $U_{N}x$ and substitute the first bound from step 1.2. This gives the stated best m-term error rate with the declared constant.