Paper V: Filter banks, frame bounds, and lifting

E5 Filter banks, frame bounds, and lifting

On this page · Permalink · Source line 2034

Throughout this section the banks act boundedly on the relevant polyphase \(\ell^2\) spaces. A finite channel analysis bank acts in Fourier coordinates by a matrix \(E(z)\). A synthesis bank acts by a matrix \(R(z)\). The matrices may be square or rectangular. Their entries are Laurent polynomials for finite filters and bounded measurable functions for general stable filters.

Permalink · Source line 2036

Theorem E5.1: Perfect reconstruction criterion

Let \(E(z)\) be an \(M\) by \(N\) analysis matrix and let \(R(z)\) be an \(N\) by \(M\) synthesis matrix. The bank reconstructs every input with a delay of \(d\) coarse channel samples, equivalent to \(Nd\) original samples in the one dimensional \(N\)-phase convention, exactly if and only if

\[ R(z)E(z)=z^{-d}I_N \]

for almost every point on the unit circle. A nonzero scalar factor gives exact reconstruction up to gain and delay.

Read proof · Read statement and proof side by side · Permalink · Source line 2038 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem E5.1

The channel Fourier transform turns analysis followed by synthesis into multiplication by \(R(z)E(z)\). If the matrix identity holds, inverse transformation gives the delayed input. Conversely, if every input is reconstructed with that delay, the difference matrix annihilates every vector valued Fourier datum and must vanish almost everywhere.

Back to statement · Read statement and proof side by side · Permalink · Source line 2046 · Claim record · Lean coverage · Code · Worked examples

Theorem E5.2: Quantitative imperfect reconstruction

Define the delay compensated defect

\[ D({\mathrm e}^{{\mathrm i}\omega}) = {\mathrm e}^{{\mathrm i} d\omega}R({\mathrm e}^{{\mathrm i}\omega})E({\mathrm e}^{{\mathrm i}\omega})-I_N. \]

\[ \varepsilon_{\mathrm{rec}} = {\operatorname*{ess\,sup}}_{\omega}\|D({\mathrm e}^{{\mathrm i}\omega})\|_{\mathrm{op}}<\infty, \]

then the delay compensated reconstruction \(\widetilde x\) satisfies

\[ \|\widetilde x-x\|_2 \leq \varepsilon_{\mathrm{rec}}\|x\|_2. \]

The constant is sharp as an operator norm.

Read proof · Visual guide: A positive singular-value gap survives perturbation · Read statement and proof side by side · Permalink · Source line 2050 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem E5.2

In polyphase Fourier coordinates, the error is \(D({\mathrm e}^{{\mathrm i}\omega}){\boldsymbol{X}}({\mathrm e}^{{\mathrm i}\omega})\). Pointwise multiplication and Plancherel's theorem give the upper bound. The operator norm of a measurable matrix multiplier is its essential supremum, which proves sharpness.

Back to statement · Read statement and proof side by side · Permalink · Source line 2072 · Claim record · Lean coverage · Code · Worked examples

Example E5.3: A reconstruction certificate

Suppose a two channel bank has delay compensated defect

\[ D({\mathrm e}^{{\mathrm i}\omega}) = \begin{pmatrix} 0.01\cos\omega&0\\ 0&0.02\sin\omega \end{pmatrix}. \]

Then

\[ {\operatorname*{ess\,sup}}_\omega\|D({\mathrm e}^{{\mathrm i}\omega})\|_{\mathrm{op}} =0.02. \]

Every input therefore has relative reconstruction error at most two percent in \(\ell^2\). The estimate is independent of the input length.

Permalink · Source line 2076

Theorem E5.4: Stability under filter perturbation

Assume \(RE=z^{-d}I_N\). Let

\[ \widetilde E=E+\Delta E, \qquad \widetilde R=R+\Delta R. \]

Set

\[ \begin{aligned} e_0&={\operatorname*{ess\,sup}}\|E\|_{\mathrm{op}}, & r_0&={\operatorname*{ess\,sup}}\|R\|_{\mathrm{op}},\\ \delta_E&={\operatorname*{ess\,sup}}\|\Delta E\|_{\mathrm{op}}, & \delta_R&={\operatorname*{ess\,sup}}\|\Delta R\|_{\mathrm{op}}. \end{aligned} \]

