The recently introduced theory of compressed sensing (CS) enables the recovery of sparse or compressible signals from a small set of non-adaptive measurements, and furthermore, it holds promise for substantially improving the performance by leveraging more signal structures that go beyond simple sparsity. In this study, the authors study the weighted l ₁ minimisation problem for CS reconstruction when partial support information is available. Firstly, they focus on the coherence-based performance guarantees and show that if an estimated support can be obtained with its accuracy and relative size satisfying certain coherence-related conditions, the weighted l ₁ minimisation is then stable and robust under weaker sufficient conditions than that of the analogous standard l ₁ optimisation. Meanwhile, better upper bounds on the reconstruction error could also be achieved. Besides, a novel adaptive alternating direction method of multipliers with iterative support detection is outlined to solve the weighted l ₁ minimisation problem. Simulation results show that the authors’ method achieves good convergence, and obtains improved reconstruction performance in comparison with the conventional methods.

References

1. 1)
  - Y. Wang , J. Yang , W. Yin , Y. Zhang . A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Sci. Comput. , 3 , 248 - 272
2. 2)
  - 17. Liu, H., Song, B., Qin, H., Qiu, Z.: ‘An adaptive-ADMM algorithm with support and signal value detection for compressed sensing’, IEEE Signal Process. Lett., 2013, 20, (4), pp. 315–318 (doi: 10.1109/LSP.2013.2245893).
3. 3)
  - E. Candes , J. Romberg , T. Tao . Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. , 8 , 1207 - 1223
4. 4)
  - 6. Lu, W., Vaswani, N.: ‘Modified BPDN for noisy compressive sensing with partially known support’. Proc. IEEE Int. Conf. Acoustics, Speech, Signal Processing (ICASSP), 2010, pp. 3926–3929.
5. 5)
  - 7. Lu, W., Vaswani, N.: ‘Exact reconstruction conditions for regularized modified basis pursuit’, IEEE Trans. Signal Process., 2012, 60, (5), pp. 2634–2640 (doi: 10.1109/TSP.2012.2186445).
6. 6)
  - 20. Tseng, P.: ‘Further results on a stable recovery of sparse overcomplete representations in the presence of noise’, IEEE Trans. Inf. Theory, 2009, 55, (2), pp. 888–899 (doi: 10.1109/TIT.2008.2009812).
7. 7)
  - 12. 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).
8. 8)
  - 19. Cai, T.T., Xu, G., Zhang, J.: ‘On recovery of sparse signals via l1 minimization’, IEEE Trans. Inf. Theory, 2009, 55, (7), pp. 3388–3397 (doi: 10.1109/TIT.2009.2021377).
9. 9)
  - Z. Ben-Haim , Y.C. Eldar , M. Elad . Coherence-based performance guarantees for estimating a sparse vector under random noise. IEEE Trans. Signal Process. , 10 , 5030 - 5043
10. 10)
  - 15. Afonso, M., Bioucas-Dias, J., Figueiredo, M.: ‘Fast image recovery using variable splitting and constrained optimization’, IEEE Trans. Image Process., 2010, 19, (9), pp. 2345–2356 (doi: 10.1109/TIP.2010.2047910).
11. 11)
  - 24. Strohmer, T., Heath, R.W.Jr: ‘Grassmannian frames with applications to coding and communication’, Appl. Comput. Harmon. Anal., 2003, 14, (3), pp. 257–275 (doi: 10.1016/S1063-5203(03)00023-X).
12. 12)
  - 18. Cai, T.T., Wang, L., Xu, G.: ‘Stable recovery of sparse signals and an oracle inequality’, IEEE Trans. Inf. Theory, 56, (7), pp. 3516–3522 (doi: 10.1109/TIT.2010.2048506).
13. 13)
  - D. Donoho . Compressed sensing. IEEE Trans. Inf. Theory , 2 , 1289 - 1306
14. 14)
  - 5. Vaswani, N., Lu, W.: ‘Modified-CS: modifying compressive sensing for problems with partially known support’. Proc. IEEE Int. Symp. Information Theory (ISIT), 2009, pp. 488–492.
15. 15)
  - 17. Wang, Y., Yin, W.: ‘Sparse signal reconstruction via iterative support detection’, SIAM J. Imaging Sci., 2010, 3, (3), pp. 462–491 (doi: 10.1137/090772447).
16. 16)
  - 23. YUV video sequences. Available at http://trace.eas.asu.edu/yuv/.
17. 17)
  - 14. Gabay, D., Mercier, B.: ‘A dual algorithm for the solution of nonlinear variational problems via finite element approximations’, Comput. Math. Appl., 1976, 2, pp. 17–40 (doi: 10.1016/0898-1221(76)90003-1).
18. 18)
  - 13. Boyd, S., Parikh, N., Chu, E., Peleato, B.: ‘Distributed optimization and statistical learning via the alternating direction method of multipliers’, Found. Trends Mach. Learn., 2011, 3, (1), pp. 1–122 (doi: 10.1561/2200000016).
19. 19)
  - 21. Elad, M.: ‘Sparse and redundant representation: from theory to applications in signal and image processing’ (Springer Press, 2010), pp. 79–109.
20. 20)
  - 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).
21. 21)
  - E. Candès , J. Romberg , T. Tao . Near-optimal signal recovery from random projections: universal encoding strategies?. IEEE Trans. Inf. Theory , 2 , 489 - 509
22. 22)
  - 13. Glowinski, R., Marrocco, A.: ‘Sur l'approximation, par elements finisd'ordre un, et la resolution, par penalisation-dualité d'une classe de problems de dirichlet non lineares’, Rev. Fr. Autom. Inform. Rech. Opér., 1975, 9, pp. 41–76.
23. 23)
  - 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).
24. 24)
  - 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).

Compressed sensing with partial support information: coherence-based performance guarantees and alternative direction method of multiplier reconstruction algorithm

References

Related content