# 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