Open access peer-reviewed chapter

Computation of Two-Dimensional Fourier Transforms for Noisy Band-Limited Signals

By Weidong Chen

Submitted: June 26th 2018Reviewed: September 16th 2018Published: July 24th 2019

DOI: 10.5772/intechopen.81542

Downloaded: 44

Abstract

The computation of the two-dimensional Fourier transform by the sampling points creates an ill-posed problem. In this chapter, we will cover this problem for the band-limited signals in the noisy case. We will present a regularized algorithm based on the two-dimensional Shannon Sampling Theorem, the two-dimensional Fourier series, and the regularization method. First, we prove the convergence property of the regularized solution according to the maximum norm. Then an error estimation is given according to the L2-norm. The convergence property of the regularized Fourier series is given in theory, and some examples are given to compare the numerical results of the regularized Fourier series with the numerical results of the Fourier series.

Keywords

  • Fourier transform
  • band-limited signal
  • ill-posedness
  • regularizationAMS subject classifications: 65T40
  • 65R20
  • 65R30
  • 65R32

1. Introduction

The two-dimensional Fourier transform is widely applied in many fields [1, 2, 3, 4, 5, 6, 7, 8, 9]. In this chapter, the ill-posedness of the problem for computing two-dimensional Fourier transform is analyzed on a pair of spaces by the theory and examples in detail. A two-dimensional regularized Fourier series is presented with the proof of the convergence property and some experimental results.

First, we describe the band-limited signals.

Definition. For two positive Ω1, Ω2R, a function fL2R2is said to be band-limited if

f̂ω1ω2=0,ω1ω2R2\Ω1Ω1×Ω2Ω2.

Here f̂is the Fourier transform of:

Ffω1ω2=f̂ω1ω2=ft1t2eit1ω1+it2ω2dt1dt2,ω1ω2R2.E1

We will consider the problem of computing f̂ω1ω2from ft1t2.

For band-limited signals, we have the following sampling theorem [4, 10, 11]. For the two-dimensional band-limited function above, we have

ft1t2=n1=n2=fn1H1n2H2sinΩ1t1n1H1Ω1t1n1H1sinΩ2t2n2H2Ω2t2n2H2,E2

where H1π/Ω1and H2π/Ω2.

Calculating the Fourier transform of ft1t2by the formula (2), we have the formula which is same as the Fourier series

f̂ω1ω2=H1H2n1=n2=fn1H1n2H2ein1H1ω1+in2H2ω2PΩω1ω2,E3

where PΩω1ω2=1Ω1Ω1×Ω2Ω2(ω1, ω2) is the characteristic function of Ω1Ω1×Ω2Ω2.

In many practical problems, the samples fn1H1n2H2are noisy:

fn1H1n2H2=fTn1H1n2H2+ηn1H1n2H2,E4

where ηn1H1n2H2is the noise

ηn1H1n2H2δ,E5

and fTL2is the exact band-limited signal.

The noise in the two-dimensional case is discussed in [5, 6], and the Tikhonov regularization method is used. However, there is too much computation in the Tikhonov regularization method since the solution of an Euler equation is required.

The ill-posedness in the one-dimensional case is considered in [12, 13]. The regularized Fourier series

f̂αω=Hn=fnHeinHω1+2πα+2παn1H12PΩω

in [12] is given based on the regularized Fourier transform

Fαf=fteiωtdt1+2πα+2παt2

in [14]. The regularized Fourier transform was found by finding the minimizer of the Tikhonov’s smoothing functional.

In this chapter, we will find a reliable algorithm for this ill-posed problem using a two-dimensional regularized Fourier series. In Section 2, the ill-posedness is discussed in the two-dimensional case. In Section 3, the regularized Fourier series and the proof of the convergence property are given. The bias and variance of regularized Fourier series are given in Section 4. The algorithm and the experimental results of numerical examples are given in Section 5. Finally, the conclusion is given in Section 6.

