×

Effective zero-norm minimization algorithms for noisy compressed sensing. (English) Zbl 1455.94055

Summary: This paper proposes two new algorithms, namely (i) SSReL1Min(CVX)-scalar-sign function-based reweighted \(l_1\)-norm minimization algorithm combined with disciplined convex programming for a high-performance \(L_0\)-norm minimization algorithm and (ii) SSReL1Min(MBB) – SSReL1Min algorithm combined with modified Barzilai-Borwein algorithm for a computational fast \(L_0\)-norm minimization algorithm (without significantly sacrificing the performance). Based on the proposed \(L_0\)-norm minimization algorithm, this paper also presents an upgraded compressed sensing to improve its performance on the recovery of noisy signals. The proposed \(L_0\)-norm minimization algorithm includes a new optimal scalar-sign function-based weighting (in the least squares sense), as well as a new and systematic mapping mechanism in pre- and post-processing, for noisy compressed sensing. This improvement is further confirmed by experimental results. Comparisons with different state-of-the-art solvers are also included, to show that the proposed method outperforms existing ones.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
65K10 Numerical optimization and variational techniques

Software:

PDCO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Candès, E. J.; Romberg, J.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Communications on Pure and Applied Mathematics, 59, 1207-1223 (2006) · Zbl 1098.94009
[2] Donoho, D. L., Compressed sensing, IEEE Transactions on Information Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016
[3] Graff, C. G.; Sidky, E. Y., Compressive sensing in medical imaging, Applied Optics, 54, 8, 23-44 (2015)
[4] Lustig, M.; Donoho, D.; Pauly, J. M.; Sparse, MRI, The application of compressed sensing for rapid MR imaging, Magnetic Resonance in Medicine, 58, 6, 1182-1195 (2007)
[5] Meng, J.; Yin, W.; Li, H.; Hossain, E.; Han, Z., Collaborative spectrum sensing from sparse observations in cognitive radio networks, IEEE Journal on Selected Areas in Communications, 29, 2, 327-337 (2011)
[6] Li, S.; Xu, L. D.; Wang, X., Compressed sensing signal and data acquisition in wireless sensor networks and internet of things, IEEE Transactions on Industrial Informatics, 9, 4, 2177-2186 (2013)
[7] Abdi, M. J., Cardinality Optimization Problems (May 2013), University of Birmingham, Ph. D. Dissertation
[8] Hong, X.; Chen, S.; Harris, C. J., Using zero-norm constraint for sparse probability density function estimation, International Journal of Systems Science, 43, 11, 2107-2113 (2012) · Zbl 1305.93193
[9] E.J. Candès, M.B. Wakin, S.P. Boyd, Enhancing sparsity by reweighted l_1 minimization, Journal of Fourier Analysis and Applications. 14 (5) (2008) 877-905. · Zbl 1176.94014
[10] Wipf, D.; Nagarajan, S., Iterative reweighted ℓ_1 and ℓ_2 methods for finding sparse solutions, IEEE Journal of Selected Topics in Signal Processing, 4, 2, 317-329 (2010)
[11] Zhao, Y.; Li, D., Reweighted-minimization for sparse solutions to underdetermined linear systems, SIAM Journal on Optimization, 22, 3, 1065-1088 (2012) · Zbl 1261.65042
[12] Ambat, S. K.; Hari, K. V.S., An iterative framework for sparse signal reconstruction algorithms, Signal Processing, 108, 351-364 (2015)
[13] Asif, M. S.; Romberg, J., Fast and accurate algorithms for re-weighted l_1-norm minimization, IEEE Transactions on Signal Processing, 61, 23, 5905-5916 (2013) · Zbl 1394.94052
[14] Daubechies, I.; DeVore, R.; Fornasier, M.; Güntürk, C. S., Iteratively reweighted least squares minimization for sparse recovery, Communications on Pure and Applied Mathematics, 63, 1, 1-38 (2010) · Zbl 1202.65046
[15] Mallat, S., A Wavelet Tour of Signal Processing (September 1999), Academic Press: Academic Press New York · Zbl 0998.94510
[16] Engan, K.; Aase, S. O.; Husoy, J. H., Method of optimal directions for frame design, IEEE International Conference on Acoustics, Speech, and Signal Processing (March 1999)
[17] Aharon, M.; Elad, M.; Bruckstein, A., K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation, IEEE Transactions on Signal Processing, 54, 11, 4311-4322 (2006) · Zbl 1375.94040
[18] Castro, E. A.; Eldar, Y. C., Noise folding in compressed sensing, IEEE Signal Processing Letters, 18, 8, 478-481 (2011)
[19] Candes, E. J.; Tao, T., Decoding by linear programming, IEEE Transactions on Information Theory, 51, 12, 4203-4215 (2005) · Zbl 1264.94121
[20] Natarajan, B. K., Sparse approximate solutions to linear systems, SIAM Journal on Computing, 24, 2, 227-234 (1995) · Zbl 0827.68054
[21] Mallat, S. G.; Zhang, Z., Matching pursuits with time-frequency dictionaries, IEEE Transactions on Signal Processing, 41, 12, 3397-3415 (1993) · Zbl 0842.94004
[22] Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, Society for Industrial and Applied Mathematics, 43, 1, 129-159 (2001) · Zbl 0979.94010
[23] Saab, R.; Chartrand, R.; Yilmaz, O., Stable sparse approximations via nonconvex optimization, IEEE International Conference on Acoustics, Speech and Signal Processing, 3885-3888 (2008)
[24] Chen, X.; Xu, F.; Ye, Y., Lower bound theory of nonzero entries in solutions of l_2-l_p minimization, SIAM Journal on Scientific Computing, 32, 5, 2832-2852 (2010) · Zbl 1242.90174
[25] Chen, X.; Zhou, W., Convergence of reweighted l_1 minimization algorithms and unique solution of truncated l_p minimization, Technical Report, HK Polytech, University (2010)
[26] Shieh, L. S.; Tsai, Y. T.; Yates, R. E., Some properties of matrix sign functions derived from continued fractions, IEE Proc. Part. D, 130, 3, 111-118 (1983) · Zbl 0518.93018
[27] Wu, J.; Shieh, L. S.; Tsai, J. S.H.; Zhang, Y., An approximated scalar sign function approach to optimal anti-windup digital controller design for continuous-time digital controller design for continuous-time nonlinear systems with input constraints, International Journal of Systems Science, 41, 6, 657-671 (2010) · Zbl 1193.93135
[28] Peter, S.; Artina, M.; Fornasier, M., Damping noise-folding and enhanced support recovery in compressed sensing, IEEE Transactions on Signal Processing, 63, 22, 5990-6002 (2015) · Zbl 1394.94457
[29] Wright, S. J.; Nowak, R. D.; Figueiredo, M. A.T., Sparse reconstruction by separable approximation, IEEE Transactions on Signal Processing, 57, 7, 3373-3376 (2009)
[30] Zheng, Y.; Zheng, B., A New modified Barzilai-Borwein gradient method for the quadratic minimization problem, Journal of Optimization Theory and Applications, 172, 1, 179-186 (2017) · Zbl 1358.65039
[31] Wright, S. J., Primal-Dual Interior Point Methods, Society for Industrial and Applied Mathematics (SIAM) (1997), Philadelaphia, PA · Zbl 0863.65031
[32] Barzilai, J.; Borwein, J., Two-point step size gradient methods, IMA Journal of Numerical Analysis, 8, 141-148 (1988) · Zbl 0638.65055
[33] J. Meng, H. Li, Z. Han, Sparse event detection in wireless sensor networks using compressive sensing, CISS 2009. 43rd Annual Conference on Information Sciences and Systems, 2009.
[34] Mohimani, H.; Babaie-Zadeh, M.; Jutten, C., A fast approach for overcomplete sparse decomposition based on smoothed ℓ^0 norm, IEEE Transactions on Signal Processing, 57, 1, 289-301 (2009) · Zbl 1391.94325
[35] Zaki, A.; Chatterjee, S.; Rasmussen, L. K., Generalized fusion algorithm for compressive sampling reconstruction and RIP based analysis, Signal Processing, 139, 36-48 (2017)
[36] Guan, W.; Fan, H.; Xu, L.; Wang, Y., An adaptive gradient greedy algorithm for compressed sensing, DDCLS 2017, 6^th Data Driven Control and Learning Systems, 760-763 (2017)
[37] Y. Wang, W. Yin, Sparse signal reconstruction via iterative support detection, SIAM Journal on Imaging Sciences. 3(3) (2010) 462-491. · Zbl 1206.68340
[38] Hong, X.; Chen, S.; Guo, Y.; Gao, J., l_1-norm penalized orthogonal forward regression, International Journal of Systems Science., 48, 10, 2195-2201 (2017) · Zbl 1373.62343
[39] Donoho, D. L.; Elad, M.; Temlyakov, V. N., Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Transactions on Information Theory, 52, 1, 6-18 (2006) · Zbl 1288.94017
[40] Cohen, A.; Dahmen, W.; DeVore, R., Compressed sensing and best k-term approximation, Journal of the American Mathematical Society, 22, 1, 211-231 (2008) · Zbl 1206.94008
[41] Tillmann, A. M.; Pfetsch, M. E., The computational complexity of the restricted isometry property, the null space property, and related concepts in compressed sensing, IEEE Transactions on Information Theory, 60, 2, 1248-1259 (2014) · Zbl 1364.94170
[42] Natarajan, A.; Wu, Y., Computational complexity of certifying restricted isometry property, Approximation Randomization and Combinatorial Optimization Algorithms and Techniques (2014) · Zbl 1359.68141
[43] Baraniuk, R.; Davenport, M.; DeVore, R.; Wakin, M., A simple proof of the restricted isometry property for random matrices, Constructive Approximation, 28, 3, 253-263 (2008) · Zbl 1177.15015
[44] Chiani, M.; Elzanaty, A.; Giorgetti, A., Analysis of the restricted isometry property for Gaussian random matrices, IEEE Global Communications Conference (GLOBECOM) (2015)
[45] Candès, E. J., The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathematique, 346, 9-10, 589-592 (2008) · Zbl 1153.94002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.