Then the delay compensated reconstruction defect obeys

\[ \varepsilon_{\mathrm{rec}} \leq r_0\delta_E+e_0\delta_R+\delta_R\delta_E. \]

Read proof · Read statement and proof side by side · Permalink · Source line 2094 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem E5.4

Expand

\[ \widetilde R\widetilde E-RE = R\Delta E+\Delta R E+\Delta R\Delta E. \]

Take pointwise operator norms, then the essential supremum. Multiplication by the delay factor has unit modulus.

Back to statement · Read statement and proof side by side · Permalink · Source line 2118 · Claim record · Lean coverage · Code · Worked examples

Theorem E5.5: Frame bounds from the polyphase symbol

Assume that

\[ A I_N \leq E({\mathrm e}^{{\mathrm i}\omega})^*E({\mathrm e}^{{\mathrm i}\omega}) \leq B I_N \]

for almost every \(\omega\), where \(0<A\leq B<\infty\). Then the analysis bank satisfies

\[ A\|x\|_2^2 \leq \|{\mathcal A}_E x\|_2^2 \leq B\|x\|_2^2. \]

The pointwise matrix

\[ R_{\rm can}({\mathrm e}^{{\mathrm i}\omega}) = (E^*E)^{-1}E^* \]

is a bounded left inverse and gives the canonical dual synthesis bank.

Read proof · Read statement and proof side by side · Permalink · Source line 2128 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem E5.5

Apply the matrix inequality to the polyphase Fourier vector at every frequency and integrate. Plancherel's theorem gives the frame inequalities. The lower bound makes \(E^*E\) invertible almost everywhere, and direct multiplication gives \(R_{\rm can}E=I_N\). The same spectral bounds show that the canonical dual is bounded.

Back to statement · Read statement and proof side by side · Permalink · Source line 2154 · Claim record · Lean coverage · Code · Worked examples

Corollary E5.6: Coefficient noise under canonical synthesis

Under the hypotheses of Theorem E5.5, suppose the observed coefficient vector is

\[ c={\mathcal A}_Ex+\nu. \]

Canonical synthesis gives

\[ \widehat x=R_{\mathrm{can}}c \]

and

\[ \|\widehat x-x\|_2 \leq \frac1{\sqrt A}\|\nu\|_2. \]

Read proof · Visual guide: A positive singular-value gap survives perturbation · Read statement and proof side by side · Permalink · Source line 2158 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary E5.6

The smallest singular value of \(E\) is at least \(\sqrt A\), so the pointwise norm of its pseudoinverse is at most \(1/\sqrt A\). Apply Plancherel's theorem to \(R_{\mathrm{can}}\nu\).

Back to statement · Read statement and proof side by side · Permalink · Source line 2175 · Claim record · Lean coverage · Code · Worked examples

Theorem E5.7: Perturbation of frame bounds

Under the hypotheses of Theorem E5.5, let \(\widetilde E=E+\Delta E\) and suppose

\[ \delta={\operatorname*{ess\,sup}}_\omega\|\Delta E({\mathrm e}^{{\mathrm i}\omega})\|_{\mathrm{op}}<\sqrt A. \]

Then \(\widetilde E\) is a frame analysis bank with bounds

\[ (\sqrt A-\delta)^2 \quad\text{and}\quad (\sqrt B+\delta)^2. \]

Read proof · Visual guide: A positive singular-value gap survives perturbation · Read statement and proof side by side · Permalink · Source line 2179 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem E5.7

For every vector \(v\),

\[ \|\widetilde Ev\| \geq \|Ev\|-\|\Delta Ev\| \geq (\sqrt A-\delta)\|v\|. \]

The upper bound follows from

\[ \|\widetilde Ev\| \leq (\sqrt B+\delta)\|v\|. \]

Square the inequalities and integrate in frequency.

Back to statement · Read statement and proof side by side · Permalink · Source line 2192 · Claim record · Lean coverage · Code · Worked examples

