Finite pseudo-differential operators

Abstract

Pseudo-differential operators on ${\mathbb {Z}}^N$ are introduced. We give the matrix representations with respect to the Fourier basis and the unit impulse basis. Traces of these operators are computed.

1 Introduction

Let $f$ be a signal in $L^{2}({\mathbb {R}}^{n})$. Then the Fourier transform $\hat{f}$ of $f$ is defined by

$$\begin{aligned} \hat{f}(\xi )=(2\pi )^{-n/2}\int _{{\mathbb {R}}^{n}}e^{-ix\times \xi }f(x)\,dx,\quad \xi \in {\mathbb {R}}^{n}. \end{aligned}$$

The Fourier inversion formula gives us back the signal $f$ via

$$\begin{aligned} f(x)=(2\pi )^{-n/2}\int _{{\mathbb {R}}^{n}}e^{ix\times \xi } \hat{f}(\xi )\,d\xi ,\quad x\in {\mathbb {R}}^{n}. \end{aligned}$$

This is the basis for pseudo-differential operators on ${\mathbb {R}}^{n}$ or sometimes referred to as time-varying filters. Indeed, let $\sigma$ be a suitable function on ${\mathbb {R}}^{n}\times {\mathbb {R}}^{n}$. Then the pseudo-differential operator $T_\sigma$ is defined by

$$\begin{aligned} (T_\sigma f)(x)=(2\pi )^{-n/2}\int _{{\mathbb {R}}^{n}}e^{ix\times \xi }\sigma (x,\xi )\,\hat{f}(\xi )\,d\xi ,\quad x\in {\mathbb {R}}^{n}. \end{aligned}$$

In the case when $\sigma$ is identically equal to 1, then $T_\sigma$ is the identity in view of the Fourier inversion formula. Pseudo-differential operators have been used in quantizations and time-frequency analysis. Their usefulness notwithstanding, these operators are difficult to work with because of the convergence of the integrals. Moreover, useful information such as eigenvalues is difficult or even impossible to compute. So, it is desirable to obtain finite analogs of pseudo-differential operators. First of all, in applications the numerical implementations of pseudo-differential operators require a finite setting. Secondly, finite pseudo-differential operators are finite-dimensional matrices of which the entries are given by the finite Fourier transforms defined in Sect. 2. Thus, the computations of the eigenvalues can be performed using the fast Fourier transforms and available algorithms. Furthermore, issues like $L^{{\mathrm {p}}}$-boundedness, which pseudo-differential operators have to deal with all the time, are irrelevant to finite pseudo-differential operators. In this paper, we are particularly interested in constructing such operators on $L^{2}({\mathbb {Z}}_{N})$, where ${\mathbb {Z}}_{N}$ is the discretization of a circle. These operators are discrete analogs of pseudo-differential operators on the unit circle ${\mathbb {S}}^1$ with center at the origin, which have been studied in [2, 3]. Pseudo-differential operators on the torus $\prod _{j=1}^n{\mathbb {S}}^1$ are routine extensions of the ones on ${\mathbb {S}}^1$.

2 Finite Fourier transforms

The starting point is the additive group ${\mathbb {Z}}_{N}= \{0, 1, \ldots , N-1\}$, where $N$ is a positive integer greater than or equal to 2 and the group law is addition modulo $N$. It is an abelian group of order $n$ and it is cyclic, which may be viewed as the multiplicative group of $n$-th roots of unity and can be drawn as $n$ equally spaced points on a unit circle. Thus ${\mathbb {Z}}_{N}$ is a finite analog of the circle. A function $z: {\mathbb {Z}}_{N}\rightarrow {\mathbb {C}}$ is completely specified by $z = \left( \begin{array}{c} z(0) \\ z(1) \\ \vdots \\ z(N-1)\end{array} \right)$. We can think of the set of all $n$-tuples with complex entries as functions on ${\mathbb {Z}}_{N}$ and we denote it by $L^{2}({\mathbb {Z}}_{N})$. The inner product and norm in $L^{2}({\mathbb {Z}}_{N})$ are given by

$$\begin{aligned} (z,w) = \sum _{n=0}^{N-1} z(n) \overline{w(n)} \end{aligned}$$

and

$$\begin{aligned} ||z||^2 = (z,z)=\sum _{n=0}^{N-1} |z(n)|^2 \end{aligned}$$

