Sparse reconstruction via the mixture optimization model with iterative support estimate. (English) Zbl 1531.94014
Summary: This paper is devoted to the construction and analysis of a novel hybrid optimization model of the \(\ell_0\) minimization and the \(\ell_1\) minimization with a given support estimate. With the help of the Moreau envelop of the \(\ell_1\) norm, we provide reasonable explanation for the claim that the capped-\(\ell_1\) penalty is one of the continuous relaxation to the \(\ell_0\)-norm penalty and thus develop the scale iteratively reweighed \(\ell_1\)-minimization (SIRL1) aiming to achieve fast reconstruction and a reduced requirement on the number of measurements compared to the \(\ell_1\) minimization approach. To illustrate the theoretical results, some numerical experiments are presented to demonstrate the effectiveness and flexibility of the proposed SIRL1 algorithm.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 65K10 | Numerical optimization and variational techniques |
| 90C25 | Convex programming |
| 90C51 | Interior-point methods |
| 90C30 | Nonlinear programming |
Keywords:
sparse signal reconstruction; reweighted \(\ell_1\) minimization; \(\ell_0\) minimization; iterative support detectionReferences:
| [1] | Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imag. Sci., 2, 1, 183-202 (2009) · Zbl 1175.94009 |
| [2] | Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1058.90049 |
| [3] | Cohen, A.; Dahmen, W.; DeVore, R., Compressed sensing and best k-term approximation, J. Amer. Math. Soc., 22, 1, 211-231 (2009) · Zbl 1206.94008 |
| [4] | Chen, W.; Li, Y., Recovery of signals under the condition on RIC and ROC via prior support information, Appl. Comput. Harmon. Anal., 46, 2, 417-430 (2019) · Zbl 1405.94023 |
| [5] | E.J. Candès, J. Romberg, T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory 52 (2) (2006) 489-509. doi:10.1109/TIT.2005.862083. · Zbl 1231.94017 |
| [6] | E.J. Candès, T. Tao, Near optimal signal recovery from random projections: Universal encoding strategies?, IEEE Trans. Inf. Theory 52 (12) (2006) 5406-5425. doi:10.1109/TIT.2006.885507. · Zbl 1309.94033 |
| [7] | Candès, E. J.; Tao, T., Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 12, 4203-4215 (2005) · Zbl 1264.94121 |
| [8] | Candès, E. J.; Wakin, M. B., An introduction to compressive sampling, IEEE Signal Process. Mag., 25, 2, 21-30 (2008) |
| [9] | Candès, E. J.; Wakin, M. B.; Boyd, S. P., Enhancing sparsity by reweighted \(\ell_1\) minimization, J. Fourier Anal. Appl., 14, 5, 877-905 (2008) · Zbl 1176.94014 |
| [10] | Chartrand, R.; Yin, W., Iteratively reweighted algorithms for compressive sensing, (Proceedings of the 33rd IEEE International Conference on Acoustics, Speech and Signal Processing (2008)), 3869-3872 |
| [11] | Daubechies, I.; Devore, R.; Fornasier, M.; Güntürk, C. S., Iteratively reweighted least squares minimization for sparse recovery, Commun. Pure Appl. Math., 63, 1-38 (2010) · Zbl 1202.65046 |
| [12] | Devore, R.; Jawerth, B., Image compression through wavelet transform coding, IEEE Trans. Inf. Theory, 38, 719-746 (1992) · Zbl 0754.68118 |
| [13] | Donoho, D. L., Compressed sensing, IEEE Trans. Inf. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016 |
| [14] | Donoho, D. L.; Elad, M., Optimally sparse representation in general (nonorthogonal) dictionaries via \(\ell_1\) minimization, Proc. Natl. Acad. Sci., 100, 5, 2197-2202 (2003) · Zbl 1064.94011 |
| [15] | Foucart, S.; Lai, M., Sparsest solutions of underdetermined linear systems via \(\ell_p\)-minimization for \(0 < p 1\), Appl. Comput. Harmon. Anal., 26, 395-407 (2009) · Zbl 1171.90014 |
| [16] | Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing (2013), Springer-Verlag: Springer-Verlag New York, USA · Zbl 1315.94002 |
| [17] | Ge, H.; Chen, W., Recovery of signals by a weighted \(\ell_2/ \ell_1\) minimization under arbitrary prior support information, Signal Process., 148, 288-302 (2018) |
| [18] | Ong, C. S.; An, L. T., Learning sparse classifiers with difference of convex function algorithms, Optim. Method Softw., 28, 4, 830-854 (2013) · Zbl 1282.90181 |
| [19] | Peleg, D.; Meir, R., A bilinear formulation for vector sparsity optimization, Signal Process., 88, 2, 375-389 (2008) · Zbl 1186.94273 |
| [20] | Carrillo, R. E.; Barner, K. E., Lorentzian iterative hard thresholding: robust compressed sensing with prior information, IEEE Trans. Signal Process., 61, 19, 4822-4833 (2013) · Zbl 1393.94188 |
| [21] | Bian, W.; Chen, X., A smoothing proximal gradient algorithm for nonsmooth convex regression with cardinality penalty, SIAM J. Numer. Anal., 58, 1, 858-883 (2020) |
| [22] | Monsieur, H.; Saab, R., Recovery analysis for weighted \(\ell_1\)-minimization using the null space property, Appl. Comput. Harmon. Anal., 43, 1, 23-38 (2017) · Zbl 1384.94008 |
| [23] | Natarajan, B. K., Sparse approximate solutions to linear systems, SIAM J. Comput., 24, 2, 227-234 (1995) · Zbl 0827.68054 |
| [24] | Selesnick, I., Sparse regularization via convex analysis, IEEE Trans. Signal Process., 65, 17, 4481-4494 (2017) · Zbl 1414.94545 |
| [25] | Vaswani, N.; Lu, W., Modified-CS: Modifying compressive sensing for problems with partially known support, IEEE Trans. Signal Process., 58, 9, 4595-4607 (2010) · Zbl 1392.94045 |
| [26] | Wang, J.; Wang, X. T., Sparse approximate reconstruction decomposed by two optimization problems, Circ. Syst. Signal Process., 37, 5, 2164-2178 (2017) · Zbl 1426.94063 |
| [27] | Wang, J.; Wang, X. T., Sparse signal reconstruction via the approximations of \(\ell_0\) quasinorm, J. Ind. Manage. Optim., 16, 4, 1907-1925 (2020) · Zbl 1449.90327 |
| [28] | Wang, Y.; Yin, W., Sparse signal reconstruction via iterative support detection, SIAM J. Imag. Sci., 3, 3, 462-491 (2010) · Zbl 1206.68340 |
| [29] | Yu, J.; Tao, D.; Wang, M., Adaptive hypergraph learning and its application in image classification, IEEE Trans. Image Process., 21, 7, 3262-32722 (2012) · Zbl 1381.62216 |
| [30] | Yu, J.; Rui, Y.; Tao, D., Click prediction for web image reranking using multimodal sparse coding, IEEE Trans. Image Process., 23, 5, 2019-2032 (2014) · Zbl 1374.94435 |
| [31] | Zhao, Y.-B.; Li, D., Reweighted \(\ell_1\)-minimization for sparse solutions to underdetermined linear systems, SIAM J. Opt., 22, 3, 1065-1088 (2012) · Zbl 1261.65042 |
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.
