Polyphase matrix

From Wikipedia, the free encyclopedia

In signal processing, a polyphase matrix is a matrix whose elements are filter masks. It represents a filter bank as it is used in sub-band coders alias discrete wavelet transforms. [1]

If h,g are two filters, then one level the traditional wavelet transform maps an input signal a0 to two output signals a1,d1, each of the half length:

a_1 = (h\cdot a_0) \downarrow 2
d_1 = (g\cdot a_0) \downarrow 2

Note, that the dot means polynomial multiplication, i.e. convolution and \downarrow means downsampling.

If the above formula is implemented directly, you will compute values that are subsequently flushed by the down-sampling. You can avoid that by splitting the filters and the signal into even and odd indexed values before the transformation.

\begin{array}{rclcrcl} h_{\mbox{e}} &=& h \downarrow 2 &\qquad& a_{0,\mbox{e}} &=& a_0 \downarrow 2 \\ h_{\mbox{o}} &=& (h \leftarrow 1) \downarrow 2 && a_{0,\mbox{o}} &=& (a_0 \leftarrow 1) \downarrow 2 \end{array}

The arrows \leftarrow and \rightarrow denote left and right shifting, respectively. They shall have the same precedence like convolution, because they are in fact convolutions with a shifted discrete delta impulse.

\delta = (\dots,0,0,\underset{0-\mbox{th position}}{1},0,0,\dots)

The wavelet transformation reformulated to the split filters is:

a_1 = h_{\mbox{e}}\cdot a_{0,\mbox{e}} + h_{\mbox{o}}\cdot a_{0,\mbox{o}} \rightarrow 1
d_1 = g_{\mbox{e}}\cdot a_{0,\mbox{e}} + g_{\mbox{o}}\cdot a_{0,\mbox{o}} \rightarrow 1

This can be written as matrix-vector-multiplication

\begin{array}{rcl} P &=& \begin{pmatrix} h_{\mbox{e}} & h_{\mbox{o}} \rightarrow 1 \\ g_{\mbox{e}} & g_{\mbox{o}} \rightarrow 1 \end{pmatrix} \\ \begin{pmatrix}a_1 \\ d_1\end{pmatrix} &=& P \cdot \begin{pmatrix} a_{0,\mbox{e}} \\ a_{0,\mbox{o}} \end{pmatrix} \end{array}

This matrix P is the polyphase matrix.

Of course, a polyphase matrix can have any size, it need not to have square shape. That is, the principle scales well to any filterbanks, multiwavelets, wavelet transforms based on fractional refinements.

Contents

[edit] Properties

The representation of subband coding by the polyphase matrix is more than about write simplification. It allows to adapt many results from matrix theory and module theory. The following properties are explained for a 2\times 2 matrix, but they scale equally to higher dimensions.

[edit] Invertibility / Perfect reconstruction

The case that a polyphase matrix allows reconstruction of a processed signal from the filtered data, is called perfect reconstruction property. Mathematically this is equivalent to invertibility. According to the theorem of invertibility of a matrix over a ring, the polyphase matrix is invertible if and only if the determinant of the polyphase matrix is a Kronecker delta, which is zero everywhere except of one value.

\det P = h_{\mbox{e}} \cdot g_{\mbox{o}} - h_{\mbox{o}} \cdot g_{\mbox{e}}
\exists A\ A\cdot P = I \iff \exists c\ \exists k\ \det P = c\cdot \delta \rightarrow k

By Cramer's rule the inverse of P can be given immediately.

P^{-1}\cdot\det P = \begin{pmatrix} g_{\mbox{o}} \rightarrow 1 & - h_{\mbox{o}} \rightarrow 1 \\ - g_{\mbox{e}} & h_{\mbox{e}} \end{pmatrix}

[edit] Orthogonality

Orthogonality means that the adjoint matrix P * is also the inverse matrix of P. The adjoint matrix is the transposed matrix with adjoint filters.