for all $z = \left( \begin{array}{c} z(0) \\ z(1) \\ \vdots \\ z(N-1)\end{array} \right)$ and $w = \left( \begin{array}{c} w(0) \\ w(1) \\ \vdots \\ w(N-1)\end{array} \right)$ in $L^{2}({\mathbb {Z}}_{N})$.

An obvious orthonormal basis for $L^{2}({\mathbb {Z}}_{N})$ is $\{\epsilon _0,\epsilon _1,\ldots ,\epsilon _{N-1} \}$, where

$$\begin{aligned} \epsilon _m = \left( \begin{array}{c} 0 \\ 0 \\ \vdots \\ 1 \\ \vdots \\ 0 \end{array} \right) , {\quad } m = 0,1, \ldots ,N-1, \end{aligned}$$

and $\epsilon _m$ has 1 in the $m$th position and zeros elsewhere. Another orthonormal basis for $L^{2}({\mathbb {Z}}_{N})$ is $\{e_0,e_1,\ldots ,e_{N-1}\}$, where

$$\begin{aligned} e_m = \left( \begin{array}{c} e_m(0) \\ e_m(1) \\ \vdots \\ e_m(N-1)\end{array} \right) , {\quad } m = 0,1, \ldots ,N-1, \end{aligned}$$

and

$$\begin{aligned} e_m(n) = \frac{1}{\sqrt{N}} e^{2\pi i mn/N},{\quad } n = 0,1, \ldots ,N-1. \end{aligned}$$

Definition 2.1

Let $z \in L^{2}({\mathbb {Z}}_{N})$. Then we let $\hat{z} \in L^{2}({\mathbb {Z}}_{N})$ be defined by

$$\begin{aligned} \hat{z} = \left( \begin{array}{c} \hat{z}(0) \\ \hat{z}(1) \\ \vdots \\ \hat{z}(N-1)\end{array} \right) , \end{aligned}$$

where

$$\begin{aligned} \hat{z}(m) = \sum _{n = 0}^{N-1} z(n) e^{-2\pi i mn/N}, {\quad } m = 0, 1, \ldots , N-1. \end{aligned}$$

We call $\hat{z}$ the finite Fourier transform of $z$.

Of particular importance to us is the following inversion formula,

Theorem 2.2

Let $z$ and $\hat{z}$ be in $L^{2}({\mathbb {Z}}_{N})$. Then

$$\begin{aligned} z(n) = \frac{1}{N} \sum _{m = 0}^{N-1} \hat{z}(m) e^{2\pi i mn/N}, {\quad } n = 0, 1, \ldots , N-1. \end{aligned}$$

To simplify the Fourier inversion formula in Theorem 2.2, we define

$$\begin{aligned} F_m = \left( \begin{array}{c} F_m(0) \\ F_m(1) \\ \vdots \\ F_m(N-1)\end{array} \right) ,{\quad } m = 0, 1, \ldots , N-1, \end{aligned}$$

in $L^{2}({\mathbb {Z}}_{N})$, where

$$\begin{aligned} F_m(n) = \frac{1}{N} e^{2\pi i mn/N}, {\quad } n = 0, 1, \ldots , N-1. \end{aligned}$$

(2.1)

Obviously, $\{F_0, F_1, \ldots , F_{N-1}\}$ is orthogonal, but not orthonormal in $L^{2}({\mathbb {Z}}_{N})$. Being an orthogonal set of $N$ elements in the $N$-dimensional vector space $L^{2}({\mathbb {Z}}_{N})$, $\{F_0, F_1, \ldots , F_{N-1}\}$ is a basis for $L^{2}({\mathbb {Z}}_{N})$ and we call it the Fourier basis for $L^{2}({\mathbb {Z}}_{N})$. By Theorem 2.2, we get for $k =0,1,\ldots ,N-1$,

$$\begin{aligned} F_k =\sum _{m=0}^{N-1} \widehat{F_k}(m)F_m. \end{aligned}$$

Therefore

