Transfer matrix

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 $h$, which is a vector with component indexes from $a$ to $b$,the transfer matrix of $h$, we call it $T\_h$ here, is defined as:$(T\_h)\_\{j,k\}\; =\; h\_\{2cdot\; j-k\}$.More verbosely:The effect of $T\_h$ can be expressed in terms of the downsampling operator "$downarrow$"::$T\_hcdot\; x\; =\; (h*x)downarrow\; 2$.

Properties

* $T\_hcdot\; x\; =\; T\_xcdot\; 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 $h\_\{mathrm\{e$ be the even indexed coefficients of $h$ ($(h\_\{mathrm\{e)\_k\; =\; h\_\{2cdot\; k\}$) and let $h\_\{mathrm\{o$ be the odd indexed coefficients of $h$ ($(h\_\{mathrm\{o)\_k\; =\; h\_\{2cdot\; k+1\}$).:Then $det\; T\_h\; =\; (-1)^\{lfloorfrac\{b-a+1\}\{4\}\; floor\}cdot\; h\_acdot\; h\_bcdotmathrm\{res\}(h\_\{mathrm\{e,h\_\{mathrm\{o)$, where $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:$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:$det\; T\_\{g*h\}\; =\; det\; T\_\{g\}\; cdot\; det\; T\_\{h\}\; cdot\; mathrm\{res\}(g\_-,h)$:where $g\_-$ denotes the mask with alternating signs, i.e. $(g\_-)\_k\; =\; (-1)^k\; cdot\; g\_k$.
* If $T\_\{h\}cdot\; x\; =\; 0$, then $T\_\{g*h\}cdot\; (g\_-*x)\; =\; 0$.: This is a concretion of the determinant property above. From the determinant property one knows that $T\_\{g*h\}$ is singular whenever $T\_\{h\}$ is singular. This property also tells, how vectors from the null space of $T\_\{h\}$ can be converted to null space vectors of $T\_\{g*h\}$.
* If $x$ is an eigenvector of $T\_\{h\}$ with respect to the eigenvalue $lambda$, i.e.: $T\_\{h\}cdot\; x\; =\; lambdacdot\; x$,:then $x*(1,-1)$ is an eigenvector of $T\_\{h*(1,1)\}$ with respect to the same eigenvalue, i.e.: $T\_\{h*(1,1)\}cdot\; (x*(1,-1))\; =\; lambdacdot\; (x*(1,-1))$.
* Let $lambda\_a,dots,lambda\_b$ be the eigenvalues of $T\_h$, which implies $lambda\_a+dots+lambda\_b\; =\; mathrm\{tr\}~T\_h$ and more generally $lambda\_a^n+dots+lambda\_b^n\; =\; mathrm\{tr\}(T\_h^n)$. This sum is useful for estimating the spectral radius of $T\_h$. There is an alternative possibility for computing the sum of eigenvalue powers, which is faster for small $n$.:Let $C\_k\; h$ be the periodization of $h$ with respect to period $2^k-1$. That is $C\_k\; h$ is a circular filter, which means that the component indexes are residue classes with respect to the modulus $2^k-1$. Then with the upsampling operator $uparrow$ it holds:$mathrm\{tr\}(T\_h^n)\; =\; left(C\_k\; h\; *\; (C\_k\; huparrow\; 2)\; *\; (C\_k\; huparrow\; 2^2)\; *\; cdots\; *\; (C\_k\; huparrow\; 2^\{n-1\})\; ight)\_\{\; [0]\; \_\{2^n-1$:Actually not $n-2$ convolutions are necessary, but only $2cdot\; 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 $varrho(T\_h)$. It holds:$varrho(T\_h)\; ge\; frac\{a\}\{sqrt\{\#\; h\; ge\; frac\{1\}\{sqrt\{3cdot\; \#\; h$:where $\#\; h$ is the size of the filter and if all eigenvalues are real, it is also true that:$varrho(T\_h)\; le\; a$,:where $a\; =\; Vert\; C\_2\; h\; Vert\_2$.

ee also

* Transfer matrix method

References

* Gilbert Strang: Eigenvalues of $(downarrow\; 2)\{H\}$ and convergence of the cascade algorithm. "IEEE Transactions on Signal Processing", 44:233-238, 1996.

* Henning Thielemann: [http://nbn-resolving.de/urn:nbn:de:gbv:46-diss000103131 Optimally matched wavelets] , 2006 (contains proofs of the above properties)