3

If c(x) is a circulant matrix of a vector x, is it always true that $c(x)^{-1}=\mathcal{F}^{-1}(\mathcal{F}(1/x))$? How can we prove it?

In this case $c(x)^{-1}$ is the inverse of the circulant matrix of vector x, $\mathcal{F}(x)$ represent the fourier transform while $\mathcal{F}^{-1}$ is the fourier inverse. The division in $1/x$ is performed element wise (in matlab it is written as "1./x").

gorba cuh
  • 33

1 Answers1

4

Let $\mathcal{C}(\mathbf{x}) \in \mathbb{C}^{N\times N}$ denote the circulant matrix generated by $\mathbf{x} \in \mathbb{C}^N$ (with $\mathbf{x}$ as its first column). Finding eigenvalues/eigenvectors for $\mathcal{C}(\mathbf{x})$ shows that the latter can be written as \begin{equation} \mathcal{C}(\mathbf{x}) = \mathbf{F}_N^H\mathcal{D}(\sqrt{N}\mathbf{F}_N\mathbf{x})\mathbf{F}_N, \end{equation} where $\mathbf{F}_N \in \mathbb{C}^{N\times N}$ is the unitary DFT matrix, i.e., $[\mathbf{F}_N]_{n,k}=\frac{1}{\sqrt{N}}e^{-i 2\pi k n /N}$, $(\cdot)^H$ denotes hermitian traspose, and $\mathcal{D}(\mathbf{z})$ is the diagonal matrix with main diagonal elements given by $\mathbf{z}$.

Note that $\sqrt{N}\mathbf{F}_N\mathbf{x}$ is equal to matlab's "fft($\mathbf{x}$)" and $(1/\sqrt{N})\mathbf{F}_N^H\mathbf{x}$ is equal to matlab's "ifft($\mathbf{x}$)" and the above decomposition essentially states that compuation of $\mathcal{C}(\mathbf{x})\mathbf{y}$ is equivalent to "ifft(fft(x).*fft(y))", i.e., (circular) convolution in time domain corresponds to multiplication in (discrete) frequency domain.

Now, if $\sqrt{N}\mathbf{F}_N\mathbf{x}$ does not have a zero element, then $\mathcal{D}(\sqrt{N}\mathbf{F}_N\mathbf{x})$ is invertible, therefore, \begin{align} \mathcal{C}^{-1}(\mathbf{x}) &= \left(\mathbf{F}_N^H \mathcal{D}(\sqrt{N}\mathbf{F}_N\mathbf{x})\mathbf{F}_N\right)^{-1} \\ &= \mathbf{F}_N^{-1} \mathcal{D}^{-1}(\sqrt{N}\mathbf{F}_N\mathbf{x})(\mathbf{F}_N^{H})^{-1} \\ &= \mathbf{F}_N^{H} \mathcal{D}^{-1}(\sqrt{N}\mathbf{F}_N\mathbf{x})\mathbf{F}_N\\ \end{align}

which implies that $\mathcal{C}^{-1}(\mathbf{x})\mathbf{y}$ can be computed as "ifft(fff(y)./fft(x))".

Stelios
  • 3,077