$$\begin{aligned} \widehat{F_k}(m) = {\left\{ \begin{array}{ll} 1, &{} k=m, \\ 0, &{} k\ne m, \end{array}\right. } \end{aligned}$$

and

$$\begin{aligned} \widehat{F_k}(m) = \epsilon _m. \end{aligned}$$

Using the Fourier basis for $L^{2}({\mathbb {Z}}_{N})$ defined in (2.1), the Fourier inversion formula in Theorem 2.2 becomes

$$\begin{aligned} z = \sum _{m = 0}^{N-1} \hat{z}(m) F_m. \end{aligned}$$

(2.2)

Details on the results in this section can be found in [5].

3 Pseudo-differential operators

Now we look at Theorem 2.2 more carefully in the perspective of representation theory. Since ${\mathbb {Z}}_{N}$ is an abelian group with respect to addition modulo $N$, it follows that the irreducible and unitary representations of ${\mathbb {Z}}_{N}$ are one-dimensional. In fact, they are given by the elements in orthonormal basis $\{e_0,e_1,\ldots ,e_{N-1}\}$ for $L^{2}({\mathbb {Z}}_{N})$, which can then be identified with ${\mathbb {Z}}_{N}$. Thus, the dual group of ${\mathbb {Z}}_{N}$ is the group ${\mathbb {Z}}_{N}$ itself. We can now give the definition of pseudo-differential operators on the group ${\mathbb {Z}}_{N}$.

Let $\sigma$ be a function on the phase space ${\mathbb {Z}}_{N}\times {\mathbb {Z}}_{N}$. Then $T_{\sigma }$, the pseudo-differential operator on ${\mathbb {Z}}_{N}$ corresponding to the symbol $\sigma$, is defined by

$$\begin{aligned} (T_{\sigma }z)(n) = \sum _{m = 0}^{N-1} \sigma (n,m) \hat{z}(m) F_m(n), \end{aligned}$$

for all $z \in L^{2}({\mathbb {Z}}_{N})$, where

$$\begin{aligned} \hat{z}(m) = \sum _{n = 0}^{N-1} z(n) e^{-2\pi i mn/N}, {\quad } m = 0, 1, \ldots , N-1. \end{aligned}$$

3.1 Matrix representations

We give the matrix of the pseudo-differential operator $T_{\sigma } :L^{2}({\mathbb {Z}}_{N}) \rightarrow L^{2}({\mathbb {Z}}_{N})$ with respect to the Fourier basis $\{F_0, F_1, \ldots , F_{N-1}\}$ for $L^{2}({\mathbb {Z}}_{N})$.

For $k = 0,1,\ldots ,N-1$, we get

$$\begin{aligned} (T_{\sigma }F_k)(n)= & {} \frac{1}{N} \sum _{m = 0}^{N-1} \sigma (n,m) \widehat{F_k}(m) e^{2\pi imn/N}\\= & {} \frac{1}{N} \sigma (n,k) e^{2\pi ikn/N}\\= & {} \sigma (n,k) F_k(n) \end{aligned}$$

for $n= 0, 1, \ldots , N-1$. Denoting the Fourier transform of $\sigma$ with respect to the first variable by $\mathcal {F}_1\sigma$, we get by Theorem 2.2

$$\begin{aligned} (T_{\sigma }F_k)(n)= & {} \sum _{j = 0}^{N-1} \mathcal {F}_1\sigma (j,k) F_j(n) F_k(n) \\= & {} \frac{1}{N^2} \sum _{j = 0}^{N-1} \mathcal {F}_1\sigma (j,k) e^{2\pi i(j+k)n/N} \end{aligned}$$

for $n= 0, 1, \ldots , N-1$. Changing the summation index $j$ to $m$ by means of the equation $j+k=m$, and using the periodicity of $\sigma$ with respect to the first variable,

$$\begin{aligned} (T_{\sigma }F_k)(n)= & {} \frac{1}{N^2} \sum _{m = k}^{N-1+k} \mathcal {F}_1\sigma (m-k,k) e^{2\pi imn/N}\\= & {} \frac{1}{N^2} \sum _{m = 0}^{N-1} \mathcal {F}_1\sigma (m-k,k) e^{2\pi imn/N}\\= & {} \frac{1}{N} \sum _{m = 0}^{N-1} \mathcal {F}_1\sigma (m-k,k) F_m(n) \end{aligned}$$

for $n= 0, 1, \ldots , N-1$.

$$\begin{aligned} T_{\sigma }F_n = \frac{1}{N} \sum _{m = 0}^{N-1} \mathcal {F}_1\sigma (m-n,n) F_m, {\quad }n= 0, 1, \ldots , N-1. \end{aligned}$$

So the matrix $(T_{\sigma })_F$ of the pseudo-differential operator $T_{\sigma }$ with respect to the Fourier basis is given by

$$\begin{aligned}&(T_{\sigma })_F\\&\quad = \frac{1}{N}\left( \begin{array}{ccc} (\mathcal {F}_1\sigma )(0-0,0) &{} \ldots &{} (\mathcal {F}_1\sigma )(0-(N-1),0) \\ (\mathcal {F}_1\sigma )(1-0,1) &{} \ldots &{} (\mathcal {F}_1\sigma )(1-(N-1),1)\\ \vdots &{} \vdots &{} \vdots \\ (\mathcal {F}_1\sigma )((N-1)-0,N-1) &{} \ldots &{} (\mathcal {F}_1\sigma )((N-1)-(N-1)),(N-1)) \end{array} \right) \\&\quad = \frac{1}{N}\left( \begin{array}{cccc} (\mathcal {F}_1\sigma )(0,0) &{} (\mathcal {F}_1\sigma )(N-1,0) &{} \ldots &{} (\mathcal {F}_1\sigma )(1,0) \\ (\mathcal {F}_1\sigma )(1,1) &{} (\mathcal {F}_1\sigma )(0,1) &{} \ldots &{} (\mathcal {F}_1\sigma )(2,1)\\ \vdots &{} \vdots &{} \vdots &{} \vdots \\ (\mathcal {F}_1\sigma )(N-1,N-1) &{} (\mathcal {F}_1\sigma )(N-2,N-1) &{} \ldots &{} (\mathcal {F}_1\sigma )(0,N-1) \end{array} \right) \\&\quad =\frac{1}{N}(\mathcal {F}_1\sigma (m-n,n))_{0\le m,n\le N-1}. \end{aligned}$$