2. The ill-posedness

We will first study the ill-posedness of the problem (3) in the noisy case (4). The concept of ill-posed problems was introduced in [15]. Here we borrow the following definition from it.

Definition 2.1 Assume A:DUis an operator in which Dand Uare metric spaces with distances ρDand ρU, respectively. The problem

Az=u.E6

of determining a solution zin the space Dfrom the “initial data” uin the space Uis said to be well-posed on the pair of metric spaces DUin the sense of Hadamard if the following three conditions are satisfied:

  1. For every element uU, there exists a solution zin the space D; in other words, the mapping Ais surjective.

  2. The solution is unique; in other words, the mapping Ais injective.

  3. The problem is stable in the spaces DU:>0,δ>0, such that

    ρUu1u2<δρDz1z2<.

In other words, the inverse mapping A1is uniformly continuous. Problems that violate any of the three conditions are said to be ill-posed.

In this section, we discuss the ill-posedness of Af̂=fon the pair of Banach spaces (L2Ω1Ω1×Ω2Ω2,l(Z2)), where f̂ω1ω2is given by the Fourier series in Eq. (3).

The operator Ain Eq. (6) is defined by the following formula:

Af̂=f,E7

where =fn1H1n2H2:n1Zn2Z.

As usual, lis the space an:nZ2of bounded sequences. The norm of lis defined by

al=supnZ2an,

where

  1. The existence condition is not satisfied.

  2. The uniqueness condition is satisfied.

  3. The stability condition is not satisfied. The proof is similar to the proof in [10].

3. The regularized Fourier series

Based on the one-dimensional regularized Fourier series in [12], we construct the two-dimensional regularized Fourier series:

f̂αω1ω2=H1H2n1=n2=fn1H1n2H2ein1H1ω1+in2H2ω21+2πα+2παn1H121+2πα+2παn2H22PΩω1ω2,E8

where fn1H1n2H2is given in (4). We will give the convergence property of the regularized Fourier series in this section.

Lemma 3.1

F11+2πα+2παt2sinΩtnHΩtnH=H1+2πα+2παnH2einHωH4πaα1neaωΩainH+eaω+Ωa+inH,E9

where a1+2πα2πα.

Proof.

F11+2πα+2παt2sinΩtnHΩtnH=12πF11+2πα+2παt2FsinΩtnHΩtnH=12π12eaωHeiωnHPΩω=H14πaαeaueinHωu1ωΩω+Ωudu=H14πaαeinHωωΩω+ΩeauinHudu=H14πaαeinHωωΩ0eauinHudu+0ω+ΩeauinHudu=H14πaαeinHω1ainHeainHωΩainH+1a+inHea+inHω+Ωa+inH=H14πaαeinHω1ainH+1a+inHH14πaαeinHωeainHωΩainH+ea+inHω+Ωa+inH=H12παeinHωa2+nH2H14πaαeinHω1neaωΩinHωainH+eaω+ΩinHωa+inH=HeinHω1+2πα+2παnH2H14πaα1neaωΩainH+eaω+Ωa+inH.

Lemma 3.2 For any band-limited function gt1t2and ω1ω2Ω1Ω1×Ω2Ω2

gt1t2eit1ω1+it2ω2dt1dt21+2πα+2παt121+2πα+2παt22=H1H2n1=n2=gn1H1n2H2ein1H1ω1+in2H2ω2[1+2πα+2παn1H1)2[1+2πα+2παn2H2)2H1H2n1=n2=gn1H1n2H2ein1H1ω11+2πα+2παn1H121n24πaαeaω2Ω2ain2H2+eaω2+Ω2a+in2H2H1H2n1=n2=gn1H1n2H2ein2H2ω21+2πα+2παn2H221n14πaαeaω1Ω1ain1H1+eaω1+Ω1a+in1H1+H1H2n1=n2=gn1H1n2H21n1+n24πaα2eaω1Ω1ain1H1+eaω1+Ω1a+in1H1·eaω2Ω2ain2H2+eaω2+Ω2a+in2H2.E10

