Conditions for the decomposition of a discrete convolution kernel in two

Question

Let $h \in \mathbb{R}^{n_1\times\ldots\times n_D}$. Are there constraints that would guarantee that there exists a $g \in \mathbb{R}^{m_1\times\ldots\times m_D}, \, 2m_i-1 = n_i$ such that $h = g*g$, where $*$ is discrete convolution?

Answer 1

I would suggest to algorithmically try to find $g$. After that, we try to validate whether $g$ does indeed exist.

Consider the case for 1-dimensional $h\in\mathbb{R}^{n_1}, g\in\mathbb{R}^{m_1}$. At the starting point, we have $$ h(0)=g(0)^2 $$ so we can already solve for $g(0)$. For the second point, we have $$ h(1)=g(0)g(1)+g(1)g(0) = 2g(0)g(1) $$ Since we already know $g(0)$, we can solve for $g(1)$. Then, for the point that follows after it $$ h(2)=g(0)g(2)+g(1)^2+g(2)g(0) $$ Again, we already know $g(0)$ and $g(1)$ so we can solve for $g(2)$. This can be repeated up to $h(m_1-1)$. By then, we will have the solution for $g$. All that is left is to validate the solution using $h(m_1)\dots h(n_1-1)$. If any of the validation fails, then the "convolutional root" $g$ does not exist.

This algorithm can also be generalized for 2 dimensions and above.

As a matter of curiosity, every even-indexed element $h(2i_1)$ contains $g(i_1)^2$. Also, $h(2m_1)=g(m_1)^2$.