圖像處理中，空間域的卷積相當於頻率域的乘積，從矩陣分析角度如何理解？

12-31

卷積相當於對信號乘以一個Toeplitz矩陣，傅里葉變換是可以將矩陣轉換到頻率域中，為什麼在這個空間裡面直接相乘就可以了？

從題目描述來看，題主說的卷積是循環卷積，傅里葉變換是離散傅里葉變換。

先定義一些記號：

用小寫字母 $x,y$ 表示空間域序列，均為列向量，如 $x = [x_0, x_1, ldots, x_{n-1}]^T$ ；
用大寫字母 $X,Y$ 表示頻率域序列，即 $x,y$ 的傅里葉變換，亦為列向量。傅里葉變換和逆變換都可以寫成矩陣形式： $X=Fx, x = F^{-1}X$ ，其中 $F = left[ egin{array}{cccc} 1 1 cdots 1\ 1 ext{e}^{-i2pi/N} cdots ext{e}^{-(N-1) cdot i2pi/N} \ vdots vdots ddots vdots \ 1 ext{e}^{-(N-1) cdot i2pi/N} cdots ext{e}^{-(N-1)^2 cdot i2pi/N} end{array} ight]$ ， $F^{-1} = ar{F}/N$ （上劃線表示共軛）。
用 $ext{Diag}(X)$ 表示以向量 $X$ 的元素為對角元的對角矩陣；
用 $ext{Toep}(x)$ 表示用向量 $x$ 的元素排成的Toeplitz矩陣， $ext{Toep}(x) = left[ egin{array}{ccccc} x_0 x_{n-1} x_{n-2} cdots x_1 \ x_1 x_0 x_{n-1} cdots x_2 \ x_2 x_1 x_0 cdots x_3 \ vdots vdots vdots ddots vdots \ x_{n-1} x_{n-2} x_{n-3} cdots x_0 end{array} ight]$ 。

題主已經知道，在空間域中兩個序列 $x,y$ 的卷積，等於其中一個序列排成的Toeplitz矩陣乘以另一個序列，即 $ext{Toep}(x) cdot y$ 。題主想證明的是，此卷積結果的傅里葉變換，等於兩個序列各自的傅里葉變換之積 $ext{Diag}(X) cdot Y$ 。

待證式： $F cdot ext{Toep}(x) cdot y = ext{Diag}(X) cdot F cdot y$

由於此式對所有 $y$ 都成立，所以待證式化為 $F cdot ext{Toep}(x) = ext{Diag}(X) cdot F$

即 $F cdot ext{Toep}(x) cdot F^{-1} = ext{Diag}(X)$

這是什麼？這是把 $ext{Toep}(x)$ 對角化了！

也就是說，我們的目標的是證明， $ext{Toep}(x)$ 的特徵向量正是逆傅里葉變換矩陣 $F^{-1}$ 的各列（即 $ar{F}$ 的各列），而特徵值則是 $X$ 的各個元素。

$ar{F}$ 的各列的特徵，是每個元素都等於上一個元素乘以 $ext{e}^{kcdot i2pi/N}$ （ $k$ 是列號，從0開始）；第1個元素1也等於最後一個元素 $ext{e}^{k(N-1)cdot i2pi/N}$ 乘以 $ext{e}^{kcdot i2pi/N}$ （指數函數以 $i2pi$ 為周期）。

由於 $ext{Toep}(x)$ 各行之間的平移關係， $ext{Toep}(x)$ 的第 $j+1$ 行乘以 $ar{F}$ 的第 $k$ 列，正好也等於 $ext{Toep}(x)$ 的第 $j$ 行乘以 $ar{F}$ 的第 $k$ 列再乘以 $ext{e}^{kcdot i2pi/N}$ 。

這就證明了 $ar{F}$ 的每一列都是 $ext{Toep}(x)$ 的特徵向量。

