# American Institute of Mathematical Sciences

• Previous Article
Deteriorating inventory with preservation technology under price- and stock-sensitive demand
• JIMO Home
• This Issue
• Next Article
Analytical modeling of laminated composite plates using Kirchhoff circuit and wave digital filters
doi: 10.3934/jimo.2019035

## Sparse signal reconstruction via the approximations of $\ell_{0}$ quasinorm

 Department of Mathematics, Harbin Institute of Technology, Harbin 150001, Heilongjiang, China

* Corresponding author: Xing Tao Wang

Received  June 2018 Revised  November 2018 Published  May 2019

In this paper, we propose two classes of the approximations to the cardinality function via the Moreau envelope of the $\ell_{1}$ norm. We show that these two approximations are good choices of the merit function for sparsity and are essentially the truncated $\ell_{1}$ norm and the truncated $\ell_{2}$ norm. Moreover, we apply the approximations to solve sparse signal recovery problems and then provide new weights for reweighted $\ell_{1}$ minimization and reweighted least squares to find sparse solutions of underdetermined linear systems of equations. Finally, we present some numerical experiments to illustrate our results.

Citation: Jun Wang, Xing Tao Wang. Sparse signal reconstruction via the approximations of $\ell_{0}$ quasinorm. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2019035
 [1] Q. Berthet and P. Rigollet, Optimal detection of sparse principal components in high dimension, Annal. Statistics, 41 (2013), 1780-1815. doi: 10.1214/13-AOS1127. Google Scholar [2] Md. Z. A. Bhot, M. O. Ahmad and M. N. S. Swamy, An improved fast iterative shrinkage thresholding algorithm for image deblurring, SIAM J. Imaging Sci., 8 (2015), 1640-1657. doi: 10.1137/140970537. Google Scholar [3] A. M. Bruckstein, D. L. Donoho and M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Review, 51 (2009), 34-81. doi: 10.1137/060657704. Google Scholar [4] E.J. Candès and B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009), 717-772. doi: 10.1007/s10208-009-9045-5. Google Scholar [5] E. J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52 (2006), 489-509. doi: 10.1109/TIT.2005.862083. Google Scholar [6] E. J. Candés, J. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59 (2006), 1207-1223. doi: 10.1002/cpa.20124. Google Scholar [7] E. J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inf. Theory, 51 (2005), 4203-4215. doi: 10.1109/TIT.2005.858979. Google Scholar [8] E. J. Candès and T. Tao, Near-optimal signal recovery from random projections: Universal encoding strategies?, IEEE Trans. Inf. Theory, 52 (2006), 5406-5425. doi: 10.1109/TIT.2006.885507. Google Scholar [9] E. J. Candès, M. Wakin and S. Boyd, Enhancing sparsity by reweighted $\ell_{1}$ minimization, J. Fourier Anal. Appl., 14 (2008), 877-905. doi: 10.1007/s00041-008-9045-x. Google Scholar [10] R. Chartrand, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14 (2007), 707-710. doi: 10.1109/LSP.2007.898300. Google Scholar [11] R. Chartrand and W. Yin, Iteratively reweighted algorithms for compressive sensing, in: Proc. Int. Conf. Accoust. Speech, Signal Process., 2008, 3869–3872. doi: 10.1109/ICASSP.2008.4518498. Google Scholar [12] S. S. Chen, D. L. Donoho and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 43 (2001), 129-159. doi: 10.1137/S003614450037906X. Google Scholar [13] A. M. Christopher, M. Arian and G. B. Richard, From denoising to compressed sensing, IEEE Trans. Inf. Theory, 62 (2016), 5117-5144. doi: 10.1109/TIT.2016.2556683. Google Scholar [14] A. Cohen, W. Dahmen and R. DeVore, Compressed sensing and best k-term approximation, J. American Math. Soc., 22 (2009), 211-231. doi: 10.1090/S0894-0347-08-00610-3. Google Scholar [15] I. Daubechies, M. Defrise and M. C. De, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pur. Appl. Math., 57 (2004), 1413-1457. doi: 10.1002/cpa.20042. Google Scholar [16] D. L. Donoho, Compressed sensing, IEEE Trans. Inf. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582. Google Scholar [17] E. Esser, Y. F. Lou and J. Xin, A method for finding structured sparse solutions to nonnegative least squares problems with applications, SIAM J. maging Sci., 6 (2013), 2010-2046. doi: 10.1137/13090540X. Google Scholar [18] J. Fan and R. Li, Variable selection via nonconcave penalized likelihood and its oracle properties, J. Amer. Statist. Assoc., 96 (2001), 1348-1360. doi: 10.1198/016214501753382273. Google Scholar [19] M. Fornasier, S. Peter, H. Rauhut and S. Worm, Conjugate gradient acceleration of iteratively re-weighted least squares methods, Comput. Optim. Appl., 65 (2016), 205-259. doi: 10.1007/s10589-016-9839-8. Google Scholar [20] S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Birkhaäuser, Basel, 2013. doi: 10.1007/978-0-8176-4948-7. Google Scholar [21] S. Foucart and M. Lai, Sparsest solutions of underdetermined linear systems via $\ell_{q}$-minimization for $0 show all references ##### References:  [1] Q. Berthet and P. Rigollet, Optimal detection of sparse principal components in high dimension, Annal. Statistics, 41 (2013), 1780-1815. doi: 10.1214/13-AOS1127. Google Scholar [2] Md. Z. A. Bhot, M. O. Ahmad and M. N. S. Swamy, An improved fast iterative shrinkage thresholding algorithm for image deblurring, SIAM J. Imaging Sci., 8 (2015), 1640-1657. doi: 10.1137/140970537. Google Scholar [3] A. M. Bruckstein, D. L. Donoho and M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Review, 51 (2009), 34-81. doi: 10.1137/060657704. Google Scholar [4] E.J. Candès and B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009), 717-772. doi: 10.1007/s10208-009-9045-5. Google Scholar [5] E. J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52 (2006), 489-509. doi: 10.1109/TIT.2005.862083. Google Scholar [6] E. J. Candés, J. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59 (2006), 1207-1223. doi: 10.1002/cpa.20124. Google Scholar [7] E. J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inf. Theory, 51 (2005), 4203-4215. doi: 10.1109/TIT.2005.858979. Google Scholar [8] E. J. Candès and T. Tao, Near-optimal signal recovery from random projections: Universal encoding strategies?, IEEE Trans. Inf. Theory, 52 (2006), 5406-5425. doi: 10.1109/TIT.2006.885507. Google Scholar [9] E. J. Candès, M. Wakin and S. Boyd, Enhancing sparsity by reweighted$\ell_{1}$minimization, J. Fourier Anal. Appl., 14 (2008), 877-905. doi: 10.1007/s00041-008-9045-x. Google Scholar [10] R. Chartrand, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14 (2007), 707-710. doi: 10.1109/LSP.2007.898300. Google Scholar [11] R. Chartrand and W. Yin, Iteratively reweighted algorithms for compressive sensing, in: Proc. Int. Conf. Accoust. Speech, Signal Process., 2008, 3869–3872. doi: 10.1109/ICASSP.2008.4518498. Google Scholar [12] S. S. Chen, D. L. Donoho and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 43 (2001), 129-159. doi: 10.1137/S003614450037906X. Google Scholar [13] A. M. Christopher, M. Arian and G. B. Richard, From denoising to compressed sensing, IEEE Trans. Inf. Theory, 62 (2016), 5117-5144. doi: 10.1109/TIT.2016.2556683. Google Scholar [14] A. Cohen, W. Dahmen and R. DeVore, Compressed sensing and best k-term approximation, J. American Math. Soc., 22 (2009), 211-231. doi: 10.1090/S0894-0347-08-00610-3. Google Scholar [15] I. Daubechies, M. Defrise and M. C. De, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pur. Appl. Math., 57 (2004), 1413-1457. doi: 10.1002/cpa.20042. Google Scholar [16] D. L. Donoho, Compressed sensing, IEEE Trans. Inf. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582. Google Scholar [17] E. Esser, Y. F. Lou and J. Xin, A method for finding structured sparse solutions to nonnegative least squares problems with applications, SIAM J. maging Sci., 6 (2013), 2010-2046. doi: 10.1137/13090540X. Google Scholar [18] J. Fan and R. Li, Variable selection via nonconcave penalized likelihood and its oracle properties, J. Amer. Statist. Assoc., 96 (2001), 1348-1360. doi: 10.1198/016214501753382273. Google Scholar [19] M. Fornasier, S. Peter, H. Rauhut and S. Worm, Conjugate gradient acceleration of iteratively re-weighted least squares methods, Comput. Optim. Appl., 65 (2016), 205-259. doi: 10.1007/s10589-016-9839-8. Google Scholar [20] S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Birkhaäuser, Basel, 2013. doi: 10.1007/978-0-8176-4948-7. Google Scholar [21] S. Foucart and M. Lai, Sparsest solutions of underdetermined linear systems via$\ell_{q}$-minimization for$0
