Paper:

# Block Sparse Signal Reconstruction Using Block-Sparse Adaptive Filtering Algorithms

## Chen Ye^{*}, Guan Gui^{**}, Shin-ya Matsushita^{*}, and Li Xu^{*}

^{*}Department of Electronics and Information Systems, Akita Prefectural University

84-4 Ebinokuchi, Tsuchiya Aza, Yurihonjo, Akita 015-0055, Japan

^{**}College of Telecommunication and Information Engineering, Nanjing University of Post and Telecommunications

No. 66, New Mofan Rd., Gulou District, Nanjing 210003, China

Sparse signal reconstruction (SSR) problems based on compressive sensing (CS) arise in a broad range of application fields. Among these are the so-called “block-structured” or “block sparse” signals with nonzero atoms occurring in clusters that occur frequently in natural signals. To make block-structured sparsity use more explicit, many block-structure-based SSR algorithms, such as convex optimization and greedy pursuit, have been developed. Convex optimization algorithms usually pose a heavy computational burden, while greedy pursuit algorithms are overly sensitive to ambient interferences, so these two types of block-structure-based SSR algorithms may not be suited for solving large-scale problems in strong interference scenarios. Sparse adaptive filtering algorithms have recently been shown to solve large-scale CS problems effectively for conventional vector sparse signals. Encouraged by these facts, we propose two novel block-structure-based sparse adaptive filtering algorithms, i.e., the “block zero attracting least mean square” (BZA-LMS) algorithm and the “block *ℓ*_{0}-norm LMS” (BL0-LMS) algorithm, to exploit their potential performance gain. Experimental results presented demonstrate the validity and applicability of these proposed algorithms.

- [1] E. J. Candes, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,” IEEE Trans. Inf. Theory, Vol.52, pp. 489-509, 2006.
- [2] D. L. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, Vol.52, pp. 1289-1306, 2006.
- [3] E. J. Candes, “Compressive sampling,” Proc. Int. Congr. Math, pp. 1433-1452, 2006.
- [4] Y. C. Eldar and P. Kuppinger, “Block-sparse signals: Uncertainty relations and efficient recovery,” IEEE Trans. Signal Process, Vol.58, pp. 3042-3054, 2010.
- [5] M. Mishali and Y. C. Eldar, “Blind multi-band signal reconstruction: Compressed sensing for analog signals,” IEEE Trans. Signal Process., Vol.57, pp. 993-1009, 2009.
- [6] M. Mishali and Y. C. Eldar, “From theory to practice: Sub-Nyquist sampling of sparse wideband analog signals,” IEEE J. Sel. Topics Signal Process., Vol.4, pp. 375-391, 2009.
- [7] H. J. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math., Vol.117, pp. 37-52, 1967.
- [8] M. Mishali, Y. C. Eldar, O. Dounaevsky, and E. Shoshan, “Xampling: Analog to digital at sub-Nyquist rates,” IET Circuits, Devices & Systems, Vol.5, pp. 8-20, 2011.
- [9] F. Parvaresh, H. Vikalo, S. Misra, and B. Hassibi, “Recovering sparse signals using sparse measurement matrices in compressed DNA microarrays,” IEEE J. Sel. Topics Signal Process., Vol.2, pp. 275-285, 2008.
- [10] B. M. Sanandaji, T. L. Vincent, and M. B. Wakin, “Exact topology identification of large-scale interconnected dynamical systems from compressive observations,” Proc. of the 2011 American Control Conf., pp. 649-656, 2011.
- [11] B. M. Sanandaji, T. L. Vincent, and M. B. Wakin, “Compressive topology identification of interconnected dynamic systems via clustered orthogonal matching pursuit,” Proc. of the 15th IEEE Conf. on Decision and Control and European Control Conf., pp. 174-180, 2011.
- [12] R. G. Baraniuk, V. Cevher, M. F. Duarte, and C. Hegde, “Model-based compressive sensing,” IEEE Trans. Inf. Theory, Vol.56, pp. 1982-2001, 2010.
- [13] L. Yu, H. Sun, J. Barbot, and G. Zheng, “Bayesian compressive sensing for cluster structured sparse signals,” Signal Process, Vol.92, pp. 259-269, 2012.
- [14] M. Stojnic, F. Parvaresh, and B. Hassibi, “On the reconstruction of block-sparse signals with an optimal number of measurements,” IEEE Trans. Signal Process., Vol.57, pp. 3075-3085, 2009.
- [15] J. A. Tropp and A. C. Gilbert, “Signal recovery from random measurements via orthogonal matching pursuit,” IEEE Trans. Inf. Theory, Vol.53, pp. 4655-4666, 2007.
- [16] D. L. Donoho, Y. Tsaig, I. Drori, and J. Starck, “Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit,” IEEE Trans. Inf. Theory, Vol.58, pp. 1094-1120, 2012.
- [17] B. X. Huang and T. Zhou, “Recovery of block sparse signals by a block version of StOMP,” Signal Processing, Vol.106, pp. 231-244, 2015.
- [18] J. Jin, Y. Gu, and S. Mei, “A stochastic gradient approach on compressive sensing signal reconstruction based on adaptive filtering framework,” IEEE J. Sel. Top. Signal Process., Vol.4, pp. 409-420, 2010.
- [19] B. Widrow and D. Stearns, “Adaptive Signal Processing,” New Jersey: Prentice Hall, 1985.
- [20] C. Turan and M. S. Salman, “Zero-attracting function controlled VSSLMS algorithm with analysis,” Circuits, Syst. Signal Process., Vol.34, pp. 3071-3080, 2015.
- [21] M. N. S. Jahromi, M. S. Salman, A. Hocanin, and O. Kukrer, “Convergence analysis of the zero-attracting variable step-size LMS algorithm for sparse system identification,” Signal, Image Video Process., Vol.9, pp. 1353-1356, 2015.
- [22] Y. Chen, Y. Gu, and A. O. Hero, “Sparse LMS for system identification,” Acoust. Speech Signal Process., pp. 3125-3128, 2009.
- [23] Y. Gu, J. Jin, and S. Mei, “l0-Norm Constraint LMS Algorithm for Sparse System Identification,” IEEE Signal Process. Lett., Vol.16, pp. 774-777, 2009.
- [24] J. Benesty and S. L. Gay, “An improved PNLMS algorithm,” 2002 IEEE Int. Conf. Acoust. Speech, Signal Process., Vol.2, pp. II-1881-II-1884, 2002.
- [25] R. K. Martin, W. A. Sethares, R. C. Williamson, and C. R. Johnson, “Exploiting sparsity in adaptive filters,” IEEE Trans. Signal Process., Vol.50, pp. 1883-1894, 2002.
- [26] G. Gui, H. Wei, N. Shimoi, and L. Xu, “Regularization parameter selection method for sign LMS with reweighted L1-norm constriant algorithm,” 2015.
- [27] C. Ye, G. Gui, S. Matsushita, and L. Xu, “Robust stochastic gradient-based adaptive filtering algorithms to realize compressive sensing against impulsive interferences,” China Control and Design Conf., 2016.
- [28] J. Weston, A. Elisseeff, B. Scholkopf, and M. E. Tipping, “Use of the zero-norm with linear models and kernel methods,” J. of Machine Learning Research, Vol.3, pp. 1439-1461, 2002.