Journal of Signal and Information Processing, 2013, 4, 423429 Published Online November 2013 (http://www.scirp.org/journal/jsip) http://dx.doi.org/10.4236/jsip.2013.44054 Open Access JSIP 423 Generalized Discrete Entropic Uncertainty Relations on Linear Canonical Transform Yunhai Zhong1, Xiaotong Wang 1, Guanlei Xu2, Chengyong Shao1, Yue Ma1 1Navigtion Department of Dalian Naval Academy, Dalian, China; 2Ocean Department of Dalian Naval Academy, Dalian, China. Email: mayue0205@163.com, 783343634@qq.com, dljtxywxt@163.com, xgl_86@163.com, ketizuemail@163.coms Received September 24th, 2013; revised October 20th, 2013; accepted October 30th, 2013 Copyright © 2013 Yunhai Zhong et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. ABSTRACT Uncertainty principle plays an important role in physics, mathematics, signal processing and et al. In this paper, based on the definition and properties of discrete linear canonical transform (DLCT), we introduced the discrete Hausdorff Young inequality. Furthermore, the generalized discrete Shannon entropic uncertainty relation and discrete Rényi en tropic uncertainty relation were explored. In addition, the condition of equality via Lagrange optimization was devel oped, which shows that if the two conjugate variables have constant amplitudes that are the inverse of the square root of numbers of nonzero elements, then the uncertainty relations touch their lowest bounds. On one hand, these new uncer tainty relations enrich the ensemble of uncertainty principles, and on the other hand, these derived bounds yield new understanding of discrete signals in new transform domain. Keywords: Discrete Linear Canonical Transform (DLCT); Uncertainty Principle; Rényi Entropy; Shannon Entropy 1. Introduction Uncertainty principle [120] plays an important role in physics, mathematics, signal processing and et al. Un certainty principle not only holds in continuous signals, but also in discrete signals [1,2]. Recently, with the de velopment of fractional Fourier transform (FRFT), con tinuous generalized uncertainty relations associated with FRFT have been carefully explored in some papers such as [3,4,16], which effectively enrich the ensemble of FRFT. However, up till now there has been no reported article covering the discrete generalized uncertainty rela tions associated with discrete linear canonical transform (DLCT) that is the generalization of FRFT. From the viewpoint of engineering application, discrete data are widely used. Hence, there is great need to explore dis crete generalized uncertainty relations. DLCT is the dis crete version of LCT [5,6], which is applied in practical engineering fields. In this article we will discuss the en tropic uncertainty relations [7,8] on LCT. In this paper, we made some contributions such as fol lows. The first contribution is that we extend the tradi tional HausdorffYoung inequality to the DLCT domain with finite supports. It is shown that these bounds are connected with lengths of the supports and LCT parame ters. The second contribution is that we derived the Shannon entropic uncertainty principle in LCT domain for discrete data, based on which we also derived the conditions when these uncertainty relations have the equalities via Lagrange optimization. The third contribu tion is that we derived the Renyi entropic uncertainty principle in DLCT domain. As far as we know, there have been no reported papers covering these generalized discrete entropic uncertainty relations on LCT. 2. Preliminaries 2.1. LCT and DLCT Before discussing the uncertainty principle, we introduce some relevant preliminaries. Here we first briefly review the definition of LCT. For given analog signal 12 tLRLR and 21ft (where 2 t denotes the norm of function 2 l t), its LCT [5,6] is defined as 22 2 22 2 ,d 12ee ed0,1 e0 AA A iduiut iat bbb icdu FuF ftftKutt ibftt bad bc dfdu b (1)
Generalized Discrete Entropic Uncertainty Relations on Linear Canonical Transform 424 where 22 22 ,12eee iduiut iat bb b A Kut ib , and is the complex unit, is the transform pa Zni ab Acd rameter defined as that in [5,6]. In addition, AB Fft ft. If 1 B , 1,d AA tFuKut u, i.e., the in verse LCT reads: 1,d AA tFuKut u . Let 123 ,,,, 1,2, 3, , N Xxxx x xx xNC be a discrete time series with length N and 21X . Assume its DLCT (discrete FLCT) 123 ˆˆˆˆ ˆ ,,,, N xxxx C under the transform pa rameter . Then the DLCT [5] can be written as 2 2 2 22 1 1 ˆ1eee ,,1, ian idk ikn NbNbbN l N A l . kibN x uknxn nkN n . (2) Also, we can rewrite the definition (2) as ˆAA UX, where , AA N Clearly, for DLCT we have the following property [5]: Uukn . 2 2 AA In the following, we will assume that the transform parameter . Note the main difference between the discrete and analog definitions is the length: one is finite and discrete and the other one is infinite and continuous. ˆ1XUX . 0b 2.2. Shannon Entropy and Rényi Entropy For any discrete random variable 1, , n n n px N and its probability density function , the Shannon entropy [9] and the Rényi Entropy [10] are defined as, respectively 1ln N nn nn xpxp x , 1 1ln 1 N nn n Hx px . Hence, in this paper, we know that for any DLCT 123 ˆˆˆˆ ˆ ,,,, AN xxxx C (with 21X and 2 2), the Shannon entropy and the Ré nyi Entropy [13] associated with DLCT are defined as, respectively ˆ1 AA XUX 22 1 ˆˆˆ ln N AAA n xxnx 2 1 1 ˆˆ ln 1 N AA n Hx xn . Clearly, if 1 as shown in [13], ˆˆ AA xHx . 2.3. Discrete HausdorffYoung Inequality on DLCT Lemma 1: For any given discrete time series 123 ,,, , 1,2,3, , N Xxxx x xx xNC n, with length N and 21X , is the DLCT transform matrix associated with the transform parameter AB UU 11 11 ab Acd (22 22 ab Bcd , respectively), then we can obtain the generalized discrete HausdorffYoung ine quality 2 2 12 21 p p AB qp UXNab abUX with 1p2 and 11 1 pq . Proof: Let 123 ,,, , 1,2,3, , N Xxxx x xx xNC be a discrete time series with length N and its DLCT 123 ˆˆˆ ˆˆ ,,, , CN xxxx C with ˆCC UX and the transform parameter ab Ccd . Since 21X , 2 2 ˆ1 XUX BC from Parseval’s theorem. Here 1 22 1 2 N n n Xx . Clearly, we can ob tain the inequality [13]: 1 CC UXM X with C MU . Here sup CC l Uu l with ,1,, CC UullN. Hence, we have 1 CC UXM X with CC MU . Then from Riesz’s theorem [11,12], we can obtain the discrete HausdorffYoung inequality [11,12] 2p p CC q UX MX with 1p2 and Open Access JSIP
Generalized Discrete Entropic Uncertainty Relations on Linear Canonical Transform 425 11 1 pq . Set , then [5], we obtain 1 CAB UU 1 C AB B UU UU 1 A 1 2p p AC Bq UU XMX with 11 CA AB B MU UU . Let 1 B, then B YUX UY . In addition, from the property of DLCT [5] we can have 11 12 21 1 A AB B MUU Nab ab . Hence we can obtain from the above equations 1 2p p AB qp AB UYMUY with 1 12 21 1 AB MNab ab . Since the value of can be taken arbitrarily in , can also be taken arbitrarily in . Therefore, we can obtain the lemma. N C YN C Clearly, this lemma is the discrete version of Haus dorffYoung inequality. In the next sections, we will use this lemma to prove the new uncertainty relations. 3. The Uncertainty Relations 3.1. Shannon Entropic Principle Theorem 1: For any given discrete time series 123 ,,,, 1,2,3, , N Xxxx x xx xNC with length N and 2, 1X ˆˆ AB x is the DLCT se ries associated with the transform parameter 11 11 ab Acd (, respectively), 22 22 ab Bcd AB NN counts the nonzero elements of ˆA (ˆ , respectively), then we can obtain the generalized discrete Shannon en tropic uncertainty relation 12 21 ˆˆ ln,,1, , AB Hx nHxm Nab abnmN (3) where 22 1 ˆˆˆ ln N AA n Hxxn xn A and 22 1 ˆˆˆ ln N BBB m Hxx mx m which are Shannon entropies. The equality in (3) holds iff 1 ˆA A xN and 1 ˆB xN . Proof: From lemma 1, we have 1 2 2 12 211 1 1 1 ˆ 1 ˆ pp Np pB m p pp Np A n Nababx m xn . Take natural logarithm in both sides in above inequal ity, we can obtain 0Tp, where 12 211 1 1 21 ˆ ln ln 2 1ˆ ln N B m p Np A n p TpNababx m pp pxn p Since 1p2 and 2 and Parseval equality, we know 1X 2T0 . Note if 0Tp12p . Hence, 0Tp if 2p . Since 12 21 22 1 1 1 1 21 1 1 1 1 11 ˆ ln ln ˆˆ ln 1 ˆ 1ˆ ln ˆˆ ln 1 1ˆ N B m p N BB m p N B m p Np A n p Np AA n p Np A n TpNab abxm pp xm xm pxm xn p xn xn pp xn , we can obtain the final result in theorem 1 by setting p = 2. Now consider when the equality holds. From theorem 1, that the equality holds in (3) implies that ˆˆ AB xHx reaches its minimum bound, which means that Minimize ˆˆ AB xHx subject to 22 ˆˆ1 AB xx , i.e. Minimize 22 1 22 1 ˆˆ ln ˆˆ ln N AA n N BB m xn xn xm xm , , subject to 22 11 AB nn ˆˆ1 NN xn xn . To solve this problem let us consider the following Lagrangian Open Access JSIP
Generalized Discrete Entropic Uncertainty Relations on Linear Canonical Transform Open Access JSIP 426 22 1 22 1 22 12 11 ˆˆ ln ˆˆ ln ˆˆ 11 N AA n N BB m NN AB nn Lxnxn xm xm xn xn 1 ˆA A xn N . and 1 ˆB xn N , then we have 1221AB NN Nabab and In order to simplify the computation, we set 2 ˆA An np and 2 ˆ n np. Hence we have 12 21 ˆˆln AB xHxNabab. 1 ln 10 A n A n Lp p , 3.2. Rényi Entropic Principle 2 ln 10 B n B n Lp p , Theorem 2: For any given discrete time series 123 ,,, , 1,2,3, , N Xxxx x xx xNC 11 NA n np , with length N and 21X , ˆˆ AB x is the DLCT series 11 NB n np . associated with the transform parameter 11 11 ab Acd (22 22 ab Bcd , respectively), counts the non AB NN Solving the above equations, we finally obtain 1 ˆA A xn N , 1 ˆB xn N . From the definition of Shannon entropy, we know that if ˆln AA xN and ˆln B xN, then 12 21 ˆˆln AB xHxNabab. In addition, we also can obtain 12 21AB NNN abab . zero elements of ˆA (ˆ , respectively), then we can obtain the generalized discrete Renyi entropic uncer tainty relation 12 21 ˆˆ ln 111 with1and2 2 AB xHx Nabab (4) From the above proof, we know that 1 ˆA A xn N and 1 ˆB xn N imply that ˆA m and ˆB n where 2 1 1 ˆˆ ln 1 N AA m Hx xm , can be complex values, and only if their amplitudes are constants, the equality will hold. Now we can obtain the following corollary out of above analysis. 2 1 1 ˆˆ ln 1 N BB n Hx xn , Corollary 1: For any given discrete time series 123 ,,,, 1,2,3, , N Xxxx x xx xNC which are Rényi entropies. Proof: In lemma 1, set 2q and 2p , we have 11 2 and 112 . Then from lemma 1, we ob with length N and 21X , ˆˆ AB x is the DLCT series associated with the transform parameter 11 11 ab Acd (, respectively), counts the non 22 22 ab Bcd btain 1 22 1 1 122 2 12 211 ˆ ˆ N A m N B n xm Nababx n . AB NN zero elements of ˆA (ˆ , respectively), if Take the square of the above inequality, we have 11 1 22 12 21 11 ˆˆ NN AB mn xmNab abxn . Take the power 1 of both sides in above inequallity, we obtain
Generalized Discrete Entropic Uncertainty Relations on Linear Canonical Transform 427 1 21 1 1 12 1 12 211 ˆ ˆ N A m N B n xm Nababxn , i.e., 1 12 1 12 211 1 21 1 ˆ 1 ˆ N B n N A m Nababxn xm . (5) Take the natural logarithm on both sides of (5), we can obtain 22 11 12 21 11 ˆˆ ln ln 11 ln . NN BA nm xn xm Nab ab Clearly, as 1 and 1 , the Renyi entropy reduces to Shannon entropy, thus the Renyi entropic un certainty relation in (4) reduces to the Shannon entropic uncertainty relation (3). Hence the proof of equality in theorem 2 is trivial according to the proof of theorem 1. Note that although Shannon entropic uncertainty rela tion can be obtained by Rényi entropic uncertainty rela tion, we still discuss them separately in the sake of inte grality. 3.3. Another Shannon Entropic Principle via Sampling The discrete Shannon entropy can be defined as ln kk k Ess s (6) where k is the density function of variable . Discrete Rényi entropy can be defined as follows: 1ln 1k k Hx x (7) when 1 , discrete Rényi entropy tend to discrete Shannon entropy. In order to obtain the discrete spectrum, the sampling must be done. For two continuous functions’ DLCT A u and B v with the transform parameter 11 11 ab Acd (22 22 ab Bcd , respectively), we set the sampling periods 1 and 2 T and assume that they sat isfy the Shannon sampling theorem [16]. Set T 1 1 2 2 12 12 d d kT kA kT lT lB lT uFu vFv u v (8) Therefore 1 1 1 22 dd kT AA kT k uu Fu u (9) 2 2 1 22 dd lT BB lT l vv Fv v (10) Since when 1 , xx is a convex function, and when 1 , yy is a concave function, we have the following inequalities 11 11 11 22 11 11 dd kT kT AA kT kT uu Fu TT u (11) 22 22 11 22 22 11 dd lT lT BB lTlT vv Fvv TT (12) Therefore 11 11 11 22 2 1 11 1 1 dd d kT kT AA A kT kT kk k FuuFuuTFu uTu T k . 22 22 11 22 2 1 22 1 dd d lT lT BB B lT lT ll l l vvFvvTFv vTv v , i.e., 21 1 d A k Fu uTu k (13) 21 2 d B l l vvT v . (14) Therefore 112 11 11 11 1221 12 12 21 1 kl kl ababTuTv ab ab (15) Open Access JSIP
Generalized Discrete Entropic Uncertainty Relations on Linear Canonical Transform 428 Take the power of 1 on the both sides of above equation and use the relation between and , we have 1 1 1 21 12 11 1 11 21 1 12 21 12 21 π1 1 π l l k k TT v ab abu ab ab (16) Take logarithm on both sides of above equation 12 21 12 ln πln π 11 ln lnln 11 2121 lk lk ab ab vu TT (17) That is, 12 21 12 ln πln π ln 2121 BA abab HH TT (18) If 111 1 , ,,cos,sin ,sin,cosabcd and 222 2 , , ,cos,sin,sin,cosabcd , then we have 12 1 1 2 cos sincos sin ln πln π ln 2121 l l HHT v TT when 2ππ2nn Z and , we have the traditional case 2πll Z 12 ln πln π ln 2121 HT T. (19) Specially, when 1 , 1 , have 111 12 2 22 12 ,,,, , , 12 21 2 ln 2π1ln abcdabc d TT EE ab ab (20) where, 11 11 2 11 dln d kT kT AAA kT kT k EFuuF 2 uu , 22 22 22 11 dln d lT lT BB B lT lT l EFvvF vv . 4. Conclusion In this article, we extended the entropic uncertainty rela tions in DLCT domains. We first introduced the general ized discrete HausdorffYoung inequality. Based on this inequality, we derived the discrete Shannon entropic un certainty relation and discrete Rényi entropic uncertainty relation. Interestingly, when the variable’s amplitude is equal to the constant, i.e. the inverse of the square root of number of nonzero elements, the equality holds in the uncertainty relation. In addition, the product of the two numbers of nonzero elements is equal to 12 21 Nab ab, i.e., 12 21 NNN abab . On one hand, these new uncertainty relations enrich the ensemble of uncertainty principles, and on the other hand, these derived bounds yield new understanding of discrete signals in new transform domain. 5. Acknowledgements This work was fully supported by the NSFCs (61002052, 60975016, 61250006). REFERENCES [1] R. Ishii and K. Furukawa, “The Uncertainty Principle in Discrete Signals,” IEEE Transactions on Circuits and Systems, Vol. 33, No. 10, 1986, pp. 10321034. [2] L. C. Calvez and P. Vilbe, “On the Uncertainty Principle in Discrete Signals,” IEEE Transactions on Circuits and SystemsII: Analog and Digital Signal Processing, Vol. 39, No. 6, 1992, pp. 394395. http://dx.doi.org/10.1109/82.145299 [3] S. Shinde and M. G. Vikram, “An Uncertainty Principle for Real Signals in the Fractional Fourier Transform Do main,” IEEE Transactions of Signal Processing, Vol. 49, No. 11, 2001, pp. 25452548. Open Access JSIP
Generalized Discrete Entropic Uncertainty Relations on Linear Canonical Transform 429 http://dx.doi.org/10.1109/78.960402 [4] G. L. Xu, X. T. Wang and X. G. Xu, “Generalized En tropic Uncertainty Principle on Fractional Fourier Trans form,” Signal Processing, Vol. 89, No. 12, 2009, pp. 26922697. http://dx.doi.org/10.1016/j.sigpro.2009.05.014 [5] R. Tao, B. Deng and Y. Wang, “Theory and Application of the Fractional Fourier Transform,” Tsinghua Univer sity Press, Beijing, 2009. [6] S. C. Pei and J. J. Ding, “Eigenfunctions of Fourier and Fractional Fourier Transforms with Complex Offsets and Parameters,” IEEE Trans Circuits and SystemsI: Regular Papers, Vol. 54, No. 7, 2007, pp. 15991611. [7] T. M. Cover and J. A. Thomas, “Elements of Information Theory,” 2nd Edition, John Wiley &Sons, Inc., 2006. [8] H. Maassen, “A Discrete Entropic Uncertainty Relation,” Quantum Probability and Applications, SpringerVerlag, New York, 1988, pp. 263266. [9] C. E. Shannon, “A Mathematical Theory of Communica tion,” The Bell System Technical Journal, Vol. 27, 1948, pp. 379656. http://dx.doi.org/10.1002/j.15387305.1948.tb01338.x [10] A. Rényi, “On Measures of Information and Entropy,” Proceedings of the 4th Berkeley Symposium on Mathe matics, Statistics and Probability, 1960, p. 547. [11] G. Hardy, J. E. Littlewood and G. Pólya, “Inequalities,” 2nd Edition, Press of University of Cambridge, Cam bridge, 1951. [12] D. Amir, T. M. Cover and J. A. Thomas, “Information Theoretic Inequalities,” IEEE Transactions on Informa tion Theory, Vol. 37, No. 6, 2001, pp. 15011508. [13] A. Dembo, T. M. Cover and J. A. Thomas, “Information Theoretic Inequalities,” IEEE Transactions on Informa tion Theory, Vol. 37, No. 6, 1991, pp. 15011518. http://dx.doi.org/10.1109/18.104312 [14] G. L. Xu, X. T. Wang and X. G. Xu, “The Logarithmic, Heisenberg’s and ShortTime Uncertainty Principles As sociated with Fractional Fourier Transform,” Signal Proc essing, Vol. 89, No. 3, 2009, pp. 339343. http://dx.doi.org/10.1016/j.sigpro.2008.09.002 [15] G. L. Xu, X. T. Wang and X. G. Xu, “Generalized Un certainty Principles Associated with Hilbert Transform Signal,” Image and Video Processing, 2013. [16] G. L. Xu, X. T. Wang and X. G. Xu, “The Entropic Un certainty Principle in Fractional Fourier Transform Do mains,” Signal Processing, Vol. 89, No. 12, 2009, pp. 26922697. http://dx.doi.org/10.1016/j.sigpro.2009.05.014 [17] A. Stern, “Sampling of Linear Canonical Transformed Signals,” Signal Processing, Vol. 86, No. 7, 2006, pp. 14211425. http://dx.doi.org/10.1016/j.sigpro.2005.07.031 [18] G. L. Xu, X. T. Wang and X. G. Xu, “Three Cases of Uncertainty Principle for Real Signals in Linear Canoni cal Transform Domain,” IET Signal Processing, Vol. 3, No. 1, 2009, pp. 8592. http://dx.doi.org/10.1049/ietspr:20080019 [19] A. Stern, “Uncertainty Principles in Linear Canonical Transform Domains and Some of Their Implications in Optics,” Journal of the Optical Society of America, Vol. 25, No. 3, 2008, pp. 647652. http://dx.doi.org/10.1364/JOSAA.25.000647 [20] G. L. Xu, X. T. Wang and X. G. Xu, “Uncertainty Ine qualities for Linear Canonical Transform,” IET Signal Processing, Vol. 3, No. 5, 2009, pp. 392402,. http://dx.doi.org/10.1049/ietspr.2008.0102 Open Access JSIP
