The Gradient / Derivative of Least Squares of 2D Image Convolution

Question

Given the objective function:

$$ \frac{1}{2} {\left\| h \ast x - y \right\|}_{2}^{2} $$

Where $ h $ is the 2D convolution kernel and $ x $ is the 2D convolution image and $ y $ is a given 2D image.

What would be:

$$ \frac{\mathrm{d} \frac{1}{2} {\left\| h \ast x - y \right\|}_{2}^{2} }{\mathrm{d} h}, \; \frac{\mathrm{d} \frac{1}{2} {\left\| h \ast x - y \right\|}_{2}^{2} }{\mathrm{d} x} $$

Answer 1

The easiest approach would be writing each case using Matrix Form of the convolution.
In this answer we assume the discrete convolution is applied only on valid support (Matching MATLAB's valid parameter for the convolution).
Namely, given $ x \in \mathbb{R}^{m \times n} $ and $ h \in \mathbb{R}^{k \times l} $ then $ h \ast x \in \mathbb{R}^{ \left( m - k + 1 \right) \times \left( n - l + 1 \right) } $. Needless to say $ m \geq k $ and $ n \geq l $ as otherwise the operation isn't well defined. Pay attention that this form of convolution isn't commutative.

Remark
For full convolution the problem is easier as the operation is commutative hence no difference between the gradient with respect to $ h $ or $ x $ as one could switch them.

Gradient with Respect to Convolution Kernel $ h $

The matrix form is given by:

$$ f \left( h \right) = \frac{1}{2} {\left\| X h - y \right\|}_{2}^{2} $$

Where $ X $ is the 2D Convolution Matrix Form of the image. Then:

$$ \frac{\mathrm{d} f \left( h \right) }{\mathrm{d} h} = {X}^{T} \left( X h - y \right) $$

The $ {X}^{T} $ forms a correlation (Versus Convolution) with full support of the operation (Equivalent of the full convolution shape in MATLAB syntax).

Hence we have:

$$ \frac{\mathrm{d} \frac{1}{2} {\left\| h \ast x - y \right\|}_{2}^{2} }{\mathrm{d} h} = x \star \left( h \ast x - y \right) $$

In MATLAB Code:

conv2(mX(end:-1:1, end:-1:1), (conv2(mX, mH, CONVOLUTION_MODE_VALID) - mY), CONVOLUTION_MODE_VALID);

Gradient with Respect to Convolution Image $ x $

The matrix form is given by:

$$ f \left( x \right) = \frac{1}{2} {\left\| H x - y \right\|}_{2}^{2} $$

Where $ H $ is the 2D Convolution Matrix Form of the kernel. Then:

$$ \frac{\mathrm{d} f \left( x \right) }{\mathrm{d} x} = {H}^{T} \left( H x - y \right) $$

In MATLAB Code:

conv2((conv2(mX, mH, CONVOLUTION_MODE_VALID) - mY), mH(end:-1:1, end:-1:1), CONVOLUTION_MODE_FULL);

MATLAB Code

The full code is available on my StackExchange Signal Processing Q59089 GitHub Repository (Look at the SignalProcessing\Q59089 folder)..

Answer 2

My (lazy) option is to dig into the Matrix cookbook (pdf), by Kaare Brandt Petersen and Michael Syskind Pedersen, namely section 2.4 Derivatives of Matrices, Vectors and Scalar Forms. They have a whole section on complex matrices as well.