In this study, some new entropic inequalities on sparse representation for pairs of bases are investigated. First, the generalised Shannon entropic uncertainty principle and the generalised Rényi entropic uncertainty principle via new derived Hausdorff–Young inequality are proved. These new derived uncertainty principles show that signals cannot have unlimited concentration related to minimum entropies in pairs of bases. Second, the conditions of uniqueness of sparse representation under minimum entropies are given. This study also demonstrates that the entropic greedy-like algorithms can achieve the ‘sparsest’ representation for minimum entropies approximately. Third, the relations between the minimum l ₀ solution and minimum entropy are discussed as well. It shows that even if the sparsest representation of l ₀-norm is obtained, the entropy cannot always be the minimum and it is possible that the entropy is limited to a interval. These new derived inequalities will be primarily to contribute to a better understanding of sparse representation in the sense of limited entropic uncertainty bounds. Finally, the experiments are shown to verify the authors’ ideas.

References

1. 1)
  - 34. Victor, D., Murad, O., Tomasz, P.: ‘Resolution in time–frequency’, IEEE Trans. Signal Process., 1999, 47, pp. 783–788 (doi: 10.1109/78.747783).
2. 2)
  - 48. Zarezadeh, S., Asadi, M.: ‘Results on residual Rényi entropy of order statistics and record values’, Inf. Sci., 2010, 180, pp. 4195–4206 (doi: 10.1016/j.ins.2010.06.019).
3. 3)
  - 3. Li, Y.Q., Cichocki, A., Amari, S., et al: ‘Underdetermined blind source separation based on sparse representation’, IEEE Trans. Signal Process., 2006, 54, pp. 423–437 (doi: 10.1109/TSP.2005.861743).
4. 4)
  - 25. Tropp, J.: ‘Greed is good: algorithmic results for sparse approximation’, IEEE Trans. Inf. Theory, 2004, 50, (10), pp. 2231–2242 (doi: 10.1109/TIT.2004.834793).
5. 5)
  - 31. Donoho, D., Huo, X.: ‘Uncertainty principles and ideal atomic decomposition’, IEEE Trans. Inf. Theory, 2001, 47, (7), pp. 2845–2862 (doi: 10.1109/18.959265).
6. 6)
  - 16. Donoho, D.L., Stark, P.B.: ‘Uncertainty principles and signal recovery’, SIAM J. Appl. Math., 1989, 49, pp. 906–930 (doi: 10.1137/0149053).
7. 7)
  - 28. Compressed Sensing. Available at http://www.dsp.ece.rice.edu/CS/.
8. 8)
  - 32. Przebinda, T., DeBrunner, V., Özaydın, M.: ‘The optimal transform for the discrete Hirschman uncertainty principle’, IEEE Trans. Inf. Theory, 2001, 47, pp. 2086–2090 (doi: 10.1109/18.930948).
9. 9)
  - 4. Candes, E., Romberg, J., Tao, T.: ‘Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information’, IEEE Trans. Inf. Theory, 2006, 52, pp. 489–509 (doi: 10.1109/TIT.2005.862083).
10. 10)
  - 30. Lyubarskii, Y., Vershynin, R.: ‘Uncertainty principles and vector quantization’, IEEE Trans. Inf. Theory, 2010, 56, pp. 3491–3501 (doi: 10.1109/TIT.2010.2048458).
11. 11)
  - 1. Billings, S.A., Wei, H.L.: ‘Sparse model identification using a forward orthogonal regression algorithm aided by mutual information’, IEEE Trans. Neural Netw., 2007, 18, pp. 306–310 (doi: 10.1109/TNN.2006.886356).
12. 12)
  - 20. Feuer, A., Nemirovski, A.: ‘On sparse representation in pairs of bases’, IEEE Trans. Inf. Theory, 2003, 49, (6), pp. 1579–1581 (doi: 10.1109/TIT.2003.811926).
13. 13)
  - 16. Shannon, C.E.: ‘A mathematical theory of communication’, Bell Syst. Techn. J., 1948, 27, pp. 379–423, 623–656 (doi: 10.1002/j.1538-7305.1948.tb01338.x).
14. 14)
  - 40. Maassen, H., Uffink, J.B.M.: ‘Generalized entropic uncertainty relations’, Phys. Rev. Lett., 1983, 60, pp. 1103–1106 (doi: 10.1103/PhysRevLett.60.1103).
15. 15)
  - 24. Hyvärinen, A., Oja, E.: ‘Independent component analysis: algorithms and applications’, Neural Netw., 2000, 13, (4–5), pp. 411–430 (doi: 10.1016/S0893-6080(00)00026-5).
