HOU Jingyao, WANG Jianjun, ZHANG Feng, HUANG Jianwen. Robust Reconstruction of Block Sparse Signals from Adaptively One-Bit Measurements[J]. Chinese Journal of Electronics, 2020, 29(5): 937-944. doi: 10.1049/cje.2020.08.009
 Citation: HOU Jingyao, WANG Jianjun, ZHANG Feng, HUANG Jianwen. Robust Reconstruction of Block Sparse Signals from Adaptively One-Bit Measurements[J]. Chinese Journal of Electronics, 2020, 29(5): 937-944.

# Robust Reconstruction of Block Sparse Signals from Adaptively One-Bit Measurements

##### doi: 10.1049/cje.2020.08.009
Funds:  This work is supported by the National Natural Science Foundation of China (No.61673015, No.61273020), and the Fundamental Research Funds for the Central Universities (No.XDJK2018C076, No.SWU1809002).
• Corresponding author: WANG Jianjun (corresponding author) received the B.S. degree in mathematical education from Ningxia University, Yinchuan, China, in 2000, the M.S. degree in fundamental mathematics from Ningxia University, China, in 2003, and the Ph.D. degree in applied mathematics from the Institute for Information and System Science, Xi'an Jiaotong University, Xi'an, China, in December 2006. He is currently a professor in the College of Artificial Intelligence at Southwest University of China. His research focuses on machine learning, data mining, neural networks, and sparse learning. (Email:wjj@swu.edu.cn)
• Rev Recd Date: 2020-07-09
• Publish Date: 2020-09-10
• Though various theoretical results and algorithms have been proposed in one-bit Compressed sensing (1-bit CS), there are few studies on more structured signals, such as block sparse signals. We address the problem of recovering block sparse signals from one-bit measurements. We first propose two recovery schemes, one based on second-order cone programming and the other based on hard thresholding, for common non-adaptively thresholded one-bit measurements. Note that the worst-case error in recovering sparse signals from non-adaptively thresholded one-bit measurements is bounded below by a polynomial of oversampling factor. To break the limit, we introduce a recursive strategy that allows the thresholds in quantization to be adaptive to previous measurements at each iteration. Using the scheme, we propose two iterative algorithms and show that corresponding recovery errors are both exponential functions of the oversampling factor. Several simulations are conducted to reveal the superiority of our methods to existing approaches.
•  P.T. Boufounos and R.G. Baraniuk, "1-bit compressive sensing", Proc. of the 42nd Annual Conference on Information Sciences and Systems, Princeton, New Jersey, USA, pp.16-21, 2008. C.Y. Liu, J.J. Wang, W.D. Wang, et al., "A perturbation analysis on compressed data separation with nonconvex minimization method", Acta Electronica Sinica, Vol.45, No.1 pp.37-45, 2017. (in Chinese) Y.Y. Li, F. Dai, X.F. Cheng, et al., "Multiple-prespecifieddictionary sparse representation for compressive sensing image reconstruction with nonconvex regularization", Journal of the Franklin Institute, Vol.356, No.4, pp.2353-2371, 2019. B.P. Wang, Y. Zhang, Y. Fang, et al., "Parametric narrowband InISAR 3D imaging based on compressed sensing", Chinese Journal of Electronics, Vol.29, No.3, pp.508-514, 2020. D.G. Dong, G.S. Rui, W.B. Tian, et al., "A robust dynamic compressive sensing algorithm for streaming signals in time domain based on sparse Bayesian learning", Acta Electronica Sinica, Vol.48, No.5, pp.990-996, 2020. (in Chinese) P.T. Boufounos, "Reconstruction of sparse signals from distorted randomized measurements", Proc. of IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), Dallas, Texas, USA, pp.3998-4001, 2010. L. Jacques, J.N. Laska, P.T. Boufounos, et al., "Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors", IEEE Transactions on Information Theory, Vol.59, No.4, pp.2082-2102, 2013. Y. Plan and R. Vershynin, "One-bit compressed sensing by linear programming", Communications on Pure and Applied Mathematics, Vol.66, No.8, pp.1275-1297, 2013. Y. Plan and R. Vershynin, "Robust 1-bit compressed sensing and sparse logistic regression:A convex programming approach", IEEE Transactions on Information Theory, Vol.59, No.1, pp.482-494, 2013. X. Huang and M. Yan, "Nonconvex penalties with analytical solutions for one-bit compressive sensing", Signal Processing, Vol.144, pp.341-351, 2018. K. Knudson, R. Saab and R. Ward, "One-bit compressive sensing with norm estimation", IEEE Transactions on Information Theory, Vol.62, No.5, pp.2748-2758, 2016. R. Baraniuk, S. Foucart, D. Needell, et al., "Exponential decay of reconstruction error from binary measurements of sparse signals", IEEE Transactions on Information Theory, Vol.63, No.6, pp.3368-3385, 2017. R. Baraniuk, S. Foucart, D. Needell, et al., "One-bit compressive sensing of dictionary-sparse signals", Information and Inference:A Journal of the IMA, Vol.7, No.1, pp.83-104, 2017. F. Parvaresh, H. Vikalo, S. Misra, et al., "Recovering sparse signals using sparse measurement matrices in compressed DNA microarrays", IEEE Journal of Selected Topics in Signal Processing, Vol.2, No.3, pp.275-285, 2008. R. Tibshirani, M. Saunders, S. Rosset, et al., "Sparsity and smoothness via the fused lasso", Journal of the Royal Statistical Society:Series B (Statistical Methodology), Vol.61, No.1, pp.91-108, 2005. R. Vidal and Y. Ma, "A unified algebraic approach to 2-D and 3-D motion segmentation and estimation", Journal of Mathematical Imaging and Vision, Vol.25, No.3, pp.403-421, 2006. Y.C. Eldar and M. Mishali, "Robust recovery of signals from a structured union of subspaces", IEEE Transactions on Information Theory, Vol.55, No.11, pp.5302-5316, 2009. Y. Wang, J.J. Wang and Z.B. Xu, "Restricted p-isometry properties of nonconvex block-sparse compressed sensing", Signal Processing, Vol.104, pp.188-196, 2014. J.J. Wang, J.W. Huang, F. Zhang, et al., "Group sparse recovery in impulsive noise via alternating direction method of multipliers", Applied and Computational Harmonic Analysis, Vol.49, No.3, pp.831-862, 2020 J.M. Wen, Z.C. Zhou, Z.L. Liu, et al., "Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit", Applied and Computational Harmonic Analysis, Vol.47, No.3, pp.948-974, 2019. J.H. Lin and S. Li, "Block sparse recovery via mixed ℓ2/ℓ1 minimization", Acta Mathematica Sinica, English Series, Vol.29, No.7, pp.1401-1412, 2013. Y.C. Eldar, P. Kuppinger and H. Bolcskei, "Block-sparse signals:Uncertainty relations and efficient recovery", IEEE Transactions on Signal Processing, Vol.58, No.6, pp.3042-3054, 2010. R. Calderbank, A. Thompson and Y. Xie, "On block coherence of frames", Applied and Computational Harmonic Analysis, Vol.38, No.1, pp.50-71, 2015. B. Zhang, Y.L. Liu, X.J. Jing, et al., "Interweaving permutation meets block compressed sensing", Chinese Journal of Electronics, Vol.27, No.5, pp.1056-1062, 2018. Y. Chen, G. Gui, L. Xu, et al., "Recovery of block-structured sparse signal using block-sparse adaptive algorithms via dynamic grouping", IEEE Access, Vol.6, No.1, pp.56069-56083, 2018. R.X. Zeng and M.A.T. Figueiredo, "Binary fused compressive sensing:1-bit compressive sensing meets group sparsity", ArXiv preprint ArXiv:1402.5074, 2014. R.X. Zeng and M.A.T. Figueiredo, "Robust binary fused compressive sensing using adaptive outlier pursuit", Proc. of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Firenze, Tuscany, Italy, pp.7674-7678, 2014. N. Koep and R. Mathar, "Block-sparse signal recovery from binary measurements", Proc. of IEEE Statistical Signal Processing Workshop, Freiburg, Baden-Wurttemberg, Germany, pp.293-297, 2018.

### Catalog

###### 通讯作者: 陈斌, bchen63@163.com
• 1.

沈阳化工大学材料科学与工程学院 沈阳 110142