Similarly, we give the matrix of the pseudo-differential operator $T_{\sigma } :L^{2}({\mathbb {Z}}_{N}) \rightarrow L^{2}({\mathbb {Z}}_{N})$ with respect to the unit impulse basis $\{\epsilon _0,\epsilon _1,\ldots ,\epsilon _{N-1} \}$.

For $k = 0,1,\ldots ,N-1$, we get

$$\begin{aligned} (T_{\sigma }\epsilon _k)(n)= & {} \sum _{m = 0}^{N-1} \sigma (n,m) \widehat{\epsilon _k}(m) F_m(n)\\= & {} \frac{1}{N} \sigma (n,k) \widehat{\epsilon _k}(m) e^{2\pi imn/N}. \end{aligned}$$

The entries of the matrix denoted by $[a_{lk}]$ is computed

$$\begin{aligned} (T_{\sigma }\epsilon _k, \epsilon _l)= & {} \sum _{n = 0}^{N-1} \sum _{m = 0}^{N-1} \sigma (n,m) \widehat{\epsilon _k}(m) F_m(n)\overline{\epsilon _l}\\= & {} \frac{1}{N} \sum _{n = 0}^{N-1} \sum _{m = 0}^{N-1} \sigma (n,m) \widehat{\epsilon _k}(m) e^{2\pi imn/N}\overline{\epsilon _l}(n), \end{aligned}$$

where $l$ is the row index and $k$ is the column index in the matrix.

Since $\epsilon _k$ has 1 in the $k$th position and zeros elsewhere,

$$\begin{aligned} \widehat{\epsilon _k}(m)= & {} \sum _{n = 0}^{N-1} \epsilon _k(n)e^{-2\pi imn/N}\\= & {} e^{-2\pi ikm/N}. \end{aligned}$$

Hence, denoting the Fourier transform of $\sigma$ with respect to the second variable by $\mathcal {F}_2\sigma$

$$\begin{aligned} a_{lk}= & {} (T_{\sigma }\epsilon _k, \epsilon _l) = \frac{1}{N} \sum _{n = 0}^{N-1} \sum _{m = 0}^{N-1} \sigma (n,m) e^{-2\pi ikm/N} e^{2\pi imn/N}\overline{\epsilon _l}(n) \nonumber \\= & {} \frac{1}{N} \sum _{m = 0}^{N-1} \sigma (l,m) e^{-2\pi i(k-l)m/N}\nonumber \\= & {} \frac{1}{N} (\mathcal {F}_2\sigma )(l,k-l). \end{aligned}$$

(3.1)

The matrix $(T_{\sigma })_{IU}$ of the pseudo-differential operator $T_{\sigma }$ with respect to the unit impulse basis is given by

