# Expansions of Functions Based on Rational Orthogonal Basis with Nonnegative Instantaneous Frequencies

Authors: Xiaona Cui; Suxia Yao
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We consider in this paper expansions of functions based on the rational orthogonal basis for the space of square integrable functions. The basis functions have nonnegative instantaneous frequencies so that the expansions make physical sense. We discuss the almost everywhere convergence of the expansions and develop a fast algorithm for computing the coefficients arising in the expansions by combining the characterization of the coefficients with the fast Fourier transform.


---

## Body

## 1. Introduction

A common approach for understanding a function is to expand it as a sum of basic functions. These basic functions should be chosen for different practical purpose. In the time-frequency analysis, the instantaneous frequency is one of the most important information for understanding a given signal. Then the basic functions used to express a complicated signal are expected to have nonnegative instantaneous frequencies so that the expansion of a signal makes physical sense. In this point of view, recent works have contributed to characterize and construct the basic functions [1–7] and establish numerical algorithms for decomposing a signal based on the basic functions [8–10].Motivated by the analytic signal approach [11, 12], the authors in [7] constructed rational orthogonal basis for L2(R), the space of square integrable functions on R, with each element of the basis enjoying physically meaningful instantaneous frequency. Specifically, let N denote the set of all positive integers. The sequence ψn, |n|∈N, forms an orthogonal basis for L2(R), where for each n∈N(1)ψ2n-1(x)∶=-x1+x2(x-ix+i)2n-1,x∈R,ψ2n(x)∶=-11+x2(x-ix+i)2n-1,x∈R,
and for each -n∈N, ψn∶=ψ-n¯. As pointed out in [7], the basis functions all have nonnegative instantaneous frequencies in the sense of the analytic signal. Based upon this basis, we focus in this paper on decomposing a function in L2(R) into a sum of the basis functions ψn, |n|∈N. For simplicity, we first transform the basis into an orthonormal one by normalization. A direct computation shows that there holds, for each n∈N,
(2)∫R‍|ψ2n-1(x)|2dx=∫R‍x2(1+x2)2dx=π2,∫R‍|ψ2n(x)|2dx=∫R‍1(1+x2)2dx=π2.
Hence, we obtain the resulting orthonormal basis {ϕn:|n|∈N} for L2(R), where
(3)ϕn∶=2πψn,|n|∈N.
In fact, due to the completeness of {ϕn,|n|∈N} in L2(R), each f∈L2(R) can be represented as the infinite series
(4)∑|n|∈N‍dn(f)ϕn,
where the coefficients are defined by
(5)dn(f)∶=∫R‍f(x)ϕn(x)¯dx,|n|∈N.
However, for practical purpose, one often needs to decompose a function into a finite sum of basic functions. Thus, we have to approximate a function f∈L2(R) by the partial sum of the series (4) defined by
(6)SN(f)(x)∶=∑|n|=1N‍dn(f)ϕn(x),x∈R.
From this point of view, we have to deal with two issues. The first one is to study the convergence of the partial sum (6) as N tends to infinity. Since it is known that the sequence of the partial sums converges to f in the sense of norm, we will aim in this paper at discussing the almost everywhere convergence of them. The second one is to develop a fast algorithm for computing the partial sum so that this type of decomposition can be carried out in practical applications.The organization of this paper is as follows. In Section2, we establish the relation between the coefficients in (5) and the classical Fourier coefficients and then discuss the almost everywhere convergence of the sequence of the partial sums in (6). We develop in Section 3 an algorithm for computing the coefficients in the expansion (6) by employing the relation between the coefficients and the classical Fourier coefficients and the fast Fourier transform. To show that the proposed algorithm is fast, we also give an estimate of its computational complexity.


## 2. Almost Everywhere Convergence

