3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ yes, $H$ is a circulant matrix and $H^TH$ is also circulant. Thank you. $\endgroup$ – sigmafang Apr 10 '17 at 0:48
  • $\begingroup$ @RodrigodeAzevedo Then you should use an "in need of moderator intervention" flag and suggest that they migrate it. $\endgroup$ – David Richerby Apr 10 '17 at 12:42
  • $\begingroup$ @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. $\endgroup$ – David Richerby Apr 10 '17 at 13:01
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.