Polyphase matrix

In signal processing,a polyphase matrix is a matrix whose elements are filter masks.It represents a filter bank as it is usedin sub-band coders alias discrete wavelet transforms.Gilbert Strang and Truong Nguyen."Wavelets and Filter Banks".Wellesley-Cambridge Press, 1997.ISBN 0-9614088-7-1]

If $h,g$ are two filters,then one level the traditional wavelet transformmaps an input signal $a\_0$ to two output signals $a\_1,\; d\_1$,each of the half length::$a\_1\; =\; (hcdot\; a\_0)\; downarrow\; 2$:$d\_1\; =\; (gcdot\; 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 valuesthat are subsequently flushed by the down-sampling.You can avoid that by splitting the filters and the signalinto even and odd indexed values before the transformation.:The arrows $leftarrow$ and $ightarrow$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\{ecdot\; a\_\{0,mbox\{e\; +\; h\_\{mbox\{ocdot\; a\_\{0,mbox\{o\; ightarrow\; 1$:$d\_1\; =\; g\_\{mbox\{ecdot\; a\_\{0,mbox\{e\; +\; g\_\{mbox\{ocdot\; a\_\{0,mbox\{o\; ightarrow\; 1$This can be written as matrix-vector-multiplication: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.

Properties

The representation of subband coding by the polyphase matrixis 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\; imes\; 2$ matrix,but they scale equally to higher dimensions.

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 invertibilityof a matrix over a ring,the polyphase matrix is invertible if and only ifthe 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\; Acdot\; P\; =\; Iiffexists\; c\; exists\; k\; det\; P\; =\; ccdot\; delta\; ightarrow\; k$ By Cramer's rule the inverse of $P$can be given immediately.:

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.:

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:

Operator norm

For non-orthogonal polyphase matrices the question ariseswhat Euclidean norms the output can assume.This can be bounded by the help of the operator norm.:$forall\; x$
|Pcdot x||_2 inleft [||P^{-1}||_2^{-1}cdot||x||_2, ||P||_2cdot||x||_2 ight] For the $2\; imes\; 2$ polyphase matrixthe Euclidean operator norm can be given explicitlyusing the Frobenius norm $||cdot||\_F$ and the z transform $Z$: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] :
|P||_2 &=& maxleft{sqrt{p(z)+sqrt{p(z)^2-q(z) : zinmathbb{C} land |z|=1 ight} \
|P^{-1}||_2^{-1} &=& minleft{sqrt{p(z)-sqrt{p(z)^2-q(z) : zinmathbb{C} land |z|=1 ight}end{array}

This is a special case of the $n\; imes\; n$ matrixwhere the operator norm can be obtained via z transformand the spectral radius of a matrix or the according spectral norm.:
|P||_2 &=& sqrt{maxleft{lambda_{mbox{max(Z P^*(z)cdot Z P(z)) : zinmathbb{C} land |z|=1 ight\ &=& maxleft{||Z P(z)||_2 : zinmathbb{C} land |z|=1 ight}\
|P^{-1}||_2^{-1} &=& sqrt{minleft{lambda_{mbox{min(Z P^*(z)cdot Z P(z)) : zinmathbb{C} land |z|=1 ight \end{array}A signal, where these bounds are assumedcan be derived from the eigenvectorcorresponding to the maximizing and minimizing eigenvalue.

Lifting scheme

The concept of the polyphase matrix allows matrix decomposition.For instance the decomposition into addition matricesleads to the lifting scheme.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] However, classical matrix decompositions like LUand QR decomposition cannot be applied immediately,because the filters form a ring with respect to convolution,not a field.

References