Comparison of success rates of finding the $s$-sparse solution $\mathbf{y}$ of $\mathbf{b = Ax}$, where $\mathbf{A} \in \mathbb{R}^{50\times 250}$ and $\mathbf{y} \in \mathbb{R}^{250}$. For each $s$-sparsity, $500$ attempts were made
Comparison of $\Vert \mathbf{y}^{k}\Vert_{1}$ and weighted $\Vert \mathbf{y}^{k}\Vert_{1}$ at each iteration $k$ with $\mathbf{A} \in \mathbb{R}^{50\times 250}$, $\mathbf{y} \in \mathbb{R}^{250}$ and $p = 0.618, s = 10$
Comparison of success rates of finding the $s$-sparse solution $\mathbf{y}$ of $\mathbf{b = Ay}$, where $\mathbf{A} \in \mathbb{R}^{50\times 250}$ and $\mathbf{y} \in \mathbb{R}^{250}$. For each $s$-sparsity, $500$ attempts were made
Comparison of $\Vert \mathbf{y}^{k}\Vert_{2}^{2}$ and weighted $\Vert \mathbf{y}^{k}\Vert_{2}^{2}$ at each iteration $k$ with $\mathbf{A} \in \mathbb{R}^{50\times 250}$, $\mathbf{y} \in \mathbb{R}^{250}$ and $p = 0.618, s = 10$
 [1] Lingchen Kong, Naihua Xiu, Guokai Liu. Partial $S$-goodness for partially sparse signal recovery. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 25-38. doi: 10.3934/naco.2014.4.25 [2] Wanyou Cheng, Zixin Chen, Donghui Li. Nomonotone spectral gradient method for sparse recovery. Inverse Problems & Imaging, 2015, 9 (3) : 815-833. doi: 10.3934/ipi.2015.9.815 [3] Eduardo Casas, Mariano Mateos, Arnd Rösch. Finite element approximation of sparse parabolic control problems. Mathematical Control & Related Fields, 2017, 7 (3) : 393-417. doi: 10.3934/mcrf.2017014 [4] Yi Shen, Song Li. Sparse signals recovery from noisy measurements by orthogonal matching pursuit. Inverse Problems & Imaging, 2015, 9 (1) : 231-238. doi: 10.3934/ipi.2015.9.231 [5] Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial & Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057 [6] Ralf Banisch, Carsten Hartmann. A sparse Markov chain approximation of LQ-type stochastic control problems. Mathematical Control & Related Fields, 2016, 6 (3) : 363-389. doi: 10.3934/mcrf.2016007 [7] Pia Heins, Michael Moeller, Martin Burger. Locally sparse reconstruction using the $l^{1,\infty}$-norm. Inverse Problems & Imaging, 2015, 9 (4) : 1093-1137. doi: 10.3934/ipi.2015.9.1093 [8] Wengu Chen, Huanmin Ge. Recovery of block sparse signals under the conditions on block RIC and ROC by BOMP and BOMMP. Inverse Problems & Imaging, 2018, 12 (1) : 153-174. doi: 10.3934/ipi.2018006 [9] Ralf Banisch, Carsten Hartmann. Addendum to "A sparse Markov chain approximation of LQ-type stochastic control problems". Mathematical Control & Related Fields, 2017, 7 (4) : 623-623. doi: 10.3934/mcrf.2017023 [10] M. Sumon Hossain, M. Monir Uddin. Iterative methods for solving large sparse Lyapunov equations and application to model reduction of index 1 differential-algebraic-equations. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 173-186. doi: 10.3934/naco.2019013 [11] Chengxiang Wang, Li Zeng, Wei Yu, Liwei Xu. Existence and convergence analysis of $\ell_{0}$ and $\ell_{2}$ regularizations for limited-angle CT reconstruction. Inverse Problems & Imaging, 2018, 12 (3) : 545-572. doi: 10.3934/ipi.2018024 [12] Björn Popilka, Simon Setzer, Gabriele Steidl. Signal recovery from incomplete measurements in the presence of outliers. Inverse Problems & Imaging, 2007, 1 (4) : 661-672. doi: 10.3934/ipi.2007.1.661 [13] Yun Cai, Song Li. Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery. Inverse Problems & Imaging, 2017, 11 (4) : 643-661. doi: 10.3934/ipi.2017030 [14] Kanghui Guo and Demetrio Labate. Sparse shearlet representation of Fourier integral operators. Electronic Research Announcements, 2007, 14: 7-19. doi: 10.3934/era.2007.14.7 [15] Mattia Bongini, Massimo Fornasier, Oliver Junge, Benjamin Scharf. Sparse control of alignment models in high dimension. Networks & Heterogeneous Media, 2015, 10 (3) : 647-697. doi: 10.3934/nhm.2015.10.647 [16] Gero Friesecke, Felix Henneke, Karl Kunisch. Frequency-sparse optimal quantum control. Mathematical Control & Related Fields, 2018, 8 (1) : 155-176. doi: 10.3934/mcrf.2018007 [17] Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems & Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025 [18] Zhifeng Dai, Fenghua Wen. A generalized approach to sparse and stable portfolio optimization problem. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1651-1666. doi: 10.3934/jimo.2018025 [19] Chao Zhang, Jingjing Wang, Naihua Xiu. Robust and sparse portfolio model for index tracking. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1001-1015. doi: 10.3934/jimo.2018082 [20] Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134

2018 Impact Factor: 1.025

## Tools

Article outline

Figures and Tables

[Back to Top]