We discuss in this section the almost everywhere convergence of the sequenceSN(f), N∈N. This will be done by making use of some classical results about the Fourier series. To this end, with respect to any f∈Lp(R), 1≤p<∞, a periodic function is introduced as follows.Letσ:R→(0,2π) be defined by
(7)σ(x)=2arctan(x)+π,x∈R.
Then σ′(x)=2/(x2+1)>0, x∈R means σ is a one-to-one mapping from R onto (0,2π). Then for any f∈Lp(R), 1≤p<∞, we set
(8)fp(t)∶=f(σ-1(t))(1-eit)2,fq(t)∶=f(σ-1(t)),mmmmmmmmmmmmmmmmmt∈(0,2π),
where σ-1(t)=tan((t-π)/2)=-i(eit+1)/(eit-1). The following lemma gives a desired properties of the functions fp and fq.Lemma 1.
Letp∈[1,+∞). If f∈Lp(R) satisfies
(9)∫R‍|f(x)|p(1+x2)p-1dx<∞,
then fp,fq∈Lp(0,2π).Proof.
Taking the change of variablesx=σ-1(t), we have
(10)∫02π‍|fp(t)|pdt=∫02π|f(σ-1(t))(1-eit)2|pdt=14p-1∫R‍|f(x)|p(1+x2)p-1dx.
Similarly, for the function fq, we get
(11)∫02π‍|fq(t)|pdt=2∫R|f(x)|p(1+x2)-1dx.<2∫R|f(x)|p(1+x2)p-1dx.
Together with the assumption (9), the above equalities lead to the desired conclusions.We need one more lemma to represent the coefficientsdn, |n|∈N, in terms of the classical Fourier coefficients of fp. For any g∈L1(0,2π), the Fourier coefficients of g are defined by
(12)cn(g)∶=12π∫02π‍g(t)e-intdt,n∈Z.Lemma 2.
Suppose thatf∈L2(R) satisfies
(13)∫R‍|f(x)|2(1+x2)dx<∞,
and fp and fq are defined in (8). Then the coefficients dn(f),|n|∈N, defined in (5) are determined by
(14)dn(f)={-icn(fp)+icn-2(fp),n=±(2k-1),k∈N,-cn-1(fp)+2cn-2(fp)-cn-3(fp),WWWWWWWWn=2k,k∈N,-cn+1(fp)+2cn(fp)-cn-1(fp),WWWWWWWn=-2k,k∈N,
or
(15)dn(f)={-icn(fp)+icn-2(fp),n=±(2k-1),k∈N,-cn-1(fq),mmmmn=2k,k∈N,-cn+1(fq),mmmmn=-2k,k∈N.Proof.
For simplicity, we only give the proof for the cases ofn=2k-1 and n=2k, k∈N. The proof for the other cases can be similarly handled. By definition we have for each k∈N(16)d2k-1(f)=∫Rf(x)ϕ2k-1(x)¯dx.=-2π∫Rf(x)x1+x2(x+ix-i)2k-1dx.
Taking the change of variables t=σ(x), we get
(17)d2k-1(f)=-i12π∫02πf(σ-1(t))(1-eit)2(e-i(2k-1)t-e-i(2k-3)t)dt,
where we used the fact that (x/(1+x2))(σ-1)′=-(i/2)((eit+1)/(eit-1)). Combining the assumptions with Lemma 1, we point out that fp∈L2(0,2π). Then the above equation leads to
(18)d2k-1(f)=-ic2k-1(fp)+ic2k-3(fp).
In the same method, for the case of n=2k, k∈N, and by the fact that (1/(1+x2))(σ-1(t))′=1/2, we obtain
(19)d2k=-12π∫02π‍f(σ-1(t))e-i(2k-1)tdt=-c2k-1(fq).
According to the relationship between fp and fq, we have another form of d2k, which completes the proof.It is known that for anyg∈L1(0,2π), its Fourier coefficients cn(g) tend to zero as |n|→∞. This is the well-known Riemann-Lebesgue lemma [13]. As a direct consequence of Lemma 2, we have the same decay property of the coefficients dn(f),|n|∈N.Corollary 3.
Iff∈L2(R) satisfies (13) then there holds
(20)lim⁡|n|→∞dn(f)=0.Proof.
It follows from Lemma1 that fp∈L2(0,2π). Thus, there holds cn(fp)→0, |n|→∞. The relation between dn(f), |n|∈N and cn(fp), n∈Z, which is given in Lemma 2, yields the desired result.We now turn to the main theorem in this section about the almost everywhere convergence of the sequenceSN(f), N∈N. The almost everywhere convergence of the Fourier series is one of the most important results in the theory of Fourier series [14, 15]. It is said that for any g∈Lp(0,2π), 1<p<∞, the partial sum of its Fourier series
(21)S~N(g)(t)=12π∑n=-NN‍cn(g)eint,t∈(0,2π)
converges to g almost everywhere on (0,2π) as N→∞. We will show that the sequence of SN(f), N∈N, enjoys the same convergence property if f satisfies condition (13).Theorem 4.
Iff∈L2(R) satisfies (13), then the sequence SN(f), N∈N, converges to f almost everywhere on R.Proof.
Associated with anyf satisfying (13), due to Lemma 1, we know that fq=f∘σ-1∈L2(0,2π); it suffices to prove that as N→∞ there holds almost everywhere on (0,2π)(22)SN(f)(σ-1)(t)⟶f(σ-1)(t).
Consequently, the partial sum of its Fourier series S~N(fq) tends to fq almost everywhere on (0,2π) as N→∞. Upon this observation, (22) can be obtained by proving that as N→∞,
(23)SN(f)(σ-1(t))-S~N(fq)(t)⟶0,t∈(0,2π).
To get the difference betweenSN(f)(σ-1(t)) and S~N(fq)(t), we need to express the two items, respectively. By definition and change of variables x=σ-1(t), we have
(24)SN(f)(σ-1(t))=∑|n|=1N‍dn(f)ϕn(σ-1(t)),t∈(0,2π).
Applying Lemma 2 to the above equation, we can reexpress S2N(f)(σ-1(t)) through a direct computation. Specifically, upon introducing four summations
(25)I1∶=12π∑n=1N(c2n-1(fp)-2c2n-2(fp)+c2n-3(fp))‍mmmmmm×ei(2n-1)t,I2∶=12π∑n=1N‍(c-(2n-1)(fp)-2c-2n(fp)+c-(2n+1)(fp))mmmmmm×e-i(2n-1)t,I3∶=12π∑n=1N‍(c2n-2(fp)-c2n-3(fp))ei(2n-2)tmmmmll-(c2n-1(fp)-c2n-2(fp))ei2nt,I4∶=12π∑n=1N‍(c-2n(fp)-c-(2n+1)(fp))e-i2ntmmmmll-(c-(2n-1)(fp)-c-2n(fp))e-i(2n-2)t,
we rewrite S2N(f)(σ-1(t)) as follows:
(26)S2N(f)(σ-1(t))=I1+I2+I3+I4.
To be compared withS2N(f)(σ-1(t)), the item S~2N(fq)(t) should be represented in terms of the Fourier coefficients of fp. For this purpose, we rewrite cn(fq), n∈Z, as follows:
(27)cn(g)=12π∫02π‍f(σ-1(t))(1-eit)2(1-eit)2e-intdt=12π∫02π‍fp(t)(e-int-2e-i(n-1)t+e-i(n-2)t)dt=cn(fp)-2cn-1(fp)+cn-2(fp).
Substituting the above formula into the partial sum of the Fourier series of fq, we have
(28)S~2N(fq)(t)=12π∑n=-2N2N(cn(fp)-2cn-1(fp)+cn-2(fp))eint.‍
In a similar manner, we split the above equation into five items as follows:
(29)S~2N(fq)(t)=∑k=15‍Jk,
where
(30)J1∶=12π∑n=1N(c2n-1(fp)-2c2n-2(fp)+c2n-3(fp))mmmmmmm×ei(2n-1)t,J2∶=12π∑n=1N(c-(2n-1)(fp)-2c-2n(fp)+c-(2n+1)(fp))mmmmmmm×e-i(2n-1)t,J3∶=12π∑n=1N(c2n(fp)-2c2n-1(fp)+c2n-2(fp))mmmmmmm×ei2nt,J4∶=12π∑n=1N(c-2n(fp)-2c-(2n+1)(fp)+c-(2n+2)(fp))mmmmmmm×e-i2nt,J5:=12π(c0(fp)-2c-1(fp)+c-2(fp)).
It is clear that Ik=Jk, k=1,2. For k=3,4, there holds
(31)I3-J3=12π(c0(fp)-c-1(fp))+12π(c2N-1(fp)-c2N(fp))ei2Nt,I4-J4=12π(c-2(fp)-c-1(fp))+12π(c-(2N+1)(fp)-c-(2N+2)(fp))e-i2Nt.
Then by subtracting (29) from (26), we obtain
(32)S2N(f)(σ-1(t))-S~2N(fq)(t)=12π(c2N-1(fp)-c2N(fp))ei2Nt+12π(c-(2N+1)(fp)-c-(2N+2)(fp))e-i2Nt.
Together with the fact that fp∈L2(0,2π), Riemann-Lebesgue lemma yields for any t∈(0,2π)(33)lim⁡N→∞(S2N(f)(σ-1(t))-S~2N(fq)(t))=0.


## 3. Numerical Algorithm

Since the expansion (6) can serve as a representation of f with both mathematical and physical meanings, developing a fast approach for computing the coefficients dn(f),|n|∈N, is practically important. Lemma 2 states that evaluating the expansion coefficients of f can be carried by calculating the Fourier coefficients of fp, and then the well-known fast Fourier transform [16, 17] can be applied to compute the latter ones.We first recall the fast Fourier transform. The algorithm is developed to reduce the computational cost of the discrete Fourier transform which is defined as follows:(34)Yn=1N∑k=0N-1‍ykωN-nk,0≤n≤N-1,
where ωN∶=e2iπ(1/N). It requires (N-1)2 number of multiplications to compute Yn,0≤n≤N-1, directly by formula (34). When N is large, the computational cost is huge. The key idea of the fast Fourier transform is to compute Yn by splitting the sum into two parts according to the even and odd indices. More precisely, assume that N is an positive even integer, that is, N=2m. We rewrite formula (34) as follows:
(35)Yn=12(Pn+ωN-nIn),
where
(36)Pn=1m(y0+y2ωN-2n+⋯+yN-2ωN-(N-2)n),In=1m(y1+y3ωN-2n+⋯+yN-1ωN-(N-2)n).
Note that there holds the relations Pn+m=Pn and In+m=In, for n=0,1,…,m-1. Thus, one can obtain the same result for half of the cost by the following three steps.Step
1. For n=0,1,2,…,m-1, compute Pn and ωN-nIn.Step
2. Compute Yn,n=0,1,2,…,m-1, by Yn=(1/2)(Pn+ωN-nIn).Step
3. Compute Yn,n=m,m+1,2,…,2m-1, by Yn=(1/2)(Pn-m-ωN-(n-m)In-m).Assume thatN is a power of 2. It is clear that Pn and In are still two discrete Fourier transform of order m. Then the above process can be iterated until we arrive at the discrete Fourier transform of order 2. Consequently, we get the celebrated fast Fourier transform, which brings the computational cost for computing Yn,0≤n≤N-1, down to O(Nlog⁡2N).Applying the fast Fourier transform to compute the Fourier coefficients which are used to represent the coefficientsdn, we have the following fast algorithm for computing dn, |n|=1,2,…,N.Algorithm 5.
LetN>0 be a power of 2.
Step
1. Compute f^p,n,n=0,1,…,4N-1, by applying the fast Fourier transform to fp(kπ/2N), k=0,1,…,4N-1. Set c~n∶=f^p,n,n=0,1,…,2N-1, and c~n∶=f^p,n+4N,n=-1,-2…,-2N.
Step
2. Compute d~n,|n|=1,3,…,N-1, according to formula d~n=i(c~n-2-c~n).
Step
3. Compute d~n,n=2,4,…,N, according to formula d~n=-c~n-1+2c~n-2-c~n-3.
Step
4. Compute d~n,n=-2,-4,…,-N, according to formula d~n=-c~n+1+2c~n-c~n-1.The outputd~n,|n|=1,2,…,N, of Algorithm 5 is regarded as an approximation of the coefficients dn,|n|=1,2,…,N. The number of multiplications used in Algorithm 5 is estimated in the next theorem.Theorem 6.
The total number of multiplications needed for Algorithm5 is O(Nlog⁡2N).Proof.
The number of multiplications of Step 1, used to compute the discrete Fourier transform of order4N by the fast Fourier transform, is 2N(log⁡24N-2)+1. In the other steps, the number of multiplications for evaluating a family of d~n can be obtained as N/2. We use MN to denote the number of multiplications used in Algorithm 5. Then we have
(37)MN=2N(log⁡24N-2)+1+2N=2Nlog⁡2N+2N+1,
which gives the desired result.It is noticed that the change of variable could impact the regularity of the related functionfp in (8), thus impacting the accuracy of the numerical scheme. Therefore we require the conditions of Lemma 2 to keep the boundedness of the coefficients dn(f), n∈N. Other kinds of change of variable should be tried in the future study.



---

*Source: 526940-2014-08-21.xml*