access icon free New inequalities on sparse representation in pairs of bases

In this study, the authors investigated some new inequalities on sparse representation for pairs of bases and frames, which would enrich the theory ensemble. First, for fixed pairs of bases, frames and the signal to be represented, we presented the bounds (which can be used in practice directly) of l 0-norm of signal coefficients by the max/min cross-inner-products, as is of much importance to bases and frames selections in sparse representation. Also, the error bounds associated with the given min cross-inner-products are achieved. Moreover, the equivalence condition between l 0 solution and l 1 solution was achieved via relations of cross-inner-products, as can be applied directly for selection of optimal bases. Finally, the estimation of the parameters of cross-inner-products was shown.

Inspec keywords: signal representation; minimax techniques

Other keywords: signal representation; l0-norm; base-frame pairs; sparse representation; error bounds; max-min cross-inner-products

Subjects: Signal processing and detection; Optimisation techniques; Optimisation techniques; Signal processing theory

References

    1. 1)
      • 19. Davis, G., Mallat, S., Avellaneda, M.: ‘Adaptive greedy approximations’. in Constructive Approximation.Springer-Verlag, New York, 1997, vol. 13, pp. 5798.
    2. 2)
      • 23. Tropp, J.A.: ‘Greed is good’, IEEE Trans. Inf. Theory, 2004, 50, (10), pp. 22312242 (doi: 10.1109/TIT.2004.834793).
    3. 3)
      • 36. [http://www.mathworks.com/products/matlab/].
    4. 4)
      • 24. Huo, X., Ni, X.S.: ‘When do stepwise algorithms meet subset selection criteria?’, Ann. Stat., 2007, 35, (2), pp. 870887 (doi: 10.1214/009053606000001334).
    5. 5)
      • 27. Donoho, D.L., Stark, P.B.: ‘Uncertainty principles and signal recovery’, SIAM J. Appl. Math., 1989, 49, (9), pp. 906930 (doi: 10.1137/0149053).
    6. 6)
      • 20. Mallat, S., Zhang, Z.: ‘Matching pursuits with time-frequency dictionaries’, IEEE Trans. Signal Process., 1993, 41, (12), pp. 33973415 (doi: 10.1109/78.258082).
    7. 7)
      • 10. Donoho, D.L., Elad, M.: ‘Maximal sparsity representation via l1 minimization’, Proc. Natl. Acad. Sci., 2003, 100, (5), pp. 21972202 (doi: 10.1073/pnas.0437847100).
    8. 8)
      • 9. Elad, M., Bruckstein, A.: ‘A generalized uncertainty principle and sparse representation in pairs of bases’, IEEE Trans. Inf. Theory, 2002, 48, (9), pp. 25582567 (doi: 10.1109/TIT.2002.801410).
    9. 9)
      • 35. Zhang, X.D.: ‘Modern signal processing’ (Tsinghua university Press, Beijing, 2002, 2nd edn.), p. 362.
    10. 10)
      • 32. Li, Y., Amari, S.-i.: ‘Two conditions for equivalence of 0-norm solution and 1-norm solution in sparse representation’, IEEE Trans. Neural Netw., 2010, 21, (7), pp. 11891196 (doi: 10.1109/TNN.2010.2049370).
    11. 11)
      • 4. Li, Y.Q., Amari, S., Cichocki, A., Guan, C.T.: ‘Probability estimation for recoverability analysis of blind source separation based on sparse representation’, IEEE Trans. Inf. Theory, 2006, 52, (7), pp. 31393152 (doi: 10.1109/TIT.2006.876348).
    12. 12)
      • 18. Candès, E.J., Romberg, J., Tao, T.: ‘Stable signal recovery from incomplete and inaccurate measurements’, Commun. Pure Appl. Math., 2005, 59, pp. 12071223 (doi: 10.1002/cpa.20124).
    13. 13)
      • 16. Candés, E.J., Tao, T.: ‘Decoding by linear programming’, IEEE Trans. Inf. Theory, 2005, 51, pp. 42034215 (doi: 10.1109/TIT.2005.858979).
    14. 14)
      • 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, (1), pp. 306310 (doi: 10.1109/TNN.2006.886356).
    15. 15)
      • 25. Delgado, K.K., Murray, J.F., Rao, B.D., Engan, K., Lee, T.W., Sejnowski, T.J.: ‘Dictionary learning algorithms for sparse representation’, Neural Comput., 2003, 15, (2), pp. 349396 (doi: 10.1162/089976603762552951).
    16. 16)
      • 8. Candès, E.J., Wakin, M.B.: ‘An introduction to compressive sampling’, IEEE Signal Process. Mag., 2008, 25, (2), pp. 2130 (doi: 10.1109/MSP.2007.914731).
    17. 17)
      • 31. Temlyakov, V.: ‘Nonlinear methods of approximation’, Found. Comput. Math., 2003, 3, pp. 33107 (doi: 10.1007/s102080010029).
    18. 18)
      • 22. Candès, E.J., Romberg, J., Tao, T.: ‘Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information’, IEEE Trans. Inf. Theory, 2006, 52, (2), pp. 489509 (doi: 10.1109/TIT.2005.862083).
    19. 19)
      • 13. Fuchs, J.J.: ‘On sparse representations in arbitrary redundant bases’, IEEE Trans. Inf. Theory, 2004, 50, (6), pp. 13411344 (doi: 10.1109/TIT.2004.828141).
    20. 20)
      • 28. Cevher, V., Krause, A.: ‘Greedy dictionary selection for sparse representation’, IEEE J. Sel. Top. Signal Process., 2011, 5, (5), pp. 9792011 (doi: 10.1109/JSTSP.2011.2161862).
    21. 21)
      • 34. Guanlei, X., Xiaotong, W., Xiaogang, X.: ‘Three cases of uncertainty principle for real signals in linear canonical transform domain’, IET Signal Process., 2009, 3, (8), pp. 8592 (doi: 10.1049/iet-spr:20080019).
    22. 22)
      • 5. Compressed Sensing. Available: [http://www.dsp.ece.rice.edu/CS/].
    23. 23)
      • 30. Gilbert, A.C., Tropp, J.A.: ‘Signal recovery from random measurements via orthogonal matching pursuit University of Michigan’, Technical Report Ann Arbor, MI2005.
    24. 24)
      • 6. Donoho, D.: ‘Compressed sensing’, IEEE Trans. Inf. Theory, 2006, 52, (4), pp. 12891306 (doi: 10.1109/TIT.2006.871582).
    25. 25)
      • 11. Li, Y.Q., Cichocki, A., Amari, S., Xie, S.L., Guan, C.T.: ‘Equivalence probability and sparsity of two sparse solutions in sparse representation’, IEEE Trans. Neural Netw., 2008, 19, (12), pp. 20092021 (doi: 10.1109/TNN.2008.2003980).
    26. 26)
      • 12. Feuer, A., Nemirovski, A.: ‘On sparse representation in pairs of bases’, IEEE Trans. Inf. Theory, 2003, 49, (6), pp. 15791581 (doi: 10.1109/TIT.2003.811926).
    27. 27)
      • 7. Candès, E., Romberg, J.: ‘Sparsity and incoherence in compressive sampling’, Inverse Probl., 2007, 23, (3), pp. 969985 (doi: 10.1088/0266-5611/23/3/008).
    28. 28)
      • 26. Donoho, D.L., Huo, X.: ‘Uncertainty principles and ideal atomic decomposition’, IEEE Trans. Inf. Theory, 2001, 47, (7), pp. 28452862 (doi: 10.1109/18.959265).
    29. 29)
      • 14. Gribonval, R., Nielsen, M.: ‘Sparse representations in unions of bases’, IEEE Trans. Inf. Theory, 2003, 49, (12), pp. 33203325 (doi: 10.1109/TIT.2003.820031).
    30. 30)
      • 21. Pati, Y.C., Rezaiifar, R., Krishnaprasad, P.S.: ‘Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition’. Proc. 27th Annual Asilomar Conf. Signals Systems and Computers, 1–3 November 1993.
    31. 31)
      • 15. Donoho, D.L.: ‘Neighborly polytopes and sparse solutions of underdetermined linear equations’. Technical Report 2005-4, Department of Statistics, Stanford University, Stanford, CA, 2005.
    32. 32)
      • 33. Dembo, A., Cover, T.M., Thomas, J.A.: ‘Information theoretic inequalities’, IEEE Trans. Inf. Theory, 1991, 37, (12), pp. 15011518 (doi: 10.1109/18.104312).
    33. 33)
      • 17. Chen, S., Donoho, D.L., Saunders, M.A.: ‘Atomic decomposition by basis pursuit’, SIAM J. Sci. Comput., 1998, 20, (1), pp. 3361 (doi: 10.1137/S1064827596304010).
    34. 34)
      • 3. Li, Y.Q., Cichocki, A., Amari, S., Ho, D.W.C., Xie, S.L.: ‘Underdetermined blind source separation based on sparse representation’, IEEE Trans. Signal Process., 2006, 54, (2), pp. 423437 (doi: 10.1109/TSP.2005.861743).
    35. 35)
      • 29. Lyubarskii, Y., Vershynin, R.: ‘Uncertainty principles and vector quantization’, IEEE Trans. Inf. Theory, 2010, 56, (7), pp. 34913501 (doi: 10.1109/TIT.2010.2048458).
    36. 36)
      • 2. Bofill, P., Zibulevsky, M.: ‘Underdetermined blind source separation using sparse representations’, Signal Process., 2001, 81, (11), pp. 23532362 (doi: 10.1016/S0165-1684(01)00120-7).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-spr.2012.0365
Loading

Related content

content/journals/10.1049/iet-spr.2012.0365
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading