Motion planning

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 $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_{2\cdot j-k}.$

More verbosely

$T_h=\left(\begin{array}{cccccc}{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& h_{b-1}& h_{b-2}& h_{b-3}& h_{b-4}\\ & & & h_b& h_{b-1}& h_{b-2}\\ & & & & & h_b\end{array}\right).$

The effect of $T_h$ can be expressed in terms of the downsampling operator "$\downarrow$":

$T_h\cdot x=(h*x)\downarrow 2.$

Properties

• $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 $h_{\mathrm{e}}$ be the even-indexed coefficients of $h$ ($(h_{\mathrm{e}}{)}_k=h_{2k}$) and let $h_{\mathrm{o}}$ be the odd-indexed coefficients of $h$ ($(h_{\mathrm{o}}{)}_k=h_{2k+1}$).

Then $\det T_h=(-1{)}^{\lfloor \frac{b-a+1}{4}\rfloor }\cdot h_a\cdot h_b\cdot \mathrm{r}\mathrm{e}\mathrm{s}(h_{\mathrm{e}},h_{\mathrm{o}})$, where $\mathrm{r}\mathrm{e}\mathrm{s}$ 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{t}\mathrm{r}{T}_{g*h}=\mathrm{t}\mathrm{r}{T}_g\cdot \mathrm{t}\mathrm{r}{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{r}\mathrm{e}\mathrm{s}(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=\lambda \cdot 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))=\lambda \cdot (x*(1,-1))$.

• Let ${\lambda }_a,\dots ,{\lambda }_b$ be the eigenvalues of $T_h$, which implies ${\lambda }_a+\dots +{\lambda }_b=\mathrm{t}\mathrm{r}{T}_h$ and more generally ${\lambda }_a^n+\dots +{\lambda }_b^n=\mathrm{t}\mathrm{r}(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{t}\mathrm{r}(T_h^n)={(C_{k}h*(C_{k}h\uparrow 2)*(C_{k}h\uparrow 2^2)*\cdots *(C_{k}h\uparrow 2^{n-1}))}_{[0{]}_{2^n-1}}$

Actually not $n-2$ convolutions are necessary, but only $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 $\varrho (T_h)$. It holds

$\varrho (T_h)\ge \frac{a}{\sqrt{\#h}}\ge \frac{1}{\sqrt{3\cdot \#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$.

See also

• Transfer matrix method
• Hurwitz determinant

References

• Template:Cite article
• Template:Cite thesis (contains proofs of the above properties)