16. 16)
  - 13. Donoho, D.L.: ‘Compressed sensing’, IEEE Trans. Inf. Theory, 2006, 52, pp. 1289–1306 (doi: 10.1109/TIT.2006.871582).
17. 17)
  - 49. Li, X.L., Adal, T.: ‘Complex independent component analysis by entropy bound minimization’, IEEE Trans. Circuits Syst. I, Regul. Pap., 2010, 57, (7), pp. 1417–1429 (doi: 10.1109/TCSI.2010.2046207).
18. 18)
  - 43. Guanlei, X., Xiaotong, W., Lijia, Z., et al: ‘New inequalities on sparse representation in Pairs of bases’, IET Signal Process., 2013, 7, (8), pp. 674–683 (doi: 10.1049/iet-spr.2012.0365).
19. 19)
  - 38. Birula, I.B.: ‘Entropic uncertainty relations in quantum mechanics’, in Accardi, L., von Waldenfels, W. (Eds.): ‘Quantum probability and applications II’ (Springer, Berlin, 1985), LectureNotes in Mathematics1136, p. 90.
20. 20)
  - 46. Kapur, J.N., Baciu, G., Kesavan, H.K.: ‘On the relationship between variance and minimum entropy’, Univesity of Waterloo, Waterloo, Ontario, Canada, Intern. Publ., 1994.
21. 21)
  - 47. Yuan, L., Kesavan, H.K.: ‘Minimum entropy and information measure’, IEEE Trans. Syst. Man Cybern. C, Appl. Rev., 1998, 28, pp. 488–491 (doi: 10.1109/5326.704595).
22. 22)
  - 31. Dembo, A., Cover, T.M., Thomas, J.A.: ‘Information theoretic inequalities’, IEEE Trans. Inf. Theory, 2001, 37, (6), pp. 1501–1508 (doi: 10.1109/18.104312).
23. 23)
  - 4. Li, Y.Q., Amari, S., Cichocki, A., et al: ‘Probability estimation for recoverability analysis of blind source separation based on sparse representation’, IEEE Trans. Inf. Theory, 2006, 52, pp. 3139–3152 (doi: 10.1109/TIT.2006.876348).
24. 24)
  - 23. Huo, X., Ni, X.S.: ‘When do stepwise algorithms meet subset selection criteria?’, Ann. Stat., 2007, 35, pp. 870–887 (doi: 10.1214/009053606000001334).
25. 25)
  - 17. Donoho, D.L., Elad, M.: ‘Maximal sparsity representation via l1 minimization’, Proc. Natl. Acad. Sci., 2003, 100, pp. 2197–2202 (doi: 10.1073/pnas.0437847100).
26. 26)
  - 35. Guanlei, X., Xiaotong, W., Xiaogang, X.: ‘Generalized entropic uncertainty principle on fractional Fourier transform’, Signal Process., 2009, 89, pp. 2692–2697 (doi: 10.1016/j.sigpro.2009.05.014).
27. 27)
  - 10. Cevher, V., Krause, A.: ‘Greedy dictionary selection for sparse representation’, IEEE J. Sel. Top. Signal Process., 2011, 5, pp. 979–2011 (doi: 10.1109/JSTSP.2011.2161862).
28. 28)
  - 49. Candes, E.J., Romberg, J., Tao, T.: ‘Stable signal recovery from incomplete and inaccurate measurements’, Commun. Pure Appl. Math., 2006, 59, (8), pp. 1207–1223 (doi: 10.1002/cpa.20124).
29. 29)
  - 45. Kapur, J.N., Baciu, G., Kesavan, H.K.: ‘The MinMax information measure’, Int. J. Syst. Sci., 1995, 26, pp. 1–12 (doi: 10.1080/00207729508929020).
30. 30)
  - 37. Chen, S.S., Donoho, D.L., Saunders, M.A.: ‘Atomic decomposition by basis pursuit’, SIAMJ. Sci. Comput., 1999, 20, pp. 33–61 (doi: 10.1137/S1064827596304010).
31. 31)
  - 2. Bofill, P., Zibulevsky, M.: ‘Underdetermined blind source separation using sparse representations’, Signal Process., 2001, 81, (11), pp. 2353–2362 (doi: 10.1016/S0165-1684(01)00120-7).
32. 32)
  - 37. Renyi, A.: ‘On measures of information and entropy’. Proc. of the Fourth Berkeley Symp. on Mathematics, Statistics and Probability, 1960, p. 547.
