Polyphase matrix

Last updated September 09, 2019

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]

Signal processing is an electrical engineering subfield that focuses on analysing, modifying and synthesizing signals such as sound, images and biological measurements. Signal processing techniques can be used to improve transmission, storage efficiency and subjective quality and to also emphasize or detect components of interest in a measured signal.

Linear filters process time-varying input signals to produce output signals, subject to the constraint of linearity. Many filters implemented in analog electronics, in digital signal processing, or in mechanical systems are classified as causal, time invariant, and linear signal processing filters. Since such filters can be completely characterized by their response to sinusoids of different frequencies, they are sometimes known as frequency filters.

In signal processing, a filter bank is an array of band-pass filters that separates the input signal into multiple components, each one carrying a single frequency sub-band of the original signal. One application of a filter bank is a graphic equalizer, which can attenuate the components differently and recombine them into a modified version of the original signal. The process of decomposition performed by the filter bank is called analysis ; the output of analysis is referred to as a subband signal with as many subbands as there are filters in the filter bank. The reconstruction process is called synthesis, meaning reconstitution of a complete signal resulting from the filtering process.

In mathematics convolution is a mathematical operation on two functions that produces a third function expressing how the shape of one is modified by the other. The term convolution refers to both the result function and to the process of computing it. It is defined as the integral of the product of the two functions after one is reversed and shifted.

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:

{\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}}

The arrows $\scriptstyle \leftarrow$ and $\scriptstyle \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.

In mathematics, the Kronecker delta is a function of two variables, usually just non-negative integers. The function is 1 if the variables are equal, and 0 otherwise:

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

The wavelet transformation reformulated to the split filters is:

{\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}}

This can be written as matrix-vector-multiplication

In mathematics, matrix multiplication or matrix product is a binary operation that produces a matrix from two matrices with entries in a field, or, more generally, in a ring or even a semiring. The matrix product is designed for representing the composition of linear maps that are represented by matrices. Matrix multiplication is thus a basic tool of linear algebra, and as such has numerous applications in many areas of mathematics, as well as in applied mathematics, statistics, physics, economics, and engineering. In more detail, if $A$ is an $n \times m$ matrix and $B$ is an $m \times p$ matrix, their matrix product $AB$ is an $n \times p$ matrix, in which the $m$ entries across a row of $A$ are multiplied with the $m$ entries down a column of $B$ and summed to produce an entry of $AB$ . When two linear maps are represented by matrices, then the matrix product represents the composition of the two maps.

{\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}}

This matrix $\scriptstyle 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.

In mathematics, in the area of wavelet analysis, a refinable function is a function which fulfils some kind of self-similarity. A function $is called refinable with respect to the mask if$

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 $\scriptstyle 2\,\times \,2$ matrix, but they scale equally to higher dimensions.

Matrix (mathematics) Two-dimensional array of numbers with specific operations

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions, arranged in rows and columns. For example, the dimension of the matrix below is 2 × 3, because there are two rows and three columns:

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.

{\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}}

By Cramer's rule the inverse of $\scriptstyle 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}}

Orthogonality

Orthogonality means that the adjoint matrix $\scriptstyle P^{*}$ is also the inverse matrix of $\scriptstyle 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.

\left\|a_{1}\right\|_{2}^{2}+\left\|d_{1}\right\|_{2}^{2}=\left\|a_{0}\right\|_{2}^{2}

The orthogonality condition

P\cdot P^{*}=I

can be written out

{\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}}

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\ \left\|P\cdot x\right\|_{2}\in \left[\left\|P^{-1}\right\|_{2}^{-1}\cdot \|x\|_{2},\|P\|_{2}\cdot \|x\|_{2}\right]

For the $\scriptstyle 2\,\times \,2$ polyphase matrix the Euclidean operator norm can be given explicitly using the Frobenius norm $\scriptstyle \|\cdot \|_{F}$ and the z transform $\scriptstyle Z$ :^[2]

{\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}}

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{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}}

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.

Related Research Articles

In quantum mechanics, bra–ket notation is a standard notation for describing quantum states. It can also be used to denote abstract vectors and linear functionals in mathematics. The notation uses angle brackets and a vertical bar, to denote the scalar product of vectors or the action of a linear functional on a vector in a complex vector space. The scalar product or action is written as

In linear algebra, the determinant is a scalar value that can be computed from the elements of a square matrix and encodes certain properties of the linear transformation described by the matrix. The determinant of a matrix $A$ is denoted $det(A)$ , $det A$ , or $| A |$ . Geometrically, it can be viewed as the volume scaling factor of the linear transformation described by the matrix. This is also the signed volume of the n-dimensional parallelepiped spanned by the column or row vectors of the matrix. The determinant is positive or negative according to whether the linear mapping preserves or reverses the orientation of n-space.

Pauli matrices Matrices important in quantum mechanics and the study of spin

In mathematical physics and mathematics, the Pauli matrices are a set of three $2 \times 2$ complex matrices which are Hermitian and unitary. Usually indicated by the Greek letter sigma, they are occasionally denoted by tau when used in connection with isospin symmetries. They are

In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two signals is the pointwise product of their Fourier transforms. In other words, convolution in one domain equals point-wise multiplication in the other domain. Versions of the convolution theorem are true for various Fourier-related transforms. Let $and be two functions with convolution .$

In linear algebra, the Cayley–Hamilton theorem states that every square matrix over a commutative ring satisfies its own characteristic equation.

