Transfer matrix

From Quire, the open reference·In wavelet theory·2 min read

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.

For the mask ${\displaystyle h}$ , which is a vector with component indexes from ${\displaystyle a}$ to ${\displaystyle b}$ , the transfer matrix of ${\displaystyle h}$ , we call it ${\displaystyle T_{h$ here, is defined as

${\displaystyle (T_{h})_{j,k}=h_{2\cdot j-k}.}$

More verbosely

${\displaystyle T_{h}={\begin{pmatrix}h_{a}&&&&&\\h_{a+2}&h_{a+1}&h_{a}&&&\\h_{a+4}&h_{a+3}&h_{a+2}&h_{a+1}&h_{a}&\\\ddots &\ddots &\ddots &\ddots &\ddots &\ddots \\&h_{b&#$

The effect of ${\displaystyle T_{h$ can be expressed in terms of the downsampling operator " ${\displaystyle \downarrow }$ ":

${\displaystyle T_{h}\cdot x=(h*x)\downarrow 2.}$

Properties#edit

${\displaystyle T_{h}\cdot x=T_{x}\cdot h}$ .
If you drop the first and the last column and move the odd-indexed columns to the left and the even-indexed columns to the right, then you obtain a transposed Sylvester matrix.
The determinant of a transfer matrix is essentially a resultant. More precisely: Let ${\displaystyle h_{\mathrm {e}$ be the even-indexed coefficients of ${\displaystyle h}$ ( ${\displaystyle (h_{\mathrm {e} })_{k}=h_{2k$ ) and let ${\displaystyle h_{\mathrm {o}$ be the odd-indexed coefficients of ${\displaystyle h}$ ( ${\displaystyle (h_{\mathrm {o} })_{k}=h_{2k+1$ ). Then ${\displaystyle \det T_{h}=(-1)^{\lfloor {\frac {b-a+1}{4\rfloor }\cdot h_{a}\cdot h_{b}\cdot \mathrm {res} (h_{\mathrm {e} },h_{\mathrm {o} })}$ , where ${\displaystyle \mathrm {res} }$ is the resultant. This connection allows for fast computation using the Euclidean algorithm.
For the trace of the transfer matrix of convolved masks holds ${\displaystyle \mathrm {tr} ~T_{g*h}=\mathrm {tr} ~T_{g}\cdot \mathrm {tr} ~T_{h$
For the determinant of the transfer matrix of convolved mask holds ${\displaystyle \det T_{g*h}=\det T_{g}\cdot \det T_{h}\cdot \mathrm {res} (g_{-},h)}$ where ${\displaystyle g_{-$ denotes the mask with alternating signs, i.e. ${\displaystyle (g_{-})_{k}=(-1)^{k}\cdot g_{k$ .
If ${\displaystyle T_{h}\cdot x=0}$ , then ${\displaystyle T_{g*h}\cdot (g_{-}*x)=0}$ . This is a concretion of the determinant property above. From the determinant property one knows that ${\displaystyle T_{g*h$ is singular whenever ${\displaystyle T_{h$ is singular. This property also tells, how vectors from the null space of ${\displaystyle T_{h$ can be converted to null space vectors of ${\displaystyle T_{g*h$ .
If ${\displaystyle x}$ is an eigenvector of ${\displaystyle T_{h$ with respect to the eigenvalue ${\displaystyle \lambda }$ , i.e. ${\displaystyle T_{h}\cdot x=\lambda \cdot x}$ , then ${\displaystyle x*(1,-1)}$ is an eigenvector of ${\displaystyle T_{h*(1,1)$ with respect to the same eigenvalue, i.e. ${\displaystyle T_{h*(1,1)}\cdot (x*(1,-1))=\lambda \cdot (x*(1,-1))}$ .
Let ${\displaystyle \lambda _{a},\dots ,\lambda _{b$ be the eigenvalues of ${\displaystyle T_{h$ , which implies ${\displaystyle \lambda _{a}+\dots +\lambda _{b}=\mathrm {tr} ~T_{h$ and more generally ${\displaystyle \lambda _{a}^{n}+\dots +\lambda _{b}^{n}=\mathrm {tr} (T_{h}^{n})}$ . This sum is useful for estimating the spectral radius of ${\displaystyle T_{h$ . There is an alternative possibility for computing the sum of eigenvalue powers, which is faster for small ${\displaystyle n}$ . Let ${\displaystyle C_{k}h}$ be the periodization of ${\displaystyle h}$ with respect to period ${\displaystyle 2^{k}-1}$ . That is ${\displaystyle C_{k}h}$ is a circular filter, which means that the component indexes are residue classes with respect to the modulus ${\displaystyle 2^{k}-1}$ . Then with the upsampling operator ${\displaystyle \uparrow }$ it holds ${\displaystyle \mathrm {tr} (T_{h}^{n})=\left(C_{k}h*(C_{k}h\uparrow 2)*(C_{k}h\uparrow 2^{2})*\cdots *(C_{k}h\uparrow 2^{n-1})\right)_{[0]_{2^{n}-1$ Actually not ${\displaystyle n-2}$ convolutions are necessary, but only ${\displaystyle 2\cdot \log _{2}n}$ ones, when applying the strategy of efficient computation of powers. Even more the approach can be further sped up using the Fast Fourier transform.
From the previous statement we can derive an estimate of the spectral radius of ${\displaystyle \varrho (T_{h})}$ . It holds ${\displaystyle \varrho (T_{h})\geq {\frac {a}{\sqrt {\#h\geq {\frac {1}{\sqrt {3\cdot \#h$ where ${\displaystyle \#h}$ is the size of the filter and if all eigenvalues are real, it is also true that ${\displaystyle \varrho (T_{h})\leq a}$ , where ${\displaystyle a=\Vert C_{2}h\Vert _{2$ .

References#edit

Strang, Gilbert (1996). "Eigenvalues of ${\displaystyle (\downarrow 2){H$ and convergence of the cascade algorithm". IEEE Transactions on Signal Processing. 44: 233–238. doi:10.1109/78.485920.
Thielemann, Henning (2006). Optimally matched wavelets (PhD thesis). (contains proofs of the above properties)

Categories Wavelets Numerical analysis

This article is mirrored from “Transfer matrix” on English Wikipedia, revision 1340618272, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1340618272 · just now

Transfer matrix

Properties#edit

See also#edit

References#edit