由於 $ar{F}$ 各列的首元素均為1，所以第 $k$ 列對應的特徵值就是 $ext{Toep}(x)$ 的第一行乘以 $ar{F}$ 的第 $k$ 列，結果是 $x_0 + x_{n-1} ext{e}^{kcdot i2pi/N} + ldots + x_1 ext{e}^{k(N-1) cdot i2pi/N}$ 。

由指數函數的周期性，這恰好等於 $x_0 + x_1 ext{e}^{-kcdot i2pi/N} + ldots + x_{n-1} ext{e}^{-k(N-1) cdot i2pi/N}$ ，即 $X=Fx$ 的第 $k$ 個元素。於是證畢。

補充一下：用來代替卷積的Toeplitz矩陣，其實是更特殊的Circulant matrix。

一句話說就是卷積這個線性變換在頻域的基下以矩陣的形式表出的時候是對角的。DFT 矩陣是從空域坐標轉化到頻域坐標的正交變換陣，它將空域下非對角的卷積核矩陣對角化了。直接用矩陣證明很麻煩，而且不是 coordinate-free 的，從泛函的角度講更簡潔，也更本質一點

選兩個信號 $h$ 跟 $x$ ，對於兩者的卷積 $h*x$ ，固定卷積核 $h$ ，可將卷積看成是關於 $x$ 的一個線性運算元，像這樣 $K_h(x)$ 。對於圖像來說，信號的index的物理意義是像素點的位置，對於「普通」的信號來說，index是時刻，本質沒有區別，下面就都當做是時間好了，用 $t$ 來表達

不難證明， $K_h$ 的特徵函數是 $e$ 的復指數函數，例如 $e^{jomega t}$ 。你所說的頻域其實就是一個無窮維 Hilbert 空間，其標準正交基是規定死的，就是這樣的復指數函數。 $e^{j omega t}$ 對應的卷積運算元的特徵值是 $h(t)$ 跟 $e^{j omega t}$ 的內積。運算元的特徵函數在變換後有形式不變性，僅僅是乘上了特徵值，這個跟通常說的矩陣的特徵值和特徵函數（至少看起來）是一回事

從這種角度看，Fourier 變換就是拿信號跟 $e^{jomega t}$ 做內積，這樣就可以用 $e^{jomega t}$ 來做線性表出，也就是說 $x(t) = sum_{omega}{langle x(t),e^{j omega t} angle} e^{j omega t}$ ，這是 Hilbert 空間的性質所決定的。換句話說，Fourier 變換將信號投影到了 $e ^{j omega t}$ 所張成的 Hilbert 空間（頻域）上，其結果為信號在這個空間上的坐標

那麼其實卷積的意義已經很清楚了。將 $x(t)$ 作 Fourier 變換，或者說用 $e^{j omega t}$ 展開，得到無窮多個頻率分量，卷積就是將這無窮多個頻率分量分別用 $K_h$ 映射過去，或者說通過以 $h(t)$ 為衝激響應的線性系統。由於 $e^{j omega t}$ 是特徵函數，所以卷積對它們的作用只是乘上了一個係數，這個係數就是頻響，等於 $h(t)$ 的 Fourier 變換 $langle h(t),e^{j omega t} angle$ ，這樣這些頻率分量就是正交著進去正交著出來。那麼怎麼得到卷積後的結果呢？把映射之後頻率的分量再加起來就行了

簡單來說，就是 $e ^{j omega t}$ 先分別乘上 $langle x(t),e^{j omega t} angle$ ，這樣就得到了 $x$ ，再分別乘上 $langle h(t),e^{j omega t} angle$ ，這樣就得到了 $h*x$ 。兩步合成一步，就是 $langle x(t),e^{j omega t} angle$ 和 $langle h(t),e^{j omega t} angle$ 直接相乘，或者說是頻域坐標的相乘

其實在這種情況下，你就把運算元看成是無窮維矩陣好了，上面就是個無窮維矩陣對角化