Remark E5.8

Even when \(E\) is a Laurent polynomial matrix, the canonical dual need not have finite impulse response. Finite support of both analysis and synthesis is an additional algebraic condition.

Permalink · Source line 2210

Corollary E5.9: Paraunitary bank

If \(E(z)^*E(z)=I_N\) on the unit circle, then analysis is an isometry and synthesis may be chosen as \(R(z)=E(z)^*\).

Read proof · Read statement and proof side by side · Permalink · Source line 2214 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary E5.9

Use Theorem E5.5 with \(A=B=1\), then multiply the matrices.

Back to statement · Read statement and proof side by side · Permalink · Source line 2218 · Claim record · Lean coverage · Code · Worked examples

Singular-value bounds for an analysis bank and its perturbation. — Pointwise singular value bounds govern both the original frame and its perturbed analysis bank.

E5.1 Haar analysis

On this page · Permalink · Source line 2229

The Haar matrix is

\[ E_H = \frac1{\sqrt2} \begin{pmatrix} 1&1\\ 1&-1 \end{pmatrix}. \]

For even and odd samples \(e(n)=x(2n)\) and \(o(n)=x(2n+1)\), the low and high coordinates are

\[ a(n)=\frac{e(n)+o(n)}{\sqrt2}, \qquad d(n)=\frac{e(n)-o(n)}{\sqrt2}. \]

Permalink · Source line 2231

Corollary E5.10: Haar reconstruction and energy

The Haar bank reconstructs exactly and

\[ \|x\|_2^2=\|a\|_2^2+\|d\|_2^2. \]

Read proof · Read statement and proof side by side · Permalink · Source line 2248 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary E5.10

The matrix \(E_H\) is unitary.

Back to statement · Read statement and proof side by side · Permalink · Source line 2255 · Claim record · Lean coverage · Code · Worked examples

E5.2 Lifting steps

On this page · Permalink · Source line 2259

Let \(P(z)\) and \(Q(z)\) be Laurent polynomials. Define

\[ L_P(z) = \begin{pmatrix} 1&0\\ P(z)&1 \end{pmatrix}, \qquad U_Q(z) = \begin{pmatrix} 1&Q(z)\\ 0&1 \end{pmatrix}. \]

Permalink · Source line 2261

Theorem E5.11: Exact lifting update

The lifting matrices are invertible with

\[ L_P^{-1}=L_{-P}, \qquad U_Q^{-1}=U_{-Q}. \]

If \(R_0E_0=I\), then every finite product \(V\) of lifting matrices gives another exact bank by

\[ E=VE_0, \qquad R=R_0V^{-1}. \]

Every lifting step has determinant one.

Read proof · Read statement and proof side by side · Permalink · Source line 2278 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem E5.11

Direct multiplication proves the inverse formulas and the determinant statement. The reconstructed product is

\[ RE =R_0V^{-1}VE_0 =R_0E_0 =I. \]

Back to statement · Read statement and proof side by side · Permalink · Source line 2294 · Claim record · Lean coverage · Code · Worked examples

Example E5.12: A two neighbor predict and update transform

Split a sequence into even and odd samples. Define

\[ d(n) =o(n)-\frac{e(n)+e(n+1)}2 \]

and

\[ s(n) =e(n)+\frac{d(n-1)+d(n)}4. \]

The inverse is obtained in reverse order:

\[ e(n) =s(n)-\frac{d(n-1)+d(n)}4, \]

then

\[ o(n) =d(n)+\frac{e(n)+e(n+1)}2. \]

Thus reconstruction is exact over every coefficient field in which two is invertible. This is a standard compactly supported biorthogonal lifting pattern [CohenDaubechiesFeauveau1992], [Sweldens1996], [DaubechiesSweldens1998].

Permalink · Source line 2304

Source and conversion record

Source SHA-256: 5d3c6b2e5709c37ea551eb8fd1d823e5249c5fbc411d36b806241af4df888f36

Unsupported prose commands stop the build. The mathematical expression sequence is checked against the source, with manuscript macros expanded for display.

Conversion records

Read and explore

Proofs and implementation

About this work

Other resources