Gradient of 2D convolution

Question

For a image $u\in \mathbb{R}^{20\times 20}$, we have a filter $h\in \mathbb{R}^{3\times 3}$, i.e. the average blur filter is $$ h =\frac{1}{9} \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}. $$ What is the gradient of $h*u$ with respect to u? Furthermore, we transform u into a vector $v\in\mathbb{R}^{400}$ and transform $h*u$ into another vector $\tilde{v}\in\mathbb{R}^{400}$. If $\tilde{v} = f(v)$, what is the gradient of $f(v)$?

Answer 1

The helix transform will map a ${\rm 2D}$ convolution to ${\rm 1D}$. $$\eqalign{ &H',\,U' = {\rm helix}(H,U) \\ &v = {\rm vec}(V)\\ &V = H*U &({\rm 2D\;convolution}) \\ &v = h'*u' &({\rm 1D\;convolution}) \\ }$$ In turn, ${\rm 1D}$ convolutions can be calculated as multiplication by a Toeplitz matrix $$\eqalign{ v &= h'*u' \;=\; {\cal H'}\cdot u' \\ }$$

Finally, the scalar  derivative of a convolution  is $$\eqalign{ Dv &= h'*(Du') \\ }$$ Putting all of these pieces together, you can construct the gradient in question.