# A Class of Algorithms for Continuous Wavelet Transform Based on the Circulant Matrix
## 2 Primary Definitions and Theorems  
Definition 1: **Circulant matrix**: _An \(N\times N\) circulant matrix \(\mathbf{C}\) takes the form [20; 21]_  
\[\mathbf{C}= \begin{bmatrix}c_{0}&c_{N-1}&\cdots&c_{2}&c_{1}\\ c_{1}&c_{0}&c_{N-1}&&c_{2}\\ \vdots&c_{1}&c_{0}&\ddots&\vdots\\ c_{N-2}&&\ddots&\ddots&c_{N-1}\\ c_{N-1}&c_{N-2}&\cdots&c_{1}&c_{0}\end{bmatrix}  \tag{1}\]  
A circulant matrix is fully specified by one vector, \(c\), which appears as the first column of \(\mathbf{C}\). Definition 2: Discrete Fourier transform(DFT): The sequence of \(N\) complex numbers \([x_{0},x_{1},\cdots,x_{N-1}]^{\mathrm{T}}\) is transformed into an N-periodic sequence of complex numbers [22]  
\[X_{k}=\sum_{n=0}^{N-1}x_{n}\omega_{k}^{-n},k=0,1,\cdots,N-1, \tag{2}\]  
where \(i=\sqrt{-1}\), \(\omega_{k}=e^{\frac{2\pi ij}{N}}\) is the N-th root of unity. Equation (2) can be written as  
\[\left( \begin{array}{c}X_{0}\\ X_{1}\\ \vdots\\ X_{N-1}\end{array} \right)=\mathbf{F_{N}}\left( \begin{array}{c}x_{0}\\ x_{1}\\ \vdots\\ x_{N-1}\end{array} \right) \tag{3}\]  
where \(\mathbf{F_{N}}\) is a \(N\times N\) matrix, defined as  
\[\mathbf{F_{N}}(k,j)=\omega_{k-1}^{-(j-1)},\quad k,j=1,2,\cdots,N. \tag{4}\]  
It is easy to verify that  
\[\mathbf{F_{N}}^{-1}=\frac{1}{N}\mathbf{F_{N}}^{*} \tag{5}\]  
where \"\(*\)\" means conjugate transposition. Then, the inverse discrete Fourier transform (IDFT) is given as  
\[\left( \begin{array}{c}x_{0}\\ x_{1}\\ \vdots\\ x_{N-1}\end{array} \right)=\frac{1}{N}\mathbf{F_{N}}^{*}\left( \begin{array}{ c}X_{0}\\ X_{1}\\ \vdots\\ X_{N-1}\end{array} \right) \tag{6}\]  
Theorem 1: _References [20; 21] The matrix \(\mathbf{C}\) defined in (1) can be diagonalized by the DFT matrix \(\mathbf{F_{N}}\), namely,_  
\[\mathbf{C}=\mathbf{F_{N}}^{-1}diag(\mathbf{F_{N}}c)\mathbf{F_{N}} \tag{7}\]  
_where \(c\) is the first column of \(\mathbf{C}\), i.e., \(c=[ \begin{array}{cccc}c_{0}&c_{1}&\cdots&c_{N-1}\end{array} ]^{\mathrm{T}}\)._  
From (2), (3) and (9), we have  
\[\left( \begin{array}{c}\lambda_{0}\\ \vdots\\ \lambda_{N-1}\end{array} \right)=\mathbf{F_{N}}\left( \begin{array}{c}c_{0}\\ \vdots\\ c_{N-1}\end{array} \right)=\mathbf{F_{N}}\;c \tag{10}\]  
Using \(\{v_{j}\}_{j=0}^{N-1}\) defined in Equation (8) as column vectors to form a \(N\times N\) matrix \(\mathbf{U_{N}}\)  
\[\mathbf{U_{N}}=[v_{0},v_{1},\cdots,v_{N-1}], \tag{11}\]  
then we have  
\[\mathbf{C}=\mathbf{U_{N}}\left( \begin{array}{ccc}\lambda_{0}&&\\ &\ddots&\\ &&\lambda_{N-1}\end{array} \right)\mathbf{U_{N}}^{*}. \tag{12}\]  
Furthermore, we have \(\mathbf{U_{N}}^{*}=\frac{1}{\sqrt{N}}\mathbf{F_{N}},\mathbf{U_{N}}=\sqrt{N} \mathbf{F_{N}}^{-1}\) from (4), (5) and (11). Then we have  
\[\mathbf{C}=\mathbf{F_{N}}^{-1}diag(\mathbf{F_{N}}c)\mathbf{F_{N}} \tag{13}\]  
**Definition 3**. : **Linear convolution [23]**_: A time-invariant linear operator \(L\) can be represented as a linear convolution. To be specific, we denote by \(\delta[n]\) the discrete Dirac_  
\[\delta[n]= \begin{cases}1&\text{if}\quad n=0\\ 0&\text{if}\quad n\
eq 0\end{cases} .\]  
_Any signal \(f[n]\) can be decomposed as a sum of shifted Diracs:_  
\[f[n]=\sum_{p=-\infty}^{+\infty}f[p]\delta[n-p].\]  
_Let \(L\delta[n]=h[n]\) be the discrete impulse response. Linearity and time invariance implies that_  
\[g[n]=Lf[n]=\sum_{p=-\infty}^{\infty}f[p]h[n-p]:\stackrel{{\text {def}}}{{=}}f\star h[n], \tag{14}\]  
_where \"\(\star\)\" represents linear convolution._  
**Definition 4**. : **Causality and Stability [23]**_: A discrete filter \(L\) is causal if \(Lf[p]\) depends only on the values of \(f[n]\) for \(n\leq p\). The convolution formula (14) implies that \(h[n]=0\) if \(n<0\)._  
_A discrete filter \(L\) is stable if any bounded input signal \(f[n]\) produces a bounded output signal \(Lf[n]\). One can verify that the filter is stable if and only if \(h\in l^{1}(\mathbb{Z})\)._  
**Proposition 1**. : _Assume that the length of \(f\) and \(h\) are finite.