access icon free Performance analysis of partial support recovery and signal reconstruction of compressed sensing

© The Institution of Engineering and Technology
Received 24/05/2011, Accepted 09/08/2013, Revised 26/07/2013, Published 25/09/2013

Recent work in the area of compressed sensing mainly focuses on the perfect recovery of the entire support for sparse signals. However, partial support recovery, where a part of the signal support is correctly recovered, may be adequate in many practical scenarios. In this study, in the high-dimensional and noisy setting, the authors develop the probability of partial support recovery of the optimal maximum-likelihood (ML) algorithm. When a large part of the support is available, the asymptotic mean-square-error (MSE) of the reconstructed signal is further developed. The simulation results characterise the asymptotic performance of the ML algorithm for partial support recovery, and show that there exists a signal-to-noise ratio (SNR) threshold, beyond which the increase of SNR cannot bring any obvious MSE gain.

Inspec keywords: compressed sensing; probability; signal reconstruction; maximum likelihood estimation; mean square error methods

Other keywords: signal reconstruction; sparse signals; asymptotic mean-square-error; partial support recovery; compressed sensing; MSE gain; SNR; optimal maximum-likelihood algorithm; ML algorithm

Subjects: Signal processing and detection; Signal processing theory; Other topics in statistics; Other topics in statistics; Interpolation and function approximation (numerical analysis); Interpolation and function approximation (numerical analysis)

