- Polyphase matrix
In
signal processing ,a polyphase matrix is a matrix whose elements are filter masks.It represents afilter bank as it is usedinsub-band coder s aliasdiscrete wavelet transform s.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 2Note, that the dot means
polynomial multiplication , i.e.convolution anddownarrow meansdownsampling .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.:egin{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 2end{array}The arrows leftarrow and ightarrowdenote 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 1This can be written as matrix-vector-multiplication:egin{array}{rcl}P &=&egin{pmatrix}h_{mbox{e & h_{mbox{o ightarrow 1 \g_{mbox{e & g_{mbox{o ightarrow 1end{pmatrix}\egin{pmatrix}a_1 \ d_1end{pmatrix}&=&Pcdotegin{pmatrix}a_{0,mbox{e \a_{0,mbox{oend{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
filterbank s,multiwavelet s,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 andmodule 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 ifthedeterminant of the polyphase matrix is aKronecker 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 ByCramer's rule the inverse of Pcan be given immediately.:P^{-1}cdotdet P =egin{pmatrix} g_{mbox{o ightarrow 1 & - h_{mbox{o ightarrow 1 \- g_{mbox{e & h_{mbox{eend{pmatrix}Orthogonality
Orthogonality means that the
adjoint matrix P^*is also the inverse matrix of P.The adjoint matrix is thetransposed matrix withadjoint filter s.:P^* =egin{pmatrix}h_{mbox{e^* & g_{mbox{e^* \h_{mbox{o^* leftarrow 1 & g_{mbox{o^* leftarrow 1end{pmatrix}It implies, that the
Euclidean norm of the input signals is preserved.That is, the according wavelet transform is anisometry .:a_1||_2^2 + ||d_1||_2^2 = ||a_0||_2^2The orthogonality condition:P cdot P^* = Ican be written out:egin{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}
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 theFrobenius norm cdot||_F and thez 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] :egin{array}{rcl}p(z) &=& frac{1}{2}cdot ||Z P(z)||_F^2 \q(z) &=& |det (Z P(z))|^2 \
|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 transform and thespectral radius of a matrix or the accordingspectral norm .:egin{array}{rcl}
|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 thelifting 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 LUandQR decomposition cannot be applied immediately,because the filters form a ring with respect to convolution,not a field.References
Wikimedia Foundation. 2010.