Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free A reduced l 2–l 1 model with an alternating minimisation algorithm for support recovery of multiple measurement vectors

© The Institution of Engineering and Technology
Received 06/03/2012, Accepted 30/01/2013, Revised 18/11/2012, Published

The authors address the problem of support recovery with multiple measurement vectors (MMV) in this study. The scale of an MMV is reduced by using the singular value decomposition technique, and a novel l 2–l 1 minimisation model with two variables for the reduced MMV is proposed. Then a new alternating minimisation algorithm based on the alternating direction method of multipliers is presented. They prove the globally convergence property of the presented algorithm. Several numerical simulations both on random data and for direction-of-arrival estimation are conducted to evaluate the performance of the proposed method for support recovery of MMV.

Inspec keywords: vectors; numerical analysis; convergence of numerical methods; minimisation; direction-of-arrival estimation; singular value decomposition

Other keywords: multiple measurement vector support recovery; singular value decomposition technique; l2-l1 minimisation model; alternating minimisation algorithm; numerical simulations; reduced l2-l1 model; globally convergence; alternating direction method; MMV; random data; direction-of-arrival estimation

Subjects: Optimisation techniques; Signal processing theory; Signal processing and detection; Linear algebra (numerical analysis); Linear algebra (numerical analysis); Optimisation techniques