$$\begin{aligned}&(T_{\sigma })_{UI}\\&\quad = \frac{1}{N}\left( \begin{array}{cccc} (\mathcal {F}_2\sigma )(0,0) &{} (\mathcal {F}_2\sigma )(0,1) &{} \ldots &{} (\mathcal {F}_2\sigma )(0,N-1) \\ (\mathcal {F}_2\sigma )(1,N-1) &{} (\mathcal {F}_2\sigma )(1,0) &{} \ldots &{} (\mathcal {F}_2\sigma )(1,N-2)\\ \vdots &{} \vdots &{} \vdots &{} \vdots \\ (\mathcal {F}_2\sigma )(N-1,1) &{} (\mathcal {F}_2\sigma )(N-1,2) &{} \ldots &{} (\mathcal {F}_2\sigma )(N-1,0) \end{array} \right) , \end{aligned}$$

where $l,k = 0, 1, \ldots , N-1$.

3.2 Trace of the pseudo-differential operator $T_{\sigma }$

Using the matrices hitherto computed, we can obtain the explicit eigenvalues using MATLAB or other softwares [1, 4]. But we are still interested in computing the trace of a finite pseudo-differential operator in order to see that the formulas are compatible with the ones for pseudo-differential operators on ${\mathbb {R}}^{n}$ under suitable conditions on the symbols. The beauty of the finite analogs is that no restrictions on the symbols are required.

The trace of $T_{\sigma }$, which is independent from the choice of the bases, can be computed as follows.

Theorem 3.1

Let $\sigma$ be a symbol in $L^{2}({\mathbb {Z}}_{N}\times {\mathbb {Z}}_{N})$. Then the trace $\mathrm {tr}(T_{\sigma })$ of the linear operator $T_{\sigma }$ associated with the symbol $\sigma$ is given by

$$\begin{aligned} \mathrm {tr}(T_{\sigma }) = \frac{1}{N} \sum _{n = 0}^{N-1}\sum _{m = 0}^{N-1} \sigma (n,m). \end{aligned}$$

Proof

Let $\{\varphi _0, \varphi _1,\ldots , \varphi _{N-1}\}$ be any orthonormal basis for $L^{2}({\mathbb {Z}}_{N})$. Then

$$\begin{aligned} \mathrm {tr}(T_{\sigma })= & {} \sum _{j = 0}^{N-1} (T_{\sigma }\varphi _j,\varphi _j)\\= & {} \sum _{j = 0}^{N-1} \sum _{n = 0}^{N-1}\sum _{m = 0}^{N-1}\sigma (n,m) \hat{z}(m) F_m(n)\bar{\varphi }_j(n). \end{aligned}$$

Since

$$\begin{aligned} \hat{z}(m) = N (z,F_m) \end{aligned}$$

and

$$\begin{aligned} F_m(n)= & {} \sum _{j = 0}^{N-1} (F_m, \varphi _j)\varphi _j(n),\\ \mathrm {tr}(T_{\sigma })= & {} \sum _{j = 0}^{N-1} \sum _{n = 0}^{N-1}\sum _{m = 0}^{N-1}\sigma (n,m) N (\varphi _j, F_m) F_m(n)\bar{\varphi }_j(n)\\= & {} \sum _{n = 0}^{N-1}\sum _{m = 0}^{N-1}\sigma (n,m) N F_m(n) \sum _{j = 0}^{N-1}(\varphi _j, F_m) \bar{\varphi }_j(n)\\= & {} \sum _{n = 0}^{N-1}\sum _{m = 0}^{N-1}\sigma (n,m) N F_m(n) \overline{ \sum _{j = 0}^{N-1}(F_m,\varphi _j) \varphi _j(n)}\\= & {} \sum _{n = 0}^{N-1}\sum _{m = 0}^{N-1}\sigma (n,m) N F_m(n)\bar{F}_m(n)\\= & {} N \sum _{n = 0}^{N-1}\sum _{m = 0}^{N-1}\sigma (n,m) |F_m(n)|^2\\= & {} \frac{1}{N} \sum _{n = 0}^{N-1}\sum _{m = 0}^{N-1}\sigma (n,m). \end{aligned}$$

This completes the proof. $\square$

Another way to calculate the trace of $T_{\sigma }$ is to sum the diagonal entries of the matrix in (3.1), i.e. when $l=k$.

$$\begin{aligned} \mathrm {tr}(T_{\sigma })= & {} \frac{1}{N} \sum _{l = 0}^{N-1} \sum _{m = 0}^{N-1} \sigma (l,m) e^{-2\pi i(k-l)m/N}\\= & {} \frac{1}{N} \sum _{l = 0}^{N-1} \sum _{m = 0}^{N-1} \sigma (l,m). \end{aligned}$$

Obviously, the trace is the summation of the chosen symbol.