P^* = \begin{pmatrix} h_{\mbox{e}}^* & g_{\mbox{e}}^* \\ h_{\mbox{o}}^* \leftarrow 1 & g_{\mbox{o}}^* \leftarrow 1 \end{pmatrix}

It implies, that the Euclidean norm of the input signals is preserved. That is, the according wavelet transform is an isometry.

||a_1||_2^2 + ||d_1||_2^2 = ||a_0||_2^2

The orthogonality condition

P \cdot P^* = I

can be written out

\begin{array}{rcl} h_{\mbox{e}}^* \cdot h_{\mbox{e}} + h_{\mbox{o}}^* \cdot h_{\mbox{o}} &=& \delta \\ g_{\mbox{e}}^* \cdot g_{\mbox{e}} + g_{\mbox{o}}^* \cdot g_{\mbox{o}} &=& \delta \\ h_{\mbox{e}}^* \cdot g_{\mbox{e}} + h_{\mbox{o}}^* \cdot g_{\mbox{o}} &=& 0 \quad. \end{array}

[edit] Operator norm

For non-orthogonal polyphase matrices the question arises what Euclidean norms the output can assume. This can be bounded by the help of the operator norm.

\forall x\ ||P\cdot x||_2 \in \left[||P^{-1}||_2^{-1}\cdot||x||_2, ||P||_2\cdot||x||_2\right]

For the 2\times 2 polyphase matrix the Euclidean operator norm can be given explicitly using the Frobenius norm ||\cdot||_F and the z transform Z: [2]

\begin{array}{rcl} p(z) &=& \frac{1}{2}\cdot ||Z P(z)||_F^2 \\ q(z) &=& |\det (Z P(z))|^2 \\ ||P||_2 &=& \max\left\{\sqrt{p(z)+\sqrt{p(z)^2-q(z)}} : z\in\mathbb{C}\ \land\ |z|=1\right\} \\ ||P^{-1}||_2^{-1} &=& \min\left\{\sqrt{p(z)-\sqrt{p(z)^2-q(z)}} : z\in\mathbb{C}\ \land\ |z|=1\right\} \end{array}

This is a special case of the n\times n matrix where the operator norm can be obtained via z transform and the spectral radius of a matrix or the according spectral norm.

\begin{array}{rcl} ||P||_2 &=& \sqrt{\max\left\{\lambda_{\mbox{max}}(Z P^*(z)\cdot Z P(z)) : z\in\mathbb{C}\ \land\ |z|=1\right\}} \\ &=& \max\left\{||Z P(z)||_2 : z\in\mathbb{C}\ \land\ |z|=1\right\} \\ ||P^{-1}||_2^{-1} &=& \sqrt{\min\left\{\lambda_{\mbox{min}}(Z P^*(z)\cdot Z P(z)) : z\in\mathbb{C}\ \land\ |z|=1\right\}} \\ \end{array}

A signal, where these bounds are assumed can be derived from the eigenvector corresponding to the maximizing and minimizing eigenvalue.

[edit] Lifting scheme

The concept of the polyphase matrix allows matrix decomposition. For instance the decomposition into addition matrices leads to the lifting scheme. [3] However, classical matrix decompositions like LU and QR decomposition cannot be applied immediately, because the filters form a ring with respect to convolution, not a field.

[edit] References

  1. ^ Gilbert Strang and Truong Nguyen. Wavelets and Filter Banks. Wellesley-Cambridge Press, 1997. ISBN 0-9614088-7-1
  2. ^ Henning Thielemann. Adaptive construction of wavelets for image compression. Diploma thesis, Martin-Luther-Universität Halle-Wittenberg, Fachbereich Mathematik/Informatik, 2001. http://edoc.bibliothek.uni-halle.de/servlets/DocumentServlet?id=2134
  3. ^ Ingrid Daubechies and Wim Sweldens. Factoring wavelet transforms into lifting steps. J. Fourier Anal. Appl., 4(3):245--267, 1998. http://cm.bell-labs.com/who/wim/papers/factor/index.html