33. 33)
  - 26. Pati, Y.C., Rezaiifar, R., Krishnaprasad, P.S.: ‘Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition’. Proc. of the 27th Annual Asilomar Conf. on Signals Systems and Computers, 1–3 November 1993.
34. 34)
  - 24. Li, Y.Q., Cichocki, A., Amari, S., et al: ‘Equivalence probability and sparsity of two sparse solutions in sparse representation’, IEEE Trans. Neural Netw., 2008, 19, pp. 2009–2021 (doi: 10.1109/TNN.2008.2003980).
35. 35)
  - 50. Li, X.L., Adal, T.: ‘Independent component analysis by entropy bound minimization’, IEEE Tran. Signal Process., 2010, 58, (10), pp. 5151–5164 (doi: 10.1109/TSP.2010.2055859).
36. 36)
  - 41. Maassen, H.: ‘A discrete entropic uncertainty relation’, Quantum Probab. Appl., 1988, 5, pp. 263–266.
37. 37)
  - 18. Donoho, D.L.: ‘Neighborly polytopes and sparse solutions of underdetermined linear equations’. Technical Report 2005-4, Statistics Department, Stanford University, Stanford, CA, 2005.
38. 38)
  - 8. Fuchs, J.-J.: ‘On sparse representations in arbitrary redundant bases’, IEEE Trans. Inf. Theory, 2004, 50, (6), pp. 1341–1344 (doi: 10.1109/TIT.2004.828141).
39. 39)
  - 39. Folland, G.B., Sitaram, A.: ‘The uncertainty principle: a mathematical survey’, J. Fourier Anal. Appl., 1997, 3, pp. 207–238 (doi: 10.1007/BF02649110).
40. 40)
  - 13. Delgado, K.K., Murray, J.F., Rao, B.D., et al: ‘Dictionary learning algorithms for sparse representation’, Neural Comput.., 2003, 15, pp. 349–396 (doi: 10.1162/089976603762552951).
41. 41)
  - 44. Hirschman, I.I.: ‘A note on entropy’, Am. J. Math., 1957, 79, (1), pp. 152–156 (doi: 10.2307/2372390).
42. 42)
  - 29. Somaraju, R., Hanlen, L.W.: ‘Uncertainty principles for signal concentration’. Communications Theory Workshop, 2006. Proceedings, 10.1109/AUSCTW.2006.1625252.
43. 43)
  - 2. Candès, E.J., Tao, T.: ‘Decoding by linear programming’, IEEE Trans. Inf. Theory, 2005, 51, (12), pp. 4203–4215 (doi: 10.1109/TIT.2005.858979).
44. 44)
  - 9. Elad, M., Bruckstein, A.M.: ‘A generalized uncertainty principle and sparse representation in pairs of bases’, IEEE Trans. Inf. Theory, 2002, 48, (9), pp. 2558–2567 (doi: 10.1109/TIT.2002.801410).
45. 45)
  - 17. Candès, E.J., Wakin, M.B.: ‘An introduction to compressed sampling’, IEEE Signal Process. Mag., 2008, 25, (2), pp. 21–30 (doi: 10.1109/MSP.2007.914731).
46. 46)
  - 22. Gribonval, R., Nielsen, M.: ‘Sparse representations in unions of bases’, IEEE Trans. Inf. Theory, 2003, 49, pp. 3320–3325 (doi: 10.1109/TIT.2003.820031).
47. 47)
  - 3. Candes, E., Romberg, J.: ‘Sparsity and incoherence in compressive sampling’, Inverse Probl., 2007, 23, pp. 969–985 (doi: 10.1088/0266-5611/23/3/008).
48. 48)
  - 12. Davis, G., Mallat, S., Avellaneda, M.: ‘Adaptive greedy approximations’ (Springer-Verlag, New York, 1997).
49. 49)
  - 42. Miranskyy, A.V., Davison, M., Reesor, R.M., et al: ‘Using entropy measures for comparison of software traces’, Inf. Sci., 2012, 203, pp. 59–72 (doi: 10.1016/j.ins.2012.03.017).
50. 50)
  - 36. Renyi, A.: ‘Some fundamental questions of information theory’, MTA III Oszt. Kozl., 1960.
51. 51)
  - 24. Mallat, S., Zhang, Z.: ‘Matching pursuit in a time frequency dictionary’, IEEE Trans. Signal Process., 1993, 41, (12), pp. 3397–3415 (doi: 10.1109/78.258082).

Entropic uncertainty inequalities on sparse representation

References

Related content