Compressed sensing is a novel theory for signal sampling, which breaks through Nyquist/Shannon sampling limitation and makes it into reality that one can efficiently collect and robustly reconstruct a sparse signal. However, some signals exhibit additional structures in some redundant dictionaries, which is called block-sparse signal. In this study, non-convex block-sparse compressed sensing with redundant dictionaries is investigated. Under the block D-RIP condition $( 2 / 2 ) ≤ δ 2 k | τ < 1$ , a sufficient condition for robust signal reconstruction with redundant dictionaries by mixed $ℓ 2 / ℓ p ( 0 < p < 1 )$ minimisation is established. Furthermore, the authors’ theoretical results show that, under the assumption that $( 2 / 2 ) ≤ δ 2 k | τ < 1$ , $p ∈ ( 0 , p ^ ]$ , where $p ^ = 1.6835 ( 1 − δ 2 k | τ ) , δ 2 k | τ ∈ [ 2 2 , 0.73 ) 0.45418 , δ 2 k | τ ∈ ( 0.73 , 0.7983 ) 2.2522 ( 1 − δ 2 k | τ ) , δ 2 k | τ ∈ [ 0.7983 , 1 ) ,$ then the block k-sparse signal can be stably reconstructed via non-convex ℓ₂/ℓ_p minimisation with redundant dictionaries in the presence of noise. Particularly, this improves the existed result when the block-sparse signal degenerate to the conventional signal case. Besides, the authors also obtain robust reconstruction condition and error upper bound estimation when the block number is no more than four times the sparsity of the block signal $( d ≤ 4 k )$ . Moreover, the numerical experiments to some extent testify the performance of non-convex $ℓ 2 / ℓ p ( 0 < p < 1 )$ minimisation with redundant dictionaries.

References

1. 1)
  - 5. Baraniuk, R.G.: ‘Single-pixel imaging via compressive sampling’, IEEE Signal Process. Mag., 2008, 25, (2), pp. 83–91.
2. 2)
  - 8. Chen, S.B., Donoho, D.L., Saunders, M.A.: ‘Atomic decomposition by basis pursuit’, SIAM J. Sci. Comput., 1998, 20, (1), pp. 33–61.
3. 3)
  - 24. Wu, R., Chen, D.R.: ‘The improved bounds of restricted isometry constant for recovery via ℓp at-minimization’, IEEE Trans. Inf. Theory, 2013, 59, (9), pp. 6142–6147.
4. 4)
  - 12. Lin, J.H., Li, S., Shen, Y.: ‘New bounds for restricted isometry constants with coherent tight frames’, IEEE Trans. Signal Process., 2013, 61, (3), pp. 611–621.
5. 5)
  - 3. Donoho, D.L.: ‘Compressed sensing’, IEEE Trans. Inf. Theory, 2006, 52, (4), pp. 1289–1306.
6. 6)
  - 29. Ghalehjegh, S.H., Babaie-Zadeh, M., Jutten, C.: ‘Fast block-sparse decomposition based on SL0’, Lect. Notes Comput. Sci., 2010, 6365, pp. 426–433.
7. 7)
  - 15. Li, S., Lin, J.H.: ‘Compressed sensing with coherent tight frames via ℓq minimization for 0 < q ≤ 1’, Inverse Probl. Imaging, 2014, 8, (3), pp. 761–777.
8. 8)
  - 23. Sun, Q.: ‘Recovery of sparsest signals via ℓq at-minimization’, Appl. Comput. Harmon. Anal., 2012, 32, (3), pp. 329–341.
9. 9)
  - 10. Bruckstein, A.M., Donoho, D.L., Elad, M.: ‘From sparse solutions of systems of equations to sparse modeling of signals and images’, SIAM Rev., 2009, 51, (1), pp. 34–81.
10. 10)
  - 28. Eldar, Y.C., Kuppinger, P., Bölcskei, H.: ‘Block-sparse signals: uncertainty relations and efficient recovery’, IEEE Trans. Signal Process., 2010, 58, (6), pp. 3042–3054.
11. 11)
  - 26. Zelni-Manor, L., Rosenblum, K., Eldar, Y.C.: ‘Sensing matrix optimization for block-sparse decoding’, IEEE Trans. Signal Process., 2011, 59, (9), pp. 4300–4312.