Proof. By the sampling theorem

Igt1t2eit1ω1+it2ω2dt1dt21+2πα+2παt121+2πα+2παt22=eit1ω1+it2ω21+2πα+2παt121+2πα+2παt22·n1=n2=gn1H1n2H2sinΩ1t1n1H1Ω1t1n1H1sinΩ2t2n2H2Ω2t2n2H2dt1dt2=n1=n2=gn1H1n2H211+2πα+2παt12sinΩ1t1n1H1Ω1t1n1H1eit1ω1dt1·11+2πα+2παt22sinΩ2t2n2H2Ω2t2n2H2eit2ω2dt2

By Lemma 3.1 and the FOIL method, Eq. (10) is true.

Lemma 3.3 For each arbitrarily small c>0and ωΩ+cΩc,

n=eaωΩainH+eaω+Ωa+inH2=Oe2aca.E11

Proof. By the inequality a+b22a2+b2,

n=eaωΩainH+eaω+Ωa+inH22n=eaωΩainH2+eaω+Ωa+inH24n=e2aca2+nH24He2acdxa2+x2+4a2e2ac=4πe2acHa+4a2e2ac.

Lemma 3.4 For each arbitrarily small c>0and ω1ω2Ω1+cΩ1c×Ω2+cΩ2c,

n1=n2=gn1H1n2H21n1+n24πaα2eaω1Ω1ain1H1+eaω1+Ω1a+in1H1eaω2Ω2ain2H2+eaω2+Ω2a+in2H2,=Oae2ac.E12

for α+0and gthat is Ω-band-limited.

Proof. By the Cauchy inequality,

n1=n2=gn1H1n2H2eaω1Ω1ain1H1+eaω1+Ω1a+in1H1eaω2Ω2ain2H2+eaω2+Ω2a+in2H22n1=n2=gn1H1n2H22n1=n2=eaω1Ω1ain1H1+eaω1+Ω1a+in1H1eaω2Ω2ain2H2+eaω2+Ω2a+in2H22,

where n1=n2=gn1H1n2H22is bounded by Parseval equality, and

n1=n2=eaω1Ω1ain1H1+eaω1+Ω1a+in1H1eaω2Ω2ain2H2+eaω2+Ω2a+in2H22=n1=eaω1Ω1ain1H1+eaω1+Ω1a+in1H12n2=eaω1Ω1ain1H1+eaω1+Ω1a+in1H12.

By Lemma 3.3, Eq. (12) is true.

Lemma 3.5

n=11+2πα+2παnH22=O1α.E13

Proof.

n=11+2πα+2παnH2211+2πα2+n011+2πα+2παnH22,

where

n011+2πα+2παnH222n=111+2πα+2παnH222H0dx1+2πα+2παx22=O1α.

So

n=11+2πα+2παnH22=O1α.

Lemma 3.6 For each arbitrarily small c>0and ω1ω2Ω1+cΩ1c×Ω2+cΩ2c,

n1=n2=gn1H1n2H2ein1H1ω11+2πα+2παn1H121n24πaαeaω2Ω2ain2H2+eaω2+Ω2a+in2H2=Oa12eac,E14

for α+0and gthat is Ω-band-limited.

Proof. By Cauchy inequality,

n1=n2=gn1H1n2H2ein1H1ω11+2πα+2παn1H12eaω2Ω2ain2H2+eaω2+Ω2a+in2H22n1=n2=gn1H1n2H22n1=n2=ein1H1ω11+2πα+2παn1H12eaω2Ω2ain2H2+eaω2+Ω2a+in2H22,

where n1=n2=gn1H1n2H22is bounded by the Parseval equality, and

