# How to estimate filters using conjugate gradient?

An image $I$ is computed by performing convolution and summation:

$$\sum_{k=0}^{K-1} z_k * f_k = I$$

Given only the feature maps $z_k$ and the resulting image $I$, how do I compute the filters $f_k$ ?

This is a linear system, therefore it must be possible to solve it with conjugate gradient. How to formulate it as $\mathbf{Ax} = \mathbf{b}$ ?

$z_k$ and $I$ have both the same quadratic size $N \times N$.

• Welcome to DSP.SE! I've redone all your equations in MathJAX, the LaTex formatting available here. I didn't understand your first equation, so I've re-written it slightly from what you had. Can you please check to see if it still makes sense? – Peter K. Oct 14 '15 at 15:19
• You'll need to vectorize and concatenate all of the feature maps into a single vector, $\mathbf{z}$. Then do the same thing for the convolution matrices for the $f_k$, call it $F$. The last matrix will be a mix of ones and zeros, where the ones are in the correct place to add the pixels together, call it $\mathbf{S}$. The system will then be $\mathbf{SFz} = \operatorname{vec}( \mathbf{I})$. – AnonSubmitter85 Oct 14 '15 at 17:01
• Thank you for your answer. Does that mean that SF is a or corresponds to a Toeplitz matrix? – A. Eckert Oct 14 '15 at 18:25

This is a typical deconvolution problem that you can solve either by transforming to the frequency domain where convolution is a simple multiplication:

\begin{equation} F\left \{ {\bf{I}} \right \}= F\left \{ {\bf{z}} \right \} F\left \{ {\bf{f}} \right \}, \end{equation}

where ${\mathcal{F}}$ denotes the Fourier transform (or DFT) so $f$ will be:

\begin{equation} {\bf{f}}={\mathcal{F}}^{-1}\left \{ \frac{{\mathcal{F}}\left \{ {\bf{I}} \right \}}{{\mathcal{F}}\left \{ {\bf{z}} \right \}} \right \} \end{equation}, where ${\mathcal{F}}^{-1}$ is the inverse Fourier transform.

Otherwise, you can also represent in a matrix form, using a Circulant (kind of Toeplitz) for the convolution operation. The frequency domain calculation though does not involve inverting (or pseudo inverting) a matrix.

If there's additive noise in your problem, please see Wiener deconvolution (both time and frequency domain implementation)

• Thank you for your answer, it helped. The filter f (result of the division in frequency domain) would have the same size as the Image I and the feature map z. But i know that the filter is way smaller - e.g. im operating on 100x100 images and the filter sizes are 5x5. How do i construct these small 5x5 filters? – A. Eckert Oct 16 '15 at 14:46