Positive time-frequency distributions based on joint marginal constraints

2086 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 44, NO. 8, AUGUST 1996 Positive Time-Frequency Distributions Based on Joint Marginal Constraints Javier Rodrfguez Fonollosa Abstract-This correspondence studies the formulation of members of the Cohen-Posch class of positive time-frequency energy distributions. Minimization of cross-entropy measures with respect to different priors and the case of no prior or maximum entropy were considered. It is concluded that, in general, the information provided by the classical marginal constraints is very limited, and thus, the final distribution heavily depends on the prior distribution. To overcome this limitation, joint time and frequency marginals are derived based on a “direction invariance” criterion on the time-frequency plane that are directly related to the fractional Fourier transform. I. INTRODUCTION Time-frequency representations (TFR’s) are functionals that attempt to express the joint distribution of energy density in the time-frequency plane. There are several basic requirements that TFRs need to satisfy, although the most common representations cannot satisfy all of them simultaneously. The first, and most obvious, of the desired properties is the positivity. Only positive functionals can be properly interpreted as distributions in the probabilistic sense. Second, a true joint distribution of time and frequency must satisfy what are known as the “marginal” requirements, i.e., when the joint distribution is integrated along one of the variables, it should yield the marginal distribution of the other variable. In the case of timefrequency analysis, the marginal distributions in time and frequency are (s(t)I2 and IS(W)~~, respectively. Denoting the time frequency distribution as Q(t, LO), these requirements are formulated as Positivity: Q(t, w) >O (1) Marginal Requirements: / &(t, w) dt = lS(w)I2; Historically, time-frequency “distributions” were defined using different approaches [I]. Among them, the Spectrogram, the Wigner-Ville or, in general, bilinear distributions included in the Cohen general class are the most commonly used. Representations with signal-independent kernels are bilinear with respect to the signal under analysis. This bilinearity of the TFR implies that the positive and marginal requirements cannot be satisfied simultaneously unless we restrict the signal under analysis to the generalized Gaussian class. Efforts toward the development of kernels according to different optimality criteria (other than positivity) resulted in the formulation of “signal-dependent’’ representations [2], [3]. Nevertheless, “proper” distributions, i.e., time-frequency distributions that satisfy (1) and (2), do exist and can be easily generated [4]. They belong to what has been called the Cohen-Posh class of positive Manuscript received February 24, 1995; revised January 30, 1996. This work was supported by the National Plan of Spain, CICYT, grant TIC96-0500C10-01, and the Generalitat de Catalunya, CIRIT, GRQ93-3021. Portions of this work were presented at ICASSP’94, Adelaide, South Australia, Australia, April 1994. The associate editor coordinating the review of this paper and approving it for publication was Dr. Patrick Flandrin. The author is with the Universitat Politkcnica de Catalunya, Department of Signal Theory and Communications, Campus Nord, D-5, C/Gran Capita s/n, 08034, Barcelona, Spain. Publisher Item Identifier S 1053-587X(96)05272-5. distributions, all of which can be parameterized by a function p(z, y). There is an infinite number of such distributions, and the problem lies in finding the most useful for any particular application. In this correspondence, we consider an information theoretic approach for the definition of proper time-frequency distributions. It follows the pioneering work of Loughlin et al. [5]-[7]. We will show that sometimes, the two classical marginal requirements used as constraints in an entropy optimization problem cannot provide sufficient information to yield a representation with improved resolution with respect to the prior. In addition, in this case, the resulting distribution is very sensitive with respect to the time-frequency “orientation” of the signal under analysis. II. BACKGROUND: MCE-TFD Recently, a member of Cohen-Posh class of positive distributions was defined by Loughlin et al. [5]-[7]. It was formulated as the solntion to a minimum cross-entropy (MCE) optimization problem subject to linear constraints in general and, in particular, the fulfillment of the marginal conditions. That is, given a prior estimate P(t, w) > 0 of the unknown distribution Q(t, w), it is obtained as subject to the marginal requirements of (2). The Spectrogram 0: a combination of Spectrograms was chosen as a priori distribution P(t, w). As shown in the following examples, in some cases, the a priori distribution was very much preserved in the outcome, whereas in some other cases, the result was highly independent of the prior. High similarity with respect to the prior is not necessarily negative but, in our opinion, should not depend on the time-frequency orientation of the signal under analysis. Let us first illustrate the main limitations associated with the MCETFD as defined in [5]-[7] when only the marginals are used as constraints. MCE subject to the two marginal constraints in general can only improve, to a limited extend, the apriori distributions, unless signal components are oriented in “vertical” or “horizontal” lines in the time-frequency plane. In this case, MCE minimization w.r.t. most meaningful priors would yield basically the same result since the outcome is primarily determined by the constraints. As an example, consider two Gaussian envelope complex exponentials of different constant frequency and a time-frequency “rotated” version of them. The Spectrogram’ of these signals together with the MCE-TFD with Spectrogram prior are illustrated in Figs. 1 and 2: Fig. l(a) and (b) for the constant frequencies case and Fig. 2(a) and (b) for the linear frequencies case. The high “orientation” dependency of the MCETFD is manifest since a much higher resolution is obtained in the first case compared with the second. The limitations of the MCE-TFD using the marginals constraints only can be easily recognized if we analyze the classical form of the solution to the cross-entropy minimization problem. Using the method of Lagrange multipliers [7] ‘All distributions for synthetic signals have been computed using 256 samples of the signal and with a 256 x 256 resolution. The Spectrogram employed a Gaussian window of variance equal to 256/3.5. 1053-587W96$05,00 0 1996 IEEE IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 44, NO. 8, AUGUST 1996 2087 Time (b) Fig. 1. (b) MCE-TFD for two complex exponentials of constant frequency. (a) Spectrogram for two complex exponentials of constant frequency. where a and p are the Lagrange multipliers that need to be determined using the constraints. The resulting distribution is nothing but the a priori distribution shaped by a separable kernel A(w)B(t). As proposed by Loughlin et al., a possible alternative to add more constraints, i.e., “information,” in the entropy optimization problem is incorporating the higher order moments of the time-frequency energy density such as the instantaneous frequency and bandwidth or group delay and time spread. The form of the solution then becomes Q(t, w) =P(t,u) exp {-[l+ QO(W) + Po(t) + al(~j)t + bl(t)U + ru2(w)t2 + P2(t)w211. (5) Much more information can be incorporated into the prior in this case since the exponential is no longer a separable function in the product of “time only” and “frequency only” functions. There are, however, two serious problems associated with these additional constraints: First, there is no general agreement about what the first and second moments of Q(t. w) should be, and second, numerical solution of the entropy optimization problem with the moments 0 0 0 0 E g0 Q) It 0 0 0 0 -0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Time (a) “0 0.1 02 03 0.4 0.5 0.6 0.7 0.8 09 1 Time (b) Fig. 2 linear chirp signals (a) Spectrogram for two linear chirp signals. (b) MCE-TFD for two constraints is not as simple as with the marginals constraints only We consider a different approach to supplement the “separable” information, provided we have the classical constraints. We propose the definition of joint time frequency marginals along arbitrary directions in the time-frequency plane to include them as constraints in the optimization problem. The purpose of this correspondence is to analyze the new “information” provided by the constraints in addition to the prior. Therefore, no analysis on the selection of the prior is included, but on the contrary, emphasis is given to building distributions based on constraints only. [71. 111. JOINT MARGINALS PROPERTIES We investigated the possibility of defining joint generalized marginals along arbitrary directions of the time-frequency domain and concluded that the fractional or angular Fourier transform (AFT) (see [SI-[l l] and references therein) could provide much insight into this problem. The AFT was defined independently by different 2088 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL 44, NO 8, AUGUST 1996 researchers, both mathematically and using physical considerations, and all definitions were later shown to be equivalent. The reader is referred to [ll] for a thorough review of its definition, properties, and relation to the chirp and wavelet transform and applications. The AFT decomposes the signal under analysis using an orthonormal base of linear chirps and thus preserves the Parseval relation. The “orientation” of the basis functions (chirps) in the time-frequency plane depends on the angle a. Particular cases of the AFT for a = 0 and a = 7r/2 arc the identity operator and the Fourier transform, respectively. Precisely, the AFT at angle a of a signal s(t) is [9] &(U) = S(t)K,(t, U) dt (6) s = F,[s(t)] where Iia(t, U) = ( 6(t - U), if ais multiple of 27r 6(t + U), if a + 7r is multiple of 27r /F exp (Jf2 ; u2 cot a -jut csc a if a is not a multiple of 7r (7) where csc and cot are the cosecant and cotangent functions, respectively. In addition, it is additive with respect to the angle a, Fp{F,[s(t)]} = F,+p[s(t)]. Within a time-frequency analysis context, it is important to emphasize its reIation to the Wigner-Ville Distribution (WD). In particular, defining the rotation operator for 2-D functions, corresponding to a counterclockwise rotation by 4, then that is, the AFT at angle a of the signal is equivalent to a a-degree rotation of its WD. Considering all the properties of the AFT and the fact that there is a general agreement on what the time-frequency representation of chirp signals should be, we concluded that the same integration of the distribution in the frequency and time axes should give the squared magnitude of the signal and its Fourier transform, as indicated by (2). The integration of the distribution along a rotated axis should give the squared magnitude of the AFT. That is the WD is the only distribution that satisfies (9) and, since the WD is a nonpositive functional in general, the subclass of the positive distributions satisfying (9) for all a, -7r/2 < a 5 7r/2 is empty. Satisfaction of the joint marginals for all angles is incompatible with positivity, but this fact does not disqualify them as desirable properties. The same way the WD satisfies the joint marginals and is not positive everywhere, we can think of distributions that are positive and do not satisfy the joint marginals everywhere, but only at some angles. Hence, we propose to further restrict the Cohen-Posch class of positive distributions, enforcing the joint marginal constraints for some angles az only. From an information theoretic point of view, the two classical marginal constraints of (2) supply information from the observation of the distribution at angles 0 and ~12. As seen in the case of MCE-TFD with Spectrogram pnor, not much information is provided along other directions and the posterior, which is the resulting distribution, looks much like the prior when observed from those angles since it is modeled by a separable time-frequency kernel. On the other hand, satisfaction of the generalized marginals (9) at a limited number of angles can restrict the positive class of distributions and eventually make the outcome insensitive to the choice for the a priori distribution. Therefore, we define a positive time-frequency distribution (METFD) based on a maximum entropy cnterion and given by subject to 1 1 &(t, w)6(t cos a, + w sin a, - U) dtdw = IS,,(u)I2 (lO.b) for a1 = 0, a2 = ~12, and some additional a, to a total of N constraints. The information introduced by the joint marginals can be observed in the form of the solution to the entropy maximization problem (which is equivalent to cross-entropy minimization with uniform prior). Again, using the method of Lagrange multipliers (see the Appendix) where A,(t cos az + w sin a,) are the Lagrange multipliers that result from the enforcement of the constraints. Note that a1 = 0, and a2 are a function of t and U only, respectively, whereas the others depend of a combination of both variables. It is apparent that the information introduced by the constraints is given (in general) in the form of a nonseparable kernel. Of course, if a reliable estimate of the distribution was available, it could be introduced as a prior, and the solution to the minimum cross-entropy problem would have the form 11 ~(t, w)S(t cos a + w sina - U) dtdw = 1se(u)12. It is well known that these generalized marginals are satisfied by the WD [9], [IO]. In the next section, we will investigate the consequences of considering these joint marginals as constraints in an entropy-optimization problem. and thus, A1 and Iv. JOINT MARGINALS AS CONSTRAINTS Apparently, a subclass of the Cohen-Posch class of positive distributions could be defined as the positive distributions that satisfy (9) for all a, -7r/2 < a 5 7r/2. Nevertheless, (9) can be readily recognized as the Radon transform [12] of the distribution P(t, U), and the inverse Radon transform theorem establishes that a 2-D function is uniquely determined from its Radon transform. Therefore, Q(t, w) = (12) N ~(t, w) exp { - [I + A,(t cos at + w sin 01%) 2=1 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 44, NO. 8, AUGUST 1996 2089 -0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 I Time (a) -0 01 02 03 04 05 06 07 08 09 I Time ih) Fig 3 two adhtlonal constrants (a) ME-TFD with the marginal constrants only (h) ME-TFD with No proof of consistency can be given for satisfaction of the marginals for a given set of angles. From a theoretical point of view, the satisfaction of the joint marginals should be regarded as a desirable property that might be incompatible with positivity. From a practical point of view, no inconsistency has been observed using a small number of constraints. Analysis of the robustness of the method with respect to slight rotations in the angles is deferred for a later publication. V. IMPLEMENTATION Computation of (10) is a multivariate constrained maximization problem that can be solved using the Lagrange multipliers method but for which a closed-form solution cannot be obtained in general. Yet, there is an iterative solution to the problem in which each of the univariate optimization problems is solved independently [14], [15]. The same technique was used in [7] for the MCE-TFD. In our case, we start with the uniform distribution (instead of the Spectrogram) 1 E, ’ Q:(t, w) = -. E, = / ls(t)I2 dt (13) and follow with the N individual constraint enforcement iterations QP(t, w) = QPi(t, ~)ISaz(~z)l~ lt lt ~:-~(tt, w‘)~[t‘ cos (a,) + w’ sin (a,) - ut] dt’ dw’ fori = 1, ... . N and uz = t cos (a,) + w sin (a,) (14) for 01 = 0, a2 = ~12, and the desired additional a,. Computation of the AFT is not directly required since IS,(u)I2 can be obtained as the integration along the corresponding line of the WD Please note that since we are forcing each of the constraints independently, after each iteration, only the last one (and perhaps none of the other constraints) will be satisfied. Then, using Q&(t, w) as prior, we obtain Q:(t, U), . .. , Qh(t, w). This procedure should be repeated until convergence is attained to the desired precision Q(t, U) = lim QL(t, U). (15) k-oo Convergence is, however, assured, provided the constraints are consistent, by the convexity of the cross-entropy cost function [13], which implies ff[Q(t, w), QF+l(t, w)l i H[Q(t, U), Qt(t, w)l (16) where H[Q(t, U), P(t, w)] is the cross-entropy between Q(t, U) and Addition of constraints only increases the computational complexP(t, U). ity of the method linearly. VI. EXAMPLES In our simulations, we considered two additional values of cy, in addition to the “horizontal” and “vertical” marginals a3 = ~/4 and a4 = -.lr/4. These marginals are very simple to compute since, in a discrete implementation, they correspond to the sum of the diagonals of the matrix that represents the WD. This choice of angles a2 means that the form of the distribution, given by the particularization of (ll), is Q(t, = exp{-[l+Xl(t)+Xz(w)+X3(~+W)+X4(t--)I}. (17) A. Synthetic Signals We first illustrate how the results obtained using the ME-TFD are consistent with what should be expected from its theory. Fig. 3(a) and (b) show the distributions obtained using ME-TFD with the two usual marginal constraints only and with the addition of the joint constraints at angles cy = ~/4 and cy = -.lr/4. The “orientation” dependency of the MCE-TFD has been diminished with the addition of only two joint constraints as indicated by (17) compared with (4). In addition, as expected, a resolution similar to the one obtained with the MCE-TFD in the constant frequency case (Fig. l(b)) is obtained using the ME-TFD with the linear chirp. B. Real Signals We illustrate the application of the distributions described in this correspondence to a natural signal. The signal under analysis is a chirp-like signal recorded from a dolphin. In Fig. 4(a), we give the 2090 EEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 44, NO. 8, AUGUST 1996 DOlDhin Sianal -600 50 100 Time (Samples) (a) -0 0.1 02 0.3 0.4 0.5 0.6 0.7 0.8 09 1 Time (c) -0 0.1 0.2 03 04 0 5 0.6 07 0.8 0.9 1 Time (4 Fig 4 (a) Temporal representation of the dolphin signal (b) Spectrogram of the dolphin signal (c) Wigner-Ville distribution of the dolphin signal (d) MCE-TFD of the dolphin signal with the two marginals as constraints (e) ME-TFD of the dolphin signal with the two marginals as constrants (f) ME TFD of the dolphin signal with four marginals as constraints IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 44, NO. 8, AUGUST 1996 2091 temporal representation of this signal. Fig. 4(b) and (c) show the Spectrogram and the WD of the dolphin signal, respectively. The Spectrogram is characterized by a poor time-frequency resolution, whereas the WD suffers from interference terms. In Fig. 4(d), the MCE-TFD employing the two classical marginal constraints only and Spectrogram prior is illustrated. If no prior is employed, i.e., if a maximum entropy TFD is computed using only the two marginals, the resulting distribution is very similar and is illustrated in Fig. 4(e). We can observe how the marginal constraints “shape” the a priori distribution along the horizontal and vertical directions only. Finally, the ME-TFD that makes use of the two classical marginals and two joint marginals is given in Fig. 4(f). A chirp-like representation is obtained without the interfering terms of the WD. It is fair to mention that the MCE-TFD could be potentially improved after a careful selection of the prior, as suggested in [7], but emphasis in this paper is given to the information supplied by the constraints and not to the selection of the prior. VII. CONCLUSIONS A new set of joint constraints has been proposed for the class of positive time-frequency distributions. They are the equivalent, along nonhorizontal or vertical directions, of the two classical marginals and can be directly related to the fractional Fourier transform. Although the only distribution that satisfies the complete set of joint constraints is the Wigner-Ville Distribution, they can be partially used to restrain the Cohen-Posh class of positive distributions. They have been employed as additional constraints in the formulation of positive distributions solution to entropy optimization problems. The main advantage of the joint constraints when employed in entropy optimization problems is that the apriori distribution can be modified with a kemel that is not separable in time and frequency. Only time and frequency separable functions can modify the prior when using the two marginals as unique constraints in the same problem. Positive distributions defined as solution to a maximum entropy optimization subject to the classical plus two additional constraints have been analyzed and compared with existing approaches with both synthetic and real signals. APPENDIX Given a prior distribution, i)(t, w) and a set of equality constraints 1 Q(t, w)S(t cos a2 + w sin at - U) dtdw = IS,,(U)~~ (A.1) for a1 = 0, a2 = w/2, and “some” additional at to a total of N constraints, we wish to find the distribution that minimizes Q(t, w) = Introducing the Lagrange multipliers A, (ut) forming the expression [I31 which, solving for Q(t, U), leads to 11 N P(t, w) exp { - [I + A,(t cos at + w sin at) . t=1 This proves (12) while considering uniform prior (11). In addition, taking a1 = 0, a2 = w/2, a3 = w/4, and cy4 = -w/4 and uniform prior proves (17). ACKNOWLEDGMENT The author expresses his gratitude to Prof. L. Cohen and the anonymous reviewers for their enlightening discussions and especially to reviewer A for herhis thorough review of the manuscript. REFERENCES [I] L. Cohen, “Time-frequency ,distributions-A review,” Proc. IEEE, vol. 77, no. 7, pp. 941-981, 1989. [2] R. Baraniuk and D. Jones, “A signal-dependent time-frequency-I Representation: Optimal kernel design,” IEEE Trans. Signal Processing, vol. 41, no. 4, pp. 263-284, 1993. [3] D. Jones and T. Parks, “A high resolution data-adaptive time-frequency representation,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-33, no. 12, pp. 2127-2135, 1985. [4] L. Cohen and T. E. Posch, “Positive time-frequency distribution functions,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-33, no. 1, pp. 31-38, 1985. [5] P. J. Loughlin, J. W. Pitton, and L. E. Atlas, “An information-theoretic approach to positive time-frequency distributions,” in Proc. ICASSP-92, San Francisco, CA, 1992, pp. V 125-128. [6] J. W. Pitton, P. J. Loughlin, and L. E. Atlas, “Positive time-frequency distributions via maximum entropy deconvolution of the evolutionary spectrum,” in Proc. ICASSP-93, Minneapolis, MN, 1993, pp. IV 436-439. [7] P. J. Loughlin, J. W. Pitton, and L. E. Atlas, “Construction of positive time-frequency distributions,” IEEE Trans. Signal Processing, vol. 42, no. 10, pp. 2697-2705, 1994. [8] B. W. Dickinson and K. Steiglitz, “Eigenvectors and functions of the discrete Fourier transform,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-30, no. 1, pp. 25-31, 1982. [9] L. Almeida, “An introduction to the angular Fourier transform,” in Proc. ICASSP-93, Minneapolis, MN, 1993, pp. I11 257-260. IO] R. G. Dorsch and A. W. Lohmann, “The fractional Fourier transform,” in Proc. ATHOS Workshop Syst. IdentGcation High Order Stat., Sophia Antipolis, France, 1993, pp. 1-8. 111 H. M. Ozaktas and B. Barshan, “Convolution, filtering, and multiplexing in fractional Fourier domains and their relation to chirp and wavelet transforms,” J. Opt. Soc. Amer. A, Optics Image Sci. Vision, vol. 11, no. 2, pp. 547-559, 1994. 121 S. R. Deans, The Radon Transform and Some of Its Applications. New York Wiley, 1983. [13] J. E. Shore and R. W. Johnson, “Properties of cross-entropy minimization,’’ IEEE Trans. Inform Theory, vol. IT-27, no. 4, pp. 472482, 1981. [I41 Y. A.. Alsaka, N. S. Tzannes, and W. A. Marinelli, “An efficient algorithm for implementing the relative entropy method,” in Proc. 1151 R. Burr, “Iterative convex I-projection algorithm for maximum entropy and minimum cross-entropy computations,” IEEE Trans. Inform. Theory, vol. 35, no. 3, pp. 695-698, 1989. ICASSP-88, 1988, pp. 2384-2387. .. . S(t’ cos at + w‘ sin a, - U,) dt’ dw’ du,. (A.3) Equating the variation of (A.3) with respect to Q(t, U) to zero