In mathematics, a Gaussian function, often simply referred to as a Gaussian, is a function of the form:

In linear algebra, a QR decomposition, also known as a QR factorization or QU factorization is a decomposition of a matrix A into a product A = QR of an orthogonal matrix Q and an upper triangular matrix R. QR decomposition is often used to solve the linear least squares problem and is the basis for a particular eigenvalue algorithm, the QR algorithm.

In mathematics, and in particular linear algebra, a pseudoinverse $A +$ of a matrix $A$ is a generalization of the inverse matrix. The most widely known type of matrix pseudoinverse is the Moore–Penrose inverse, which was independently described by E. H. Moore in 1920, Arne Bjerhammar in 1951, and Roger Penrose in 1955. Earlier, Erik Ivar Fredholm had introduced the concept of a pseudoinverse of integral operators in 1903. When referring to a matrix, the term pseudoinverse, without further specification, is often used to indicate the Moore–Penrose inverse. The term generalized inverse is sometimes used as a synonym for pseudoinverse.

In linear algebra, the Cauchy–Binet formula, named after Augustin-Louis Cauchy and Jacques Philippe Marie Binet, is an identity for the determinant of the product of two rectangular matrices of transpose shapes. It generalizes the statement that the determinant of a product of square matrices is equal to the product of their determinants. The formula is valid for matrices with the entries from any commutative ring.

In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. The objects of focus for this article include rewriting systems. In their most basic form, they consist of a set of objects, plus relations on how to transform those objects.

In signal processing, a finite impulse response (FIR) filter is a filter whose impulse response is of finite duration, because it settles to zero in finite time. This is in contrast to infinite impulse response (IIR) filters, which may have internal feedback and may continue to respond indefinitely.

In physics, the S-matrix or scattering matrix relates the initial state and the final state of a physical system undergoing a scattering process. It is used in quantum mechanics, scattering theory and quantum field theory (QFT).

In mathematics, the mean curvature $of a surface is an extrinsic measure of curvature that comes from differential geometry and that locally describes the curvature of an embedded surface in some ambient space such as Euclidean space.$

In geometry and linear algebra, a Cartesian tensor uses an orthonormal basis to represent a tensor in a Euclidean space in the form of components. Converting a tensor's components from one such basis to another is through an orthogonal transformation.

In mathematics, a wavelet series is a representation of a square-integrable function by a certain orthonormal series generated by a wavelet. This article provides a formal, mathematical definition of an orthonormal wavelet and of the integral wavelet transform.

The lifting scheme is a technique for both designing wavelets and performing the discrete wavelet transform (DWT). In an implementation, it is often worthwhile to merge these steps and design the wavelet filters while performing the wavelet transform. This is then called the second-generation wavelet transform. The technique was introduced by Wim Sweldens.

In applied mathematics, the transfer matrix is a formulation in terms of a block-Toeplitz matrix of the two-scale equation, which characterizes refinable functions. Refinable functions play an important role in wavelet theory and finite element theory.

In fluid mechanics and mathematics, a capillary surface is a surface that represents the interface between two different fluids. As a consequence of being a surface, a capillary surface has no thickness in slight contrast with most real fluid interfaces.

In mathematics, Manin matrices, named after Yuri Manin who introduced them around 1987–88, are a class of matrices with elements in a not-necessarily commutative ring, which in a certain sense behave like matrices whose elements commute. In particular there is natural definition of the determinant for them and most linear algebra theorems like Cramer's rule, Cayley–Hamilton theorem, etc. hold true for them. Any matrix with commuting elements is a Manin matrix. These matrices have applications in representation theory in particular to Capelli's identity, Yangian and quantum integrable systems.

Signal Processing is one of the important research fields that is used widely these days in different aspects of our lives. It is a wide area of research that extends from the simplest form of one-dimensional (1-D) signal processing to the complex form of multi-dimensional (M-D). In signal processing, a filter is used to remove or modify some components or features of a signal. A filter bank is an array of filters that separates the input signal into multiple components, each one carrying a single frequency sub-band of the original signal. Filter banks have a lot of applications these days. In filter banks the process of decomposition performed by the filter bank is called analysis and the reconstruction process is called synthesis. This article provides a short survey of the concepts, principles and applications of Multirate Filter Banks and Multidimensional Directional Filter Banks.

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.
↑ Daubechies, Ingrid; Sweldens, Wim (1998). "Factoring wavelet transforms into lifting steps". J. Fourier Anal. Appl. 4 (3). pp. 245–267. Archived from the original on 2006-12-07.Cite uses deprecated parameter |deadurl= (help)

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[strang1997filterbanks-1] Strang, Gilbert; Nguyen, Truong (1997). Wavelets and Filter Banks . Wellesley-Cambridge Press. ISBN 0-9614088-7-1.

[thielemann2001adaptivewavelet-2] Thielemann, Henning (2001). Adaptive construction of wavelets for image compression (Diploma thesis). Martin-Luther-Universität Halle-Wittenberg, Fachbereich Mathematik/Informatik.

[sweldens1998liftingfactor-3] Daubechies, Ingrid; Sweldens, Wim (1998). "Factoring wavelet transforms into lifting steps". J. Fourier Anal. Appl. 4 (3). pp. 245–267. Archived from the original on 2006-12-07.Cite uses deprecated parameter |deadurl= (help)