12. 12)
  - 17. Cotter, S., Rao, B.: ‘Sparse channel estimation via matching pursuit with application to equalization’, IEEE Trans. Commun., 2002, 50, (3), pp. 374–377.
13. 13)
  - 27. Abolghasemi, V., Ferdowsi, S., Sanei, S.: ‘A gradient-based alternating minimization approach for optimization of the measurement matrix in compressive sensing’, Signal Process., 2012, 92, (4), pp. 999–1009.
14. 14)
  - 19. Wang, Y., Wang, J.J., Xu, Z.B.: ‘A note on block-sparse signal recovery with coherent tight frames’, Discret. Dyn. Nat. Soc., 2013, 2013, (1), pp. 1–6.
15. 15)
  - 1. Nyquist, H.: ‘Certain topics in telegraph transmission theory’, Am. Inst. Electr. Eng., 1928, 47, (2), pp. 617–644.
16. 16)
  - 11. Candès, E.J., Eldas, Y.C., Needell, D., et al: ‘Compressed sensing with coherent and redundant dictionaries’, Appl. Comput. Harmon. Anal., 2011, 31, (1), pp. 59–73.
17. 17)
  - 4. Candès, E.J.: ‘Compressive sampling’, Marta Sanz Sol., 2006, 17, (2), pp. 1433–1452.
18. 18)
  - 13. Lin, J.H., Li, S., Shen, Y.: ‘Compressed data separation with redundant dictionaries’, IEEE Trans. Inf. Theory, 2013, 59, (7), pp. 4309–4315.
19. 19)
  - 25. Wen, J., Li, D., Zhu, F.: ‘Stable recovery of sparse signals via ℓp minimization’, Appl. Comput. Harmon. Anal., 2014, 38, (7), pp. 161–176.
20. 20)
  - 18. Vidal, R., Ma, Y.: ‘A unified algebraic approach to 2-D and 3-D motion segmentation and estimation’, J. Math. Imaging Vis., 2006, 25, (3), pp. 403–421.
21. 21)
  - 9. Jiao, Y., Jin, B., Lu, X.: ‘A primal dual active set with continuation algorithm for the ℓ0 at-regularized optimization problem’, Appl. Comput. Harmonic Anal., 2014, 39, (3), pp. 400–426.
22. 22)
  - 30. Deng, W., Yin, W., Zhang, Y.: ‘Group sparse optimization by alternating direction method’, Proc. SPIE-The Int. Soc. Opt. Eng., 2013, 8858, pp. 88580R–88580R-15.
23. 23)
  - 22. Xu, Z.B., Guo, H.L., Wang, Y., et al: ‘Representative of L1/2 regularization among ℓq(0<q≤1) regularizations: an experimental study based on phase diagram’, Acta Autom. Sin., 2012, 38, (7), pp. 1225–1228.
24. 24)
  - 20. Chartrand, R.: ‘Exact reconstruction of sparse signals via nonconvex minimization’, Signal Process. Lett., 2007, 14, (10), pp. 707–710.
25. 25)
  - 14. Candès, E., Tao, T.: ‘Decoding by linear programming’, IEEE Trans. Inf. Theory, 2005, 51, (12), pp. 4203–4215.
26. 26)
  - 7. Lustig, M., Donoho, D.L., Pauly, D.L.: ‘Sparse MRI: the application of compressed sensing for rapid MR imaging’, Magn. Reson. Med., 2007, 58, (6), pp. 1182–1195.
27. 27)
  - 2. Candès, E., Romberg, J., Tao, T.: ‘Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information’, IEEE Trans. Inf. Theory, 2006, 52, (2), pp. 489–509.
28. 28)
  - 16. Parvaresh, F., Vikalo, H., Misra, H., et al: ‘Recovering sparse signals using sparse measurement matrices in compressed DNA microarrays’, IEEE J. Sel. Top. Signal Process., 2008, 2, (3), pp. 275–285.
29. 29)
  - 6. Lei, J., Liu, S.: ‘Inversion algorithm based on the generalized objective functional for compressed sensing’, Appl. Math. Model., 2013, 37, (6), pp. 4407–4429.
30. 30)
  - 21. Chartrand, R., Staneva, V.: ‘Restricted isometry properties and nonconvex compressive sensing’, Inverse Probl., 2008, 24, (3), pp. 20–35.

Non-convex block-sparse compressed sensing with redundant dictionaries

References

Related content