On the inverse windowed Fourier transform

2668 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 45, NO. 7, NOVEMBER 1999 REFERENCES [1] G. D. Forney, “Coset codes—Part I: Introduction and geometrical classification,” IEEE Trans. Inform. Theory, vol. 34, pp. 1123–1151, Sept. 1998. [2] G. D. Forney and L. Wei, “Multidimensional constellations—Part I: Introduction, figures of merit, and generalized cross constellations,” IEEE J. Select. Areas Commun., vol. 7, pp. 941–958, Aug. 1989. [3] A. R. Calderbank and L. H. Ozarow, “Nonequiprobable signaling on the Gaussian channel,” IEEE Trans. Inform. Theory, vol. 36, pp. 726–740, July 1990. [4] G. D. Forney, “Trellis shaping,” IEEE Trans. Inform. Theory, vol. 38, pp. 281–300, Mar. 1992. [5] A. K. Khandani and P. Kabal, “Shaping multidimensional signal spaces—Part I: Optimum shaping, shell mapping,” IEEE Trans. Inform. Theory, vol. 39, pp. 1799–1808, Nov. 1993. [6] J. N. Livingston, “Shaping using variable-size regions,” IEEE Trans. Inform. Theory, vol. 38, pp. 1347–1353, July 1992. [7] F. R. Kschischang and S. Pasupathy, “Optimal nonuniform signaling for Gaussian channels,” IEEE Trans. Inform. Theory, vol. 39, pp. 913–929, May 1993. [8] A. R. Calderbank and M. Klimesh, “Balanced codes and nonequiprobable signaling,” IEEE Trans. Inform. Theory, vol. 38, pp. 1119–1122, May 1992. [9] J. M. Kahn and J. R. Barry, “Wireless infrared communications,” Proc. IEEE, vol. 85, pp. 265–298, Feb. 1997. [10] G. P. Agrawal, Fiber-Optic Communication Systems. New York: Wiley, 1997. [11] J. G. Proakis, Digital Communications, 3rd ed. New York: McGrawHill, 1995. On the Inverse Windowed Fourier Transform Laura Rebollo-Neira and Juan Fernandez-Rubio Abstract—The inversion problem concerning the windowed Fourier transform is considered. It is shown that, out of the infinite solutions that the problem admits, the windowed Fourier transform is the “optimal” solution according to a maximum-entropy selection criterion. Index Terms— Gabor transform, inversion problems, maximum entropy, windowed Fourier transform. I. INTRODUCTION The use of a generalized Fourier integral to convey simultaneous time and frequency information was first introduced by Gabor (1946). In [2], he defines a windowed Fourier integral, using a Gaussian window. Later, the window was generalized to any function in L 2 ( R ) , the space of square integrable functions. The so generalized Gabor Manuscript received March 1, 1997; revised February 17, 1999. This work was supported by CIRIT of Catalunya, CICYT of Spain (TIC96-0500-C10-01, TIC98-0412), and CICPBA of Argentina. L. Rebollo-Neira is with CICPBA (Comisi´on de Investigaciones Cient´ıficas de la Provincia de Buenos Aires), Departamento de F´ ısica, Universidad Nacional de La Plata C.C. 727, 1900 La Plata, Argentina. J. Fernandez-Rubio is with the Departament de Teoria del Senyal i Comunicacions, Escola Tecnica Superior, d’Enginyers de Telecomunicaci´ o, Campus Nord, UPC, Edifici D-4, c/. Gran Capita s/n. 08034 Barcelona, Spain (e-mail: [email protected]). Communicated by C. Herley, Associate Editor for Estimation. Publisher Item Identifier S 0018-9448(99)08127-4. transform is mostly referred to as the windowed Fourier transform (WFT). Restricting the space of signals to L 2 ( R ) , the WFT is a mapping from L 2 ( R ) to L 2 ( R 2 ) which is not bijective. As a consequence, lack of uniqueness of the inverse problem must be expected. In this contribution, we focus on a statistical analysis of the inversion problem. First the problem is shown to admit an infinite number of solutions. We then work on the space of possible solutions adopting a statistical description as the essential tool. The possible solutions are considered as a stochastic process distributed according to a (to be determined) probability density. The desired solution is estimated as the mean value of the random process. Among all the probability densities capable of yielding admissible mean-value solutions we single out one, adopting the maximum-entropy principle (MEP). Finally, we show that, from the maximum-entropy (ME) probability density a mean-value solution is inferred which is identical to the WFT. Thereby the WFT is shown to be an “optimal” solution according to an ME selection criterion. This result also holds as a property within the Frame Theory [9]. II. THE WFT INVERSE PROBLEM Definition: Let f ( x ) 2 L 2 ( R ) be a given signal and g ( x ) 2 L 2 ( R ) be any fixed function in L 2 ( R ) . The WFT of f ( x ) is a function F ( !;t ) 2 L 2 ( R 2 ) defined by F ( !;t )= h e i !x g ( x 0 t ) j f ( x ) i = R e 0 i!x g 3 ( x 0 t ) f ( x ) dx (1) where g 3 ( x ) denotes the complex conjugate of g ( x ) . The signal can be reconstructed from its WFT through the inversion formula [1], [3], [6] f ( x )= 1 C gR e i!x g ( x 0 t ) F ( !;t ) d!dt (2) where C g = k g k 2 = R j g ( x ) j 2 dx: Although the inversion formula (2) allows the recovery of a signal from its WFT, the inversion is not unique. Let us denote W to the image of the WFT, i.e., W = F ( !;t ); F ( !;t )= R e 0 i!x g 3 ( x 0 t ) f ( x ) dx ; for some f ( x ) 2 L 2 ( R ) : (3) W is only a closed subspace, not all of L 2 ( R 2 ) (not every function h ( !;t ) 2 L 2 ( R 2 ) belongs to W ). The next theorem, whose proof is given in [6, p. 56], provides the necessary and sufficient condition for h ( !;t ) 2W . Theorem 1: A function h ( !;t ) belongs to W if and only if it is square integrable and, in addition, satisfies h ( ! 0 ;t 0 )= 1 C gR K ( ! 0 ;t 0 ;!;t ) h ( !;t ) d!dt (4) where K ( ! 0 ;t 0 ;!;t )= h e i! x g ( x 0 t 0 ) j e i!x g ( x 0 t ) i = R e 0 i! x g 3 ( x 0 t 0 ) e i!x g ( x 0 t ) dx: (5) 0018–9448/99$10.00 1999 IEEE IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 45, NO. 7, NOVEMBER 1999 2669 The function K ( ! 0 ;t 0 ;!;t ) is called the reproducing kernel determined by the window g and (4) is called the associated consistency condition. Theorem 2: All functions h ? ( !;t ) belonging to W ? (the orthogonal complement of W ) satisfy R e i!x g ( x 0 t ) h ? ( !;t ) d!dt =0 : (6) Proof: Multiplying the right-hand side of (6) by e 0 i! x g 3 ( x 0 t 0 ) and integrating over x we have R R e i!x g ( x 0 t ) e 0 i! x g 3 ( x 0 t 0 ) dx h ? ( !;t ) d!dt: (7) From the definition of W it follows that R e 0 i!x g 3 ( x 0 t ) e i! x g ( x 0 t 0 ) dx 2W : Consequently, R R e i!x g ( x 0 t ) e 0 i! x g 3 ( x 0 t 0 ) dx h ? ( !;t ) d!dt = R R e 0 i!x g 3 ( x 0 t ) e i! x g ( x 0 t 0 ) dx 3 h ? ( !;t ) d!dt =0 (8) because h ? ( !;t ) 2W ? is orthogonal to every function in W . Notice that (8) can be recast in the form h e i! x g ( x 0 t 0 ) j F ( x ) i = R e 0 i! x g 3 ( x 0 t 0 ) F ( x ) dx =0 (9) where F ( x )= R e i!x g ( x 0 t ) h ? ( !;t ) d!dt (10) and since span f e i! x g ( x 0 t 0 ) g ( !;t ) 2 R is dense in L 2 ( R ) h e i! x g ( x 0 t 0 ) j F ( x ) i =0 ; 8 ( ! 0 ;t 0 ) implies F ( x )  0 , whereby the proof is completed. The lack of uniqueness of the inverse WFT is an immediate consequence of Theorem 2. Indeed, besides F ( !;t ) , for any h ? ( !;t ) 2 W ? the function h ( !;t )= F ( !;t )+ h ? ( !;t ) also reconstructs the same signal. The inversion formula (2) corresponds to the particular choice h ? ( !;t )=0 and obviously gives rise to a solution of the inverse problem which is “optimal” in a minimum norm (MN) sense. The MN requirement may be a reasonable criterion to be adopted in the case of some applications, but, a priori, certainly not in all of them. In this correspondence we address the problem of deciding on an appropriate estimate for the unknown solution h ( !;t ) by recourse to a postulate originally conceived for the purpose of making decisions in indeterminate situations, namely, the MEP [4], [5]. In the next section we show that the WFT is also an “optimal” solution of the inverse problem according to a ME selection criterion, as it turns out to be the mean of the probability density that maximizes the entropy. III. THE ME APPROACH The problem we address now is that of inverting for h the equation f ( x )= 1 C gR e i!x g ( x 0 t ) h ( !;t ) d!dt: (11) We begin by splitting the above complex equation into real and imaginary parts so that it becomes f u ( x )= 1 C gR g u !;t ( x ) h u ( !;t ) 0 g v !;t ( x ) h v ( !;t ) d!dt (12) f v ( x )= 1 C gR g v !;t ( x ) h u ( !;t )+ g u !;t ( x ) h v ( !;t ) d!dt (13) where f u ( x ) ;f v ( x ) are the real and imaginary parts of f ( x ) whereas h u ( !;t ) ;h v ( !;t ) are the real and imaginary parts of h ( !;t ) and g u !;t ( x ) ;g v !;t ( x ) are the real and imaginary parts of e i!x g ( x 0 t ) ; respectively. As discussed in the previous section, there exist several functions h ( !;t ) capable of satisfying (12) and (13). Our aim is that of selecting one of those solutions as “optimal” in an ME sense. In order to achieve such a goal, we regard the possible solutions as a stochastic process and estimate the desired solution as its mean value that we denote h ( !;t )= h u ( !;t )+ ih v ( !;t );( !;t ) 2 R 2 : To deal with the stochastic process in a discrete way, we divide R 2 into squares of area 1 r = 1 M , centered at the points r j =( ! j ;t j ) and take lim M !1 . With this discretization, (12) and (13), which provide the constraints to be satisfied by the desired solution, are evaluated as f u ( x ) = lim M !1 1 MC g M j =1 g u r ( x ) h u ( r j ) 0 g v r ( x ) h v ( r j ) (14) f v ( x ) = lim M !1 1 MC g M j =1 g v r ( x ) h u ( r j )+ g u r ( x ) h v ( r j ) : (15) At a fixed point r j , both h u ( r j ) and h v ( r j ) are now random variables. To simplify notation let us denote hh h uu u = h u ( r 1 ) ; 111 ;h v ( r M ) and hh h vv v = h v ( r 1 ) ; 111 ;h u ( r M ) . Assuming that these 2 M random variables are distributed according to a probability density P ( hh h uu u ;hh h vv v ) , the mean values h u ( r j ) ; h v ( r j ) involved in (14) and (15) are calculated as h u ( r j )= R P ( hh h uu u ;hh h vv v ) h u ( r j ) dhh h uu u dhh h vv v ;j =1 ; 111 ;M (16) h v ( r j )= R P ( hh h uu u ;hh h vv v ) h v ( r j ) dhh h uu u dhh h vv v ;j =1 ; 111 ;M (17) where dhh h uu u = dh u ( r 1 ) ; 111 ;dh u ( r M ) and dhh h vv v = dh v ( r 1 ) ; 111 ;dh v ( r M ) : Since P ( hh h uu u ;hh h vv v ) is a probability density we must require it satisfies the constraint R P ( hh h uu u ;hh h vv v ) dhh h uu u dhh h vv v =1 : (18) In addition, we should set a constraint to ensure h ( !;t ) 2 L 2 ( R 2 ) . This is guaranteed under the requirement that k h k 2 be finite, which 2670 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 45, NO. 7, NOVEMBER 1999 also ensures that the variance of the probability density is finite. Consequently, we will set the additional constraint k h k 2 =lim M !1 1 M M j =1 R P ( hh h uu u ;hh h vv v )( h u ( r j ) 2 + h v ( r j ) 2 ) dhh h uu u dhh h vv v = C (19) where C is an unknown constant. Constraints (14), (15), (18), and (19), to be satisfied by the probability density we are looking for, are not enough to determine it in a unique way. Among all the P ( hh h uu u ;hh h vv v ) capable of fulfilling these constraints, we shall select one adopting the MEP. This criterion yields the probability density that, being consistent with the available data, is maximally noncommittal with respect to the lack of information (entropy) [4], [5]. The entropy, or uncertainty, associated with the probability density is given by the generalization of Shannon’s measure [8] to continuous-type random variables [7], i.e., H ( hh h uu u ;hh h vv v )= 0 R P ( hh h uu u ;hh h vv v )ln P ( hh h uu u ;hh h vv v ) dhh h uu u dhh h vv v : (20) Since we should take lim M !1 to represent our stochastic process, the appropriate measure to be used is the entropy rate  H , or entropy per degree of freedom, defined as [7]  H = lim M !1 1 2 MH ( hh h uu u ;hh h vv v ) : (21) We then look for the probability density that maximizes  H with constraints (14), (15), (18), and (19). In order to introduce the constraints (14) and (15) into the variational process, we divide the axis R into intervals of length 1 x = 1 N centered at the points x i and take lim N !1 , at the end. Assuming that f u ( x ) and f v ( x ) are continuous functions we incorporate each constraint (14), evaluated at x = x i , through a Lagrange multiplier that we write  u x 1 x and each constraint (15) through a Lagrange multiplier  v x 1 x . Constraints (18) and (19) are introduced through the Lagrange multipliers  0 and  , respectively. Thus the functional, S , to be maximized is cast S = 0 1 2 M R P ( hh h uu u ;hh h vv v ) 1 ln P ( hh h uu u ;hh h vv v )+2  M j =1 ( h u ( r j ) 2 + h v ( r j ) 2 ) dhh h uu u dhh h vv v 0  0 R P ( hh h uu u ;hh h vv v ) dhh h uu u dhh h vv v 0 1 N N i =1  u x 1 MC g M j =1 g u r ( x i ) h u ( r j ) 0 g v r ( x i ) h v ( r j ) 0 1 N N i =1  v x 1 MC g M j =1 g v r ( x i ) h u ( r j )+ g u r ( x i ) h v ( r j ) (22) h u ( r j ) and h v ( r j ) are calculated as in (16) and (17). From the condition S P =0 we obtain P ( hh h uu u ;hh h vv v )=exp 0 (2 M 0 +1) 1 exp 0 2 M j =1 ( h u ( r j )  1 ( r j )+ h v ( r j )  2 ( r j ) + h u ( r j ) 2 + h v ( r j ) 2 ) (23) where  1 ( r j )= 1 NC g N i =1  u x g u r ( x i )+  v x g v r ( x i ) (24) and  2 ( r j )= 1 NC g N i =1  v x g u r ( x i ) 0  u x g v r ( x i ) : (25) Since the entropy (20) is a convex functional [7] it takes on its absolute maximum at P ( hh h uu u ;hh h vv v ) given in (23). The normalization constraint (18) entails exp(2 M 0 +1)= R exp 0 2 M j =1 ( h u ( r j )  1 ( r j )+ h u ( r j )  2 ( r j ) + h u ( r j ) 2 + h v ( r j ) 2 ) dhh h uu u dhh h vv v =  2  MM j =1 exp  1 ( r j ) 2 2  exp  2 ( r j ) 2 2 : (26) The remaining Lagrange multipliers,  u x ; v x ; i =1 ; 111 ;N; and  , should be obtained by using (23) in (14), (15), and (19) and solving the equations. However, as we shall see below, the functional form of P ( hh h uu u ;hh h vv v ) , given in (23), already provides the information that is needed to determine the mean value function h ( r j ) that such probability density will predict. Indeed, by replacing (23) in (16) and (17) and performing the integrals we have h u ( r j )= 0  1 ( r j ) 2  = 0 1 2 NC g N i =1  u x g u r ( x i )+  v x g v r ( x i ) (27) h v ( r j )= 0  2 ( r j ) 2  = 0 1 2 NC g N i =1  v x g u r ( x i ) 0  u x g v r ( x i ) : (28) Taking now lim N !1 , the above equations yield h u ( r j )= 0 1 2 C gR  u x g u r ( x )+  v x g v r ( x ) dx (29) h v ( r j )= 0 1 2 C gR  v x g u r ( x ) 0  u x g v r ( x ) dx (30) or h ( r j )= h ( ! j ;t j )= h u ( ! j ;t j )+ ih v ( ! j ;t j ) = R e 0 i! x g 3 ( x 0 t j ) w ( x ) dx (31) with w ( x )= 0 1 2 C g (  u x + i v x ) : From (31) and definition (3) we gather that h ( ! j ;t j ) 2W ; ( ! j ;t j ) 2 R 2 : So that, by Theorem 1, we are in a position to reveal h ( !;t; ) .In fact, by using h ( !;t ) in (11) and performing the inner product of both sides with e i! x g ( x 0 t 0 ) we have h e i! x g ( x 0 t 0 ) j f ( x ) i = F ( ! 0 ;t 0 ) =1 C gR h e i! x g ( x 0 t 0 ) j e i!x g ( x 0 t ) i h ( !;t ) d!dt (32) and, since h ( !;t ) 2W , by Theorem 1 the consistency condition (4) is verified. Hence, from (32) and Theorem 1 we conclude that IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 45, NO. 7, NOVEMBER 1999 2671 h ( ! 0 ;t 0 )= F ( ! 0 ;t 0 ) , which states the WFT as an optimal solution of the inverse problem according to an ME selection criterion. Since such a solution is also optimal in an MN sense, we are led to conclude that the MN requirement works by averaging functions in a maximally noncommittal way. In other words, we give here a new argument supporting the use of the MN solution for the inverse windowed Fourier transform problem, as it has been shown to be the “least biased” assignment one can make on the basis of the available information. REFERENCES [1] I. Daubechies, Ten Lectures on Wavelets. Philadelphia, PA: SIAM, 1992. [2] D. Gabor, “Theory of communications,” J. Inst. Elec. Eng., vol. 93, pp. 429–457, 1946. [3] C. Heil and D. Walnut, “Continuous and discrete wavelet transforms,” SIAM Rev., vol. 31, pp. 628–666, 1989. [4] E. T. Jaynes, “Information theory and statistical mechanics,” Phys. Rev., vol. 106, pp. 620–630, 1957. [5] , “Where do we stand maximum entropy?,” in The Maximum Entropy Formalism, R. Levine and M. Tribus, Eds. Boston, MA: MIT Press, 1979. [6] G. Kaiser, A Friendly Guide to Wavelets. Berlin, Germany: Birkh¨auser, 1994. [7] A. Papoulis, Probability, Random Variables and Stochastic Processes. New York: McGraw-Hill, 1991. [8] C. E. Shannon, “The mathematical theory of communication,” Bell Syst. Tech. J., vol. 27, pp. 379–423, 623–656, 1948. [9] L. Rebollo-Neira, J. F. Rubio, and A. Plastino, “Frames: A maximum entropy statistical estimate of the inverse problem,” J. Math. Phys., vol. 38, no. 9, pp. 4863–4871, 1997.