References

    1. 1)
    2. 2)
    3. 3)
    4. 4)
      • 11. Hormati, A., Karbasi, A., Mohajer, S., Vetterli, M.: ‘An estimation theoretic approach for sparsity pattern recovery in the noisy setting’. arXiv preprint arXiv: 0911.4880, 2009.
    5. 5)
    6. 6)
    7. 7)
    8. 8)
    9. 9)
    10. 10)
    11. 11)
    12. 12)
    13. 13)
      • 10. Reeves, G.: ‘Sparse signal sampling using noisy linear projections’. Master's thesis, EECS Department, University of California, Berkeley, 2008, Available at http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-3.html.
    14. 14)
    15. 15)
    16. 16)
    17. 17)
    18. 18)
      • 3. Fletcher, A.K.: ‘Estimation via sparse approximation: error bounds and random frame analysis’. Master's thesis, University of California, Berkeley, 2005.
    19. 19)
      • 23. Tulino, A., Verdu, S.: ‘Random matrix theory and wireless communications’ (Publisher Inc., MS, 2004).
    20. 20)
      • 16. Gradshteyn, I.S., Ryzhik, I.M.: ‘Table of integrals, series and products’ (Academic Press, New York, 2000, 6th edn.).
    21. 21)
      • 13. Tropp, J.A., Gilbert, A.C.: ‘Signal recovery from random measurements via orthogonal matching pursuit’, IEEE Trans. Inf. Theory, 2007, 53, (12), pp. 4655–4666 (doi: 10.1109/TIT.2007.909108).
    22. 22)
      • 12. Rad, K.R.: ‘Nearly sharp sufficient conditions on exact sparsity pattern recovery’, IEEE Trans. Inf.Theory, 2011, 57, (7), pp. 4672–4679 (doi: 10.1109/TIT.2011.2145670).
    23. 23)
      • 5. Ba, K.D., Indyk, P.: ‘Sparse recovery with partial support knowledge’. Proc. 14th Int. Workshop and 15th Int. Conf. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 2011, pp. 26–37.
    24. 24)
      • 14. Needell, D., Tropp, J.A.: ‘CoSaMP: iterative signal recovery from incomplete and inaccurate samples’, Appl. Comput. Harmon. Anal., 2009, 26, (3), pp. 301–321 (doi: 10.1016/j.acha.2008.07.002).
    25. 25)
      • 20. Nagaraja, H.N., Abo-Eleneen, Z.A.: ‘Fisher information in order statistics’, Pakistan J. Stat., 2003, 19, (1), pp. 161–173.
    26. 26)
      • 11. Hormati, A., Karbasi, A., Mohajer, S., Vetterli, M.: ‘An estimation theoretic approach for sparsity pattern recovery in the noisy setting’. arXiv preprint arXiv: 0911.4880, 2009.
    27. 27)
      • 1. Wang, W., Wainwright, M.J., Ramchandran, K.: ‘Information theoretic limits on sparse signal recovery: dense versus sparse measurement matrices’, IEEE Trans. Inf. Theory, 2010, 56, (6), pp. 2967–2979 (doi: 10.1109/TIT.2010.2046199).
    28. 28)
      • 21. Nielsen, J.: ‘The distribution of volume reductions induced by isotropic random projections’, Adv. Appl. Probab., 1999, 31, (4), pp. 985–994 (doi: 10.1239/aap/1029955254).
    29. 29)
      • 7. Jacques, L.: ‘A short note on compressed sensing with partially known signal support’, Signal Process., 2010, 90, (12), pp. 3308–3312 (doi: 10.1016/j.sigpro.2010.05.025).
    30. 30)
      • 19. Stankovic, S., Orovic, I., Amin, M.: ‘L-statistics based modification of reconstruction algorithms for compressive sensing in the presence of impulse noise’, Signal Process., 2013, 93, (11), pp. 2927–2931 (doi: 10.1016/j.sigpro.2013.04.022).
    31. 31)
      • 8. Akcakaya, M., Tarokh, V.: ‘Noisy compressive sampling limits in linear and sublinear regimes’. Proc. Conf. Information Sciences and Systems, 2008, pp. 1–4.
    32. 32)
      • 6. Friedlander, M.P., Mansour, H., Saab, R., Yilmaz, O.: ‘Recovering compressively sampled signals using partial support information’, IEEE Trans. Inf. Theory, 2012, 58, (2), pp. 1122–1134 (doi: 10.1109/TIT.2011.2167214).
    33. 33)
      • 3. Fletcher, A.K.: ‘Estimation via sparse approximation: error bounds and random frame analysis’. Master's thesis, University of California, Berkeley, 2005.
    34. 34)
      • 17. Xu, W., Lin, J., Niu, K., He, Z.: ‘On the performance of compressed sensing with partially correct support’, Wirel. Pers. Commun., 2013, 69, (4), pp. 1877–1884 (doi: 10.1007/s11277-012-0668-5).
    35. 35)
      • 9. Akcakaya, M., Tarokh, V.: ‘Shannon theoretic limits on noisy compressive sampling’, IEEE Trans. Inf. Theory, 2010, 56, (1), pp. 492–504 (doi: 10.1109/TIT.2009.2034796).
    36. 36)
      • 2. Fletcher, A.K., Rangan, S., Goyal, V.K.: ‘Necessary and sufficient conditions for sparsity pattern recovery’, IEEE Trans. Inf. Theory, 2009, 55, (12), pp. 5758–5772 (doi: 10.1109/TIT.2009.2032726).
    37. 37)
      • 22. Evans, J., Tse, D.N.C.: ‘Large system performance of linear multiuser receivers in multipath fading channels’, IEEE Trans. Inf. Theory, 2000, 46, (6), pp. 2059–2078 (doi: 10.1109/18.868478).
    38. 38)
      • 18. Stankovic, L.J., Stankovic, S., Orovic, I., Amin, M.: ‘Robust time-frequency analysis based on the L-estimation and compressive sensing’, IEEE Signal Process. Lett., 2013, 20, (5), pp. 499–502 (doi: 10.1109/LSP.2013.2252899).
    39. 39)
      • 10. Reeves, G.: ‘Sparse signal sampling using noisy linear projections’. Master's thesis, EECS Department, University of California, Berkeley, 2008, Available at http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-3.html.
    40. 40)
      • 4. Vaswani, N., Lu, W.: ‘Modified-CS: modifying compressive sensing for problems with partially known support’, IEEE Trans. Signal Process., 2010, 58, (9), pp. 4595–4607 (doi: 10.1109/TSP.2010.2051150).
    41. 41)
      • 15. Chen, S.S., Donoho, D.L., Saunders, M.A.: ‘Atomic decomposition by basis pursuit’, SIAM J. Sci. Comput., 1999, 20, (1), pp. 33–61 (doi: 10.1137/S1064827596304010).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-spr.2011.0205
Loading

Related content

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