ChapterZero » Radial filters preserved under convolution?

Radial filters preserved under convolution?

Mathematics — Alex @ 3:16 pm

I spent most of my time today trying to answer the following question. Let $G_1 = \{b_k\}_{k \in \Z^d}, G_2 = \{a_k\}_{k \in \Z^d}$ be radial filters in the sense that $a_k = a_{k^\prime}$ when $|k| = |k^\prime|$ (and likewise for the b_k ’s). Then is the filter $G = G_1 \star G_2 = \{c_k\}$ also radial?

The answer, it turns out, is no in general (but of course it is true in $\Z$ , because then the filters are just even). In the 2-d case, the filters

$\displaystyle b_k = \begin{cases} 1 & \text{ when $|k| = 5$} \\ 0 \text{ otherwise} \end{cases} \quad a_k = \begin{cases} 1 & \text{ when $|k| = 2\sqrt{5}$} \\ 0 \text{ otherwise} \end{cases}$

serve as a counterexample: $c_{(4,3)} = 1$ , but $c_{(5,0)} = 2$ .

I haven’t yet found a satisfactory reason for this failure — my vague idea is that rotations do not preserve the lattice, but that doesn’t do more than imply the result. To construct this counterexample, I followed Papadakis’ advice of looking at the simplest radial filters of all: filters which are unity on the intersections of the lattice and a sphere and zero elsewhere, as in the examples given above. In the Fourier domain, the convolution product would look like

$\displaystyle \left( \sum_{|k| = R_1} e^{2\pi i k \cdot \xi} \right) \left( \sum_{|k| = R_2} e^{2\pi i k \cdot \xi} \right),$

and if the resulting filter was also radial, it would look like a sum

$\displaystyle \sum_{M \leq R_1 + R_2}\left( c_M \sum_{|k| = M} e^{2\pi i k \cdot \xi} \right)$

in the frequency domain. I wrote a Mathematica program that takes R_1 and R_2 , calculates the coefficients of the resulting filter, and says if it breaks into such a sum. Now that I think about it, that would have been much easier to do in the spatial domain.

As a corollary of this result, you can see that the following proposition is not true in general: if $\ell, k, k^\prime \in \Z^d$ with $|k| = |k^\prime|$ , there is an $\ell^\prime \in \Z^d$ so that $|\ell - k| = |\ell^\prime - k^\prime|$ and $|\ell| = |\ell^\prime|$ .