n1=n2=ein1H1ω11+2πα+2παn1H12eaω2Ω2ain2H2+eaω2+Ω2a+in2H22=n1=ein1H1ω11+2πα+2παn1H122n2=eaω2Ω2ain2H2+eaω2+Ω2a+in2H22.

By Lemma 3.3 and Lemma 3.5 Eq. (14) is true.

Lemma 3.7

n1=n2=ηn1H1n2H2[1+2πα+2παn1H1)2[1+2πα+2παn2H2)2=OδαE15

for δ+0and α+0, where ηand δare given in (4) and (5) in Section 1.

Proof.

n=11+2πα+2παnH1211+2πα+n011+2πα+2παnH12,

where

n011+2πα+2παnH122n=111+2πα+2παnH122H10dx1+2πα+2παx2=O1α.

So

n=11+2πα+2παnH12=O1/α.

For the same reason,

n=11+2πα+2παnH22=O1α.

So Eq. (15) is true.

Theorem 3.1 Suppose fTL1R2L2R2is band-limited. For each arbitrarily small c>0, if we choose α=αδsuch that αδ0and δ/αδ0as δ0, then f̂αω1ω2f̂Tω1ω2uniformly in ω1ω2Ω1+cΩ1c×Ω2+cΩ2cas δ0.

Proof. By Lemma 3.2, Lemma 3.4 and Lemma 3.6, we have

H1H2n1=n2=fTn1H1n2H2[1+2πα+2παn1H1)2[1+2πα+2παn2H2)2ein1H1ω1+in2H2ω2=fTt1t2eit1ω1+it2ω2dt1dt21+2πα+2παt121+2πα+2παt22+Oa12eac.

Therefore,

f̂αω1ω2f̂Tω1ω2=H1H2n1=n2=fTn1H1n2H2+ηn1H1n2H2ein1H1ω1+in2H2ω2[1+2πα+2παn1H1)2[1+2πα+2παn2H2)2PΩω1ω2f̂Tω1ω2=H1H2n1=n2=fTn1H1n2H2ein1H1ω1+in2H2ω2[1+2πα+2παn1H1)2[1+2πα+2παn2H2)2PΩω1ω2f̂Tω1ω2+H1H2n1=n2=ηn1H1n2H2[1+2πα+2παn1H1)2[1+2πα+2παn2H2)2ein1H1ω1+in2H2ω2PΩω1ω2=fTt1t2eit1ω1+it2ω2dt1dt21+2πα+2παt121+2πα+2παt22fTt1t2eit1ω1+it2ω2dt1dt2PΩω1ω2+H1H2n1=n2=ηn1H1n2H2ein1H1ω1+in2H2ω21+2πα+2παn1H121+2πα+2παn2H22PΩω1ω2+Oa12eac.

This implies

f̂αω1ω2f̂T(ω1ω2)4πα+2παt12+2παt22+2πα+2παt122πα+2παt221+2πα+2παt121+2πα+2παt22fTt1t2eit1ω1+it2ω2dt1dt2+H1H2n1=n2=ηn1H1n2H2[1+2πα+2παn1H1)2[1+2πα+2παn2H2)2ein1H1ω1+in2H2ω2+Oa12eac

where

n1=n2=ηn1H1n2H21+2πα+2παn1H121+2πα+2παn2H22ein1H1ω1+in2H2ω2=Oδα.

For any ε>0, there exists M>0such that

t1Mort2MfTt1t2dt1dt2<ε.

Then

4πα+2παt12+2παt22+2πα+2παt122πα+2παt221+2πα+2παt121+2πα+2παt22fTt1t2eit1ω1+it2ω2dt1dt2t1Mandt2M4πα+2παt12+2παt22+2πα+2παt122πα+2παt221+2πα+2παt121+2πα+2παt22fTt1t2eit1ω1+it2ω2dt1dt2+t1Mort2M4πα+2παt12+2παt22+2πα+2παt122πα+2παt221+2πα+2παt121+2πα+2παt22fTt1t2eit1ω1+it2ω2dt1dt2,

