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
are two filters, then one level the traditional wavelet transform maps an input signal
to two output signals
, each of the half length:
![{\displaystyle {\begin{aligned}a_{1}&=(h\cdot a_{0})\downarrow 2\\d_{1}&=(g\cdot a_{0})\downarrow 2\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/784cb2c79654d85de67305745441a8bce5455347)
Note, that the dot means polynomial multiplication; i.e., convolution and
means downsampling.
If the above formula is implemented directly, you will compute values that are subsequently flushed by the down-sampling. You can avoid their computation by splitting the filters and the signal into even and odd indexed values before the wavelet transformation:
![{\displaystyle {\begin{aligned}h_{\mbox{e}}&=h\downarrow 2&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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84985982636f164aaa08dd03366d9a794ad7e2a7)
The arrows
and
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.
![{\displaystyle \delta =(\dots ,0,0,{\underset {0-{\mbox{th position}}}{1}},0,0,\dots )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3fb58d130a75bd825993cde3a6012b31ff17734)
The wavelet transformation reformulated to the split filters is:
![{\displaystyle {\begin{aligned}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\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d8601ad36001ffdccec9232f72de775441d6042)
This can be written as matrix-vector-multiplication
![{\displaystyle {\begin{aligned}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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e19effd2f3af57d6d88605378d3ae227c1a7940)
This matrix
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 sub-band coding by the polyphase matrix is more than about write simplification. It allows the adaptation of many results from matrix theory and module theory. The following properties are explained for a
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 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 for one value.
![{\displaystyle {\begin{aligned}\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\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/54395f062f0f6aeb8ff270f3eab3e50b4e65709c)
By Cramer's rule the inverse of
can be given immediately.
![{\displaystyle 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7934ea8022938fd55320797ad366d2c32587947a)
Orthogonality
Orthogonality means that the adjoint matrix
is also the inverse matrix of
. The adjoint matrix is the transposed matrix with adjoint filters.
![{\displaystyle P^{*}={\begin{pmatrix}h_{\mbox{e}}^{*}&g_{\mbox{e}}^{*}\\h_{\mbox{o}}^{*}\leftarrow 1&g_{\mbox{o}}^{*}\leftarrow 1\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1507b9198bc5ffbb06297370425ee608626c7164)
It implies, that the Euclidean norm of the input signals is preserved. That is, the according wavelet transform is an isometry.
![{\displaystyle \left\|a_{1}\right\|_{2}^{2}+\left\|d_{1}\right\|_{2}^{2}=\left\|a_{0}\right\|_{2}^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e5486448c1366a07147d882c79f4c407a0192fb)
The orthogonality condition
![{\displaystyle P\cdot P^{*}=I}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a5a2f09319ed04a14192bfaecf3ab0354117ed9)
can be written out
![{\displaystyle {\begin{aligned}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\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/970337ee67210253d5cd1da644a6d3e8e4b12e9b)
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.
![{\displaystyle \forall x\ \left\|P\cdot x\right\|_{2}\in \left[\left\|P^{-1}\right\|_{2}^{-1}\cdot \|x\|_{2},\|P\|_{2}\cdot \|x\|_{2}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55d4b3bd79206346495464ea2faf44696fad3fdd)
For the
polyphase matrix the Euclidean operator norm can be given explicitly using the Frobenius norm
and the z transform
:[2]
![{\displaystyle {\begin{aligned}p(z)&={\frac {1}{2}}\cdot \left\|ZP(z)\right\|_{F}^{2}\\q(z)&=\left|\det[ZP(z)]\right|^{2}\\\|P\|_{2}&=\max \left\{{\sqrt {p(z)+{\sqrt {p(z)^{2}-q(z)}}}}:z\in \mathbb {C} \ \land \ |z|=1\right\}\\\left\|P^{-1}\right\|_{2}^{-1}&=\min \left\{{\sqrt {p(z)-{\sqrt {p(z)^{2}-q(z)}}}}:z\in \mathbb {C} \ \land \ |z|=1\right\}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d69584210e1bd271ef25bd97289dfe5a7d998523)
This is a special case of the
matrix where the operator norm can be obtained via z transform and the spectral radius of a matrix or the according spectral norm.
![{\displaystyle {\begin{aligned}\left\|P\right\|_{2}&={\sqrt {\max \left\{\lambda _{\text{max}}\left[ZP^{*}(z)\cdot ZP(z)\right]:z\in \mathbb {C} \ \land \ |z|=1\right\}}}\\&=\max \left\{\left\|ZP(z)\right\|_{2}:z\in \mathbb {C} \ \land \ |z|=1\right\}\\[3pt]\left\|P^{-1}\right\|_{2}^{-1}&={\sqrt {\min \left\{\lambda _{\text{min}}\left[ZP^{*}(z)\cdot ZP(z)\right]:z\in \mathbb {C} \ \land \ |z|=1\right\}}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f7d8a63a91d26f2c1b1f70edfec7ee11ca17068)
A signal, where these bounds are assumed can be derived from the eigenvector corresponding to the maximizing and minimizing eigenvalue.
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.
References
- ^ Strang, Gilbert; Nguyen, Truong (1997). Wavelets and Filter Banks. Wellesley-Cambridge Press. ISBN 0-9614088-7-1.
- ^ Thielemann, Henning (2001). Adaptive construction of wavelets for image compression (Diploma thesis). Martin-Luther-Universität Halle-Wittenberg, Fachbereich Mathematik/Informatik. Archived from the original on 2011-07-18. Retrieved 2006-11-10.
- ^ Daubechies, Ingrid; Sweldens, Wim (1998). "Factoring wavelet transforms into lifting steps". J. Fourier Anal. Appl. 4 (3): 245–267. doi:10.1007/BF02476026. S2CID 195242970. Archived from the original on 2006-12-07.