# Cost of solving a matrix equation using the FFT

I am trying to calculate

$$V = (H^TH+I)^{-1} U$$

where $H\in\mathbb{R}^{m\times m}$ is a circulant convolution matrix corresponding to a convolution kernel $h$, and $U\in\mathbb{R}^{m\times n}$. The computation of $V$ can be done using the FFT algorithm.

I am confused about the computational complexity of using the FFT for this kind of problem. I will be most grateful if you could provide some suggestions or ideas for solving this problem. Thank you.

• yes, $H$ is a circulant matrix and $H^TH$ is also circulant. Thank you. – sigmafang Apr 10 '17 at 0:48
• @RodrigodeAzevedo Then you should use an "in need of moderator intervention" flag and suggest that they migrate it. – David Richerby Apr 10 '17 at 12:42
• @RodrigodeAzevedo Check the "Activity" tab of your profile. In the top-right corner is a link to your helpful flags. If your flag is marked as "pending", it means that the moderators haven't looked at it yet; "declined", probably with a brief explanation, means they disagreed. – David Richerby Apr 10 '17 at 13:01

If $$m \times m$$ symmetric matrix $$\rm H^{\top} H$$ is circulant, then its spectral decomposition is

$$\rm H^{\top} H = Q \Lambda Q^*$$

where the eigenvalues of $$\rm H^{\top} H$$ are given by the Discrete Fourier Transform (DFT) of the first row of $$\rm H^{\top} H$$, and where the eigenvalue matrix is

$$\rm Q = \frac{1}{\sqrt m} \, F_m$$

where $$\rm F_m$$ is the $$m \times m$$ Fourier matrix. Hence,

$$\rm H^{\top} H + I_m = Q \Lambda Q^* + I_m = Q \Lambda Q^* + Q Q^* = Q \, (\Lambda + I_m) \, Q^*$$

and

$$\rm \left( H^{\top} H + I_m \right)^{-1} U = Q \, (\Lambda + I_m)^{-1} \, Q^* U = \frac 1m \, F_m \, (\Lambda + I_m)^{-1} \, F_m^* U$$

The Fast Fourier Transform (FFT) algorithm can now be used to factor the Fourier matrix $$\rm F_m$$ and its Hermitian transpose. What is the cost?

• Computing $$\Lambda$$ requires one DFT of length $$m$$. Using the FFT, that costs $$O (m \log (m))$$.
• Computing $$\rm F_m^* U$$ requires $$n$$ DFTs of length $$m$$. Using the FFT, that costs $$O (n \, m \log (m))$$.
• Multiplying $$\rm (\Lambda + I_m)^{-1}$$ and $$\rm F_m^* U$$ costs $$m$$ additions and $$m \, n$$ divisions.
• Computing $$\rm F_m \, (\Lambda + I_m)^{-1} \, F_m^* U$$ requires $$n$$ DFTs of length $$m$$. Using the FFT, that costs $$O (n \, m \log (m))$$.
• Dividing $$\rm F_m \, (\Lambda + I_m)^{-1} \, F_m^* U$$ by $$m$$ costs $$m \, n$$ divisions.

Thus, the total cost is $$O (n \, m \log (m))$$.

### References

• Thank you very much for your very detailed answer and kind help. – sigmafang Apr 11 '17 at 2:04