References

    1. 1)
      • 20. Chen, J., Huo, X.M.: ‘Theoretical results on sparse representations of multiple-measurement vectors’, IEEE Trans. Signal Process., 2006, 54, (12), pp. 4634–4643.
    2. 2)
      • 13. Daubechies, I., Defrise, M., De Mol, C.: ‘An iterative thresholding algorithm for linear inverse problems with a sparsity constraint’, Commun. Pure Appl. Math., 2004, 57, pp. 1413–1457.
    3. 3)
      • 24. Lu, H.T., Long, X.Z., Lv, J.Y.: ‘A fast algorithm for recovery of jointly sparse vectors based on the alternating direction methods’, J. Mach. Learn. Res. Proc. Track, 2011, 15, pp. 461–469.
    4. 4)
      • 22. Mishali, M., Eldar, Y.C.: ‘Reduce and Boost: Recovering arbitrary sets of jointly sparse vectors’, IEEE Trans. Signal Process., 2008, 56, (10), pp. 4692–4701.
    5. 5)
      • 2. Elad, M.: ‘Sparse and redundant representations: from theory to applications in signal and image processing’ (Springer, NY, 2011).
    6. 6)
      • 5. Qi, C., Wang, X., Wu, L.: ‘Underwater acoustic channel estimation based on sparse recovery algorithms’, IET Signal Process., 2011, 5, (8), pp. 739–747.
    7. 7)
      • 21. Cotter, S.F., Rao, B.D., Engan, K., Kreutz-Delgado, K.: ‘Sparse solution to linear inverse problems with multiple measurement vectors’, IEEE Trans. Signal Process., 2005, 53, (7), pp. 2477–2488.
    8. 8)
      • 3. Aelterman, J., Luong, H.Q., Goossens, B., Pižurica, A., Philips, W.: ‘Augmented Lagrangian based reconstruction of non-uniformly sub-Nyquist sampled MRI data’, Signal Process., 2011, 91, (12), pp. 2731–2742.
    9. 9)
      • 32. Figueiredo, M.A.T., Bioucas-Dias, J.M.: ‘Restoration of Poissonian images using alternating direction optimization’, IEEE Trans. Image Process., 2010, 19, (12), pp. 3133–3145.
    10. 10)
      • 12. Tibshirani, R.: ‘Regression shrinkage and selection via the lasso’, J. R. Stat. Soc. B, 1996, 58, (1), pp. 267–288.
    11. 11)
      • 16. Fornasier, M., Rauhut, H.: ‘Recovery algorithms for vector valued data with joint sparsity constraints’, SIAM J. Numer. Anal., 2008, 46, (2), pp. 577–613.
    12. 12)
      • 25. Jin, Y.Z., Rao, B.D.: ‘Support recovery of sparse signals in the presence of multiple measurement vectors’, arXiv:1109.1895v1 [cs.IT], 2011.
    13. 13)
      • 34. Esser, E.: ‘Applications of Lagrangian-based alternating direction methods and connections to split Bregman’. CAM Report, 2000, pp. 09–31.
    14. 14)
      • 6. Pati, Y.C., Rezaiifar, R., Krishnaprasad, P.S.: ‘Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition’. Proc. 27th Annu. Asilomar Conf. Signals Systems and Computers, 1993, 1, pp. 40–44.
    15. 15)
      • 18. Cabrera, S.D., Parks, T.W.: ‘Extrapolation and spectral estimation with iterative weighted norm modification’, IEEE Trans. Acoust. Speech Signal Process., 1991, 39, (4), pp. 842–851.
    16. 16)
      • 26. Afonso, M., Bioucas-Dias, J., Figueiredo, M.A.T.: ‘Fast image recovery using variable splitting and constrained optimization’, IEEE Trans. Image Process., 2010, 19, (9), pp. 2345–2356.
    17. 17)
      • 9. Gorodnitsky, I.F., Rao, B.D.: ‘Sparse signal reconstructions from limited data using FOCUSS: a re-weighted minimum norm algorithm’, IEEE Trans. Signal Process., 1997, 45, (3), pp. 600–616.
    18. 18)
      • 37. Eckstein, J., Bertsekas, D.: ‘On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators’, Math. Program., 1992, 55, (3), pp. 293–318.
    19. 19)
      • 31. Goldstein, T., Osher, S.: ‘The split Bregman method for l1 regularized problems’, SIAM J. Imaging Sci., 2009, 2, (2), pp. 323–343.
    20. 20)
      • 4. Malioutov, D., Cetin, M., Willsky, A.S.: ‘A sparse signal reconstruction perspective for source localization with sensor arrays’, IEEE Trans. Signal Process., 2005, 53, (8), pp. 3010–3022.
    21. 21)
      • 8. Gorodnitsky, I.F., George, J.S., Rao, B.D.: ‘Neuromagnetic source imaging with FOCUSS: a recursive weighted minimum norm algorithm’, J. Electroencephalog. Clin. Neurophysiol., 1995, 95, (4), pp. 231–251.
    22. 22)
      • 36. Arrow, K.J., Hurwicz, L., Uzawa, H.: ‘Studies in linear and non-linear programming’ (Stanford University Press, CA, 1958).
    23. 23)
      • 23. Eldar, Y.C., Mishali, M.: ‘Robust recovery of signals from a structured union of subspaces’, IEEE Trans. Inf. Theory, 2009, 55, (11), pp. 5302–5316.
    24. 24)
      • 10. Wright, S.J., Nowak, R.D., Figueiredo, M.A.T.: ‘Sparse reconstruction by separable approximation’, IEEE Trans. Signal Process., 2009, 57, (8), pp. 2479–2493.
    25. 25)
      • 28. Tropp, J.A., Gilbert, A.C., Strauss, M.J.: ‘Algorithms for simultaneous sparse approximation. Part I: greedy pursuit’, Signal Process., 2006, 86, (3), pp. 572–588.
    26. 26)
      • 35. Iusem, A.N.: ‘Augmented Lagrangian methods and proximal point methods for convex optimization’, Investigacion Oper., 1999, 8, pp. 11–49.
    27. 27)
      • 29. Kim, J.M., Lee, O.K., Ye, J.C.: ‘Compressive MUSIC: revisiting the link between compressive sensing and array signal processing’, IEEE Trans. Inf. Theory, 2012, 58, (1), pp. 278–301.
    28. 28)
      • 14. Yin, W., Osher, S., Goldfarb, D., Darbon, J.: ‘Bregman iterative algorithm for l1 minimization with applications to compressed sensing’, SIAM J. Imaging Sci., 2008, 1, (1), pp. 143–168.
    29. 29)
      • 19. Ji, S., Dunson, D., Carin, L.: ‘Multi-task compressive sensing’, IEEE Trans. Signal Process., 2008, 57, (1), pp. 92–106.
    30. 30)
      • 33. Setzer, S.: ‘Operator splittings, Bregman methods and frame shrinkage in image processing’, Int. J. Comput. Vis., 2011, 92, pp. 265–280.
    31. 31)
      • 15. Figueiredo, M.A.T., Nowak, R.D., Wright, S.J.: ‘Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems’, IEEE Trans. Signal Process., 2007, 1, (4), pp. 586–597.
    32. 32)
      • 1. Tropp, J.A., Wright, S.J.: ‘Computational methods for sparse solution of linear inverse problems’, Proc. IEEE, 2010, 98, (6), pp. 948–958.
    33. 33)
      • 7. Davis, G., Mallat, S., Avellaneda, M.: ‘Adaptive greedy approximation’, J. Constr. Approx., 1997, 13, pp. 57–98.
    34. 34)
      • 38. Barabell, A.: ‘Improving the resolution performance of eigenstructured-based direction-finding algorithms’. Proc. ICASSP, 1983, pp. 336–339.
    35. 35)
      • 11. Kim, S., Koh, K., Lustig, M., Boyd, S., Gorinvesky, D.: ‘An interiorpoint method for large-scale l1-regularized least squares’, IEEE J. Sel. Top. Signal Process., 2007, 1, (4), pp. 606–617.
    36. 36)
      • 30. Donoho, D.L., Elad, M.: ‘Maximal sparsity representation via l1 minimization’, Proc. Natl Acad. Sci., 2003, 100, pp. 2197–2202.
    37. 37)
      • 17. Majumdar, A., Ward, R.K.: ‘Joint reconstruction of multiecho MR images using correlated sparsity’, Magn. Reson. Imaging, 2011, 29, pp. 899–906.
    38. 38)
      • 27. Chen, S.S.: ‘Basis Pursuit’. PhD dissertation, Stanford University, 1995.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-spr.2012.0078
Loading

Related content

content/journals/10.1049/iet-spr.2012.0078
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address