where

t1Mort2M4πα+2παt12+2παt22+2πα+2παt122πα+2παt221+2πα+2παt121+2πα+2παt22fTt1t2eit1ω1+it2ω2dt1dt2t1Mort2MfTt1t2dt1dt2<ε

and

t1Mandt2M4πα+2παt12+2παt22+2πα+2παt122πα+2παt221+2πα+2παt121+2πα+2παt22fTt1t2eit1ω1+it2ω2dt1dt20

as α0.

4. Error analysis

In last section we have proved the convergence property of the regularized Fourier series under the condition fTL1R2. In this section, we give the error analysis of the regularized Fourier series according to the L2-norm for the functions fTL2R2. The bound of the variance of the regularized Fourier series is presented.

By Lemma 3.5, we have next lemma.

Lemma 4.1

n1=n2=ηn1H1n2H2[1+2πα+2παn1H1)2[1+2πα+2παn2H2)22=Oδ2+Oδ2α

for δ+0and α+0, where ηand δare given in Eq. (4) and Eq. (5) in Section 1.

Theorem 4.1 Suppose fTL2R2is band-limited. If we choose α=αδsuch that αδ0and δ2/αδ0as δ0, then f̂αω1ω2f̂Tω1ω2in L2Ω1Ω1×Ω2Ω2as δ0.

Proof.

f̂αω1ω2f̂Tω1ω2=H1H2n1=n2=fTn1H1n2H2+ηn1H1n2H2ein1H1ω1+in2H2ω21+2πα+2παn1H121+2πα+2παn2H22PΩω1ω2f̂Tω1ω2=H1H2n1=n2=4πα+2παn1H12+2παn2H22+2πα+2παn1H122πα+2παn2H221+2πα+2παn1H121+2πα+2παn2H22
·fTn1H1n2H2ein1H1ω1+in2H2ω2PΩω1ω2+H1H2n1=n2=ηn1H1n2H21+2πα+2παn1H121+2πα+2παn2H22ein1H1ω1+in2H2ω2PΩω1ω2.

Let

Sω1ω2n1=n2=4πα+2παn1H12+2παn2H22+2πα+2παn1H122πα+2παn2H221+2πα+2παn1H121+2πα+2παn2H22·fTn1H1n2H2ein1H1ω1+in2H2ω2PΩω1ω2.

Then

f̂αω1ω2f̂Tω1ω2L222H12H22Sω1ω22+2H12H22n1=n2=ηn1H1n2H21+2πα+2παn1H121+2πα+2παn2H22ein1H1ω1+in2H2ω2PΩω1ω22,

where

n1=n2=ηn1H1n2H21+2πα+2παn1H121+2πα+2παn2H22ein1H1ω1+in2H2ω2PΩω1ω22=n1=n2=ηn1H1n2H21+2πα+2παn1H121+2πα+2παn2H222=Oδ2α

by Lemma 4.1 and

Sω1ω22=n1=n2=4πα+2παn1H12+2παn2H22+2πα+2παn1H122πα+2παn2H221+2πα+2παn1H121+2πα+2παn2H22·fTn1H1n2H22.

For every ε>0, there exists N>0such that

n1Norn2NfTn1H1n2H22<ϵ,

since

n1=n2=4πα+2παn1H12+2παn2H22+2πα+2παn1H122πα+2παn2H221+2πα+2παn1H121+2πα+2παn2H22·fTn1H1n2H22=n1Nandn2N4πα+2παn1H12+2παn2H22+2πα+2παn1H122πα+2παn2H221+2πα+2παn1H121+2πα+2παn2H22·fTn1H1n2H22+n1>Norn2>N4πα+2παn1H12+2παn2H22+2πα+2παn1H122πα+2παn2H221+2πα+2παn1H121+2πα+2παn2H22·fTn1H1n2H22,

where

n1>Norn2>N4πα+2παn1H12+2παn2H22+2πα+2παn1H122πα+2παn2H221+2πα+2παn1H121+2πα+2παn2H22·fTn1H1n2H22n1Norn2NfTn1H1n2H22<ε

and

n1Nandn2N4πα+2παn1H12+2παn2H22+2πα+2παn1H122πα+2παn2H221+2πα+2παn1H121+2πα+2παn2H22fTn1H1n2H220

as α0.

Therefore,f̂αω1ω2f̂Tω1ω2L220.

Theorem 4.2 Suppose fTL2R2is band-limited. If the noise in Eq. (4) is white noise such that Eηn1H1n2H2=0and Varηn1H1n2H2=σ2, then the bias f̂Tω1ω2Ef̂αω1ω20in L2Ω1Ω1×Ω2Ω2as α0and

Varf̂αω1ω2=Oσ2+Oσ2/α

if ασ0and σ2/ασ0as σ0.

Proof. We can calculate

f̂Tω1ω2Ef̂αω1ω2L22=H12H22·n1=n2=4πα+2παn1H12+2παn2H22+2πα+2παn1H122πα+2παn2H221+2πα+2παn1H121+2πα+2παn2H22·fTn1H1n2H22

and

Varf̂αω1ω2=n1=n2=σ21+2πα+2παn1H1221+2πα+2παn2H222.

By the proof of Theorem 4.1, we can see that f̂Tω1ω2Ef̂αω1ω20in L2Ω1Ω1×Ω2Ω2as α0and Varf̂αω1ω1=Oσ2+Oσ2/α.

5. The algorithm and experimental results

In this section, we give the algorithm and an example to show that the regularized Fourier series is more effective in controlling noise than the Fourier series.

In practical computation, we choose a large integer Nand use the next formula in computation:

f̂αω1ω2=H1H2n1=NNn2=NNfn1H1n2H2ein1H1ω1+in2H2ω21+2πα+2παn1H121+2πα+2παn2H22PΩω1ω2.

Example 1. Suppose

fTt1t2=1cost1πt121cost2πt22.

Then

f̂Tω1ω2=1ω11ω2PΩω1ω2,

where Ω1=1and Ω2=1.

We add the white noise that is uniformly distributed in 0.00050.0005and choose N=20. The exact Fourier transform is in Figure 1. The result of the Fourier series is in Figure 2. The result of the regularized Fourier series with α=0.001is in Figure 3.

Figure 1.

The exact Fourier transform in Example 2.

Figure 2.

The numerical results by Fourier series in Example 2.

Figure 3.

The numerical results by the regularized Fourier series in Example 2.

6. Conclusion

The problem of computing the two-dimensional Fourier transform is highly ill-posed. Noise can give rise to large errors if the Fourier series formula is used. The regularized two-dimensional Fourier series is presented. The convergence property is proved and tested by some examples. The convergence property and numerical results show that the regularized two-dimensional Fourier series is excellent in computation in noisy cases. The algorithm will be useful in image processing and multi-dimensional signal processing. The method will be of interest to: engineers who want higher precision in the gauging and design of function generators and analyzers; the electronic or electrical rectification industry; and also to the mathematics community for computing methods and the improvement of mathematics programs on signals and systems, for example, Simulink; and others since many problems in engineering involve noise.

Acknowledgments

The author would like to express appreciation to Sarah Lanand for her help in formatting the document to meet submission guidelines.

© 2019 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Weidong Chen (July 24th 2019). Computation of Two-Dimensional Fourier Transforms for Noisy Band-Limited Signals, Recent Advances in Integral Equations, Francisco Bulnes, IntechOpen, DOI: 10.5772/intechopen.81542. Available from:

chapter statistics

44total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Electro-magnetic Simulation Based on the Integral Form of Maxwell’s Equations

By Naofumi Kitsunezaki

Related Book

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More about us