May  2020, 3(2): 65-79. doi: 10.3934/mfc.2020006

Unconstrained $ \ell_1 $-$ \ell_2 $ minimization for sparse recovery via mutual coherence

1. 

Graduate School, China Academy of Engineering Physics, Beijing 100088, China

2. 

Institute of Applied Physics and Computational Mathematics, Beijing, 100088, China

* Corresponding author: Wengu Chen

Received  December 2019 Revised  March 2020 Published  May 2020

Fund Project: This work was supported by the NSF of China (No.11871109) and NSAF(Grant No.U1830107)

The paradigm of compressed sensing is to exactly or stably recover any sparse signal $ x\in \mathbb{R}^n $ from a small number of linear measurements $ b = Ax+e $, where $ A\in\mathbb{R}^{m\times n} $ with $ m\ll n $ and $ e\in \mathbb{R}^m $ denotes the measurement noise. $ \ell_1 $-$ \ell_2 $ minimization has recently become an effective signal recovery method. In this paper, a mutual coherence based signal recovery guarantee by the unconstrained $ \ell_1 $-$ \ell_2 $ minimization model is given to achieve the stable recovery of any sparse signal $ x $ in the presence of the Dantzig Selector (DS) type noise or the $ \ell_2 $ bounded noise, respectively. To the best of our knowledge, this is the first mutual coherence based sufficient condition to achieve sparse signal recovery via the unconstrained $ \ell_1 $-$ \ell_2 $ minimization.

Citation: Pengbo Geng, Wengu Chen. Unconstrained $ \ell_1 $-$ \ell_2 $ minimization for sparse recovery via mutual coherence. Mathematical Foundations of Computing, 2020, 3 (2) : 65-79. doi: 10.3934/mfc.2020006
References:
[1]

P. J. BickelY. Ritov and A. B. Tsybakov, Simultaneous analysis of lasso and Dantzig selector, Ann. Statist., 37 (2009), 1705-1732.  doi: 10.1214/08-AOS620.  Google Scholar

[2]

T. Blumensath and M. E. Davis, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27 (2009), 265-274.  doi: 10.1016/j.acha.2009.04.002.  Google Scholar

[3]

T. T. CaiL. Wang and G. Xu, Stable recovery of sparse signals and an oracle inequality, IEEE Trans. Inform. Theory, 56 (2010), 3516-3522.  doi: 10.1109/TIT.2010.2048506.  Google Scholar

[4]

Y. de Castro, A remark on the lasso and the Dantzig selector, Statist. Probab. Lett., 83 (2013), 304-314.  doi: 10.1016/j.spl.2012.09.020.  Google Scholar

[5]

S. S. ChenD. L. Donoho and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20 (1998), 33-61.  doi: 10.1137/S1064827596304010.  Google Scholar

[6]

W. Dai and O. Milenkovic, Subspace pursuit for compressive sensing signal reconstruction, IEEE Trans. Inform. Theory, 55 (2009), 2230-2249.  doi: 10.1109/TIT.2009.2016006.  Google Scholar

[7]

D. L. DonohoM. Elad and V. N. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Inform. Theory, 52 (2006), 6-18.  doi: 10.1109/TIT.2005.860430.  Google Scholar

[8]

D. L. Donoho and X. Huo, Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inform. Theory, 47 (2001), 2845-2862.  doi: 10.1109/18.959265.  Google Scholar

[9]

E. EsserY. Lou and J. Xin, A method for finding structured sparse solutions to non-negative least squares problems with applications, SIAM J. Imaging Sci., 6 (2013), 2010-2046.  doi: 10.1137/13090540X.  Google Scholar

[10]

J. Lin and S. Li, Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO, Appl. Comput. Harmon. Anal., 37 (2014), 126-139.  doi: 10.1016/j.acha.2013.10.003.  Google Scholar

[11]

Y. LouS. Osher and J. Xin, Computational aspects of constrained $L_1$-$L_2$ minimization for compressive sensing, Modelling, Computation and Optimization in Information Systems and Management Sciences, 359 (2015), 169-180.  doi: 10.1007/978-3-319-18161-5_15.  Google Scholar

[12]

Y. Lou and M. Yan, Fast $L_1$-$L_2$ minimization via a proximal operator, J. Sci. Comput., 74 (2018), 767-785.  doi: 10.1007/s10915-017-0463-2.  Google Scholar

[13]

Y. LouP. YinQ. He and J. Xin, Computing sparse representation in a highly coherent dictionary based on difference of $L_1$ and $L_2$, J. Sci. Comput., 64 (2015), 178-196.  doi: 10.1007/s10915-014-9930-1.  Google Scholar

[14]

D. Needell and J. A. Tropp, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26 (2009), 301-321.  doi: 10.1016/j.acha.2008.07.002.  Google Scholar

[15]

Y. ShenB. Han and E. Braverman, Stable recovery of analysis based approaches, Appl. Comput. Harmon. Anal., 39 (2015), 161-172.  doi: 10.1016/j.acha.2014.08.001.  Google Scholar

[16]

R. Tibshirani, Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B, 58 (1996), 267-288.   Google Scholar

[17]

J. A. Tropp and A. C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inform. Theory, 53 (2007), 4655-4666.  doi: 10.1109/TIT.2007.909108.  Google Scholar

[18]

J. Wang, Support recovery with orthogonal matching pursuit in the presence of noise, IEEE Trans. Signal Process., 63 (2015), 5868-5877.  doi: 10.1109/TSP.2015.2468676.  Google Scholar

[19]

J. Wang and P. Li, Recovery of sparse signals using multiple orthogonal least squares, IEEE Trans. Signal Process., 65 (2017), 2049-2062.  doi: 10.1109/TSP.2016.2639467.  Google Scholar

[20]

W. Wang, F. Zhang, Z. Wang, and J. Wang, Coherence-based performance guarantee of regularized $\ell_1$-norm minimization and beyond, preprint, arXiv: 1812.03739. Google Scholar

[21]

J. WenD. Li and F. Zhu, Stable recovery of sparse signals via $\ell_p$ minimization, Appl. Comput. Harmon. Anal., 38 (2015), 161-176.  doi: 10.1016/j.acha.2014.06.003.  Google Scholar

[22]

J. WenJ. Wang and Q. Zhang, Nearly optimal bounds for orthogonal least squares, IEEE Trans. Signal Process., 65 (2017), 5347-5356.  doi: 10.1109/TSP.2017.2728502.  Google Scholar

[23]

J. WenJ. WengC. TongC. Ren and Z. Zhou, Sparse signal recovery with minimization of 1-norm minus 2-norm, IEEE Transactions on Vehicular Technology, 68 (2019), 6847-6854.  doi: 10.1109/TVT.2019.2919612.  Google Scholar

[24]

J. WenZ. ZhouJ. WangX. Tang and Q. Mo, A sharp condition for exact support recovery with orthogonal matching pursuit, IEEE Trans. Signal Process., 65 (2017), 1370-1382.  doi: 10.1109/TSP.2016.2634550.  Google Scholar

[25]

Y. Xia and S. Li, Analysis recovery with coherent frames and correlated measurements, IEEE Trans. Inform. Theory, 62 (2016), 6493-6507.  doi: 10.1109/TIT.2016.2606638.  Google Scholar

[26]

P. Yin, Y. Lou, Q. He and J. Xin, Minimization of $\ell_{1-2}$ for compressed sensing, SIAM J. Sci. Comput., 37 (2015), A536–A563. doi: 10.1137/140952363.  Google Scholar

show all references

References:
[1]

P. J. BickelY. Ritov and A. B. Tsybakov, Simultaneous analysis of lasso and Dantzig selector, Ann. Statist., 37 (2009), 1705-1732.  doi: 10.1214/08-AOS620.  Google Scholar

[2]

T. Blumensath and M. E. Davis, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27 (2009), 265-274.  doi: 10.1016/j.acha.2009.04.002.  Google Scholar

[3]

T. T. CaiL. Wang and G. Xu, Stable recovery of sparse signals and an oracle inequality, IEEE Trans. Inform. Theory, 56 (2010), 3516-3522.  doi: 10.1109/TIT.2010.2048506.  Google Scholar

[4]

Y. de Castro, A remark on the lasso and the Dantzig selector, Statist. Probab. Lett., 83 (2013), 304-314.  doi: 10.1016/j.spl.2012.09.020.  Google Scholar

[5]

S. S. ChenD. L. Donoho and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20 (1998), 33-61.  doi: 10.1137/S1064827596304010.  Google Scholar

[6]

W. Dai and O. Milenkovic, Subspace pursuit for compressive sensing signal reconstruction, IEEE Trans. Inform. Theory, 55 (2009), 2230-2249.  doi: 10.1109/TIT.2009.2016006.  Google Scholar

[7]

D. L. DonohoM. Elad and V. N. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Inform. Theory, 52 (2006), 6-18.  doi: 10.1109/TIT.2005.860430.  Google Scholar

[8]

D. L. Donoho and X. Huo, Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inform. Theory, 47 (2001), 2845-2862.  doi: 10.1109/18.959265.  Google Scholar

[9]

E. EsserY. Lou and J. Xin, A method for finding structured sparse solutions to non-negative least squares problems with applications, SIAM J. Imaging Sci., 6 (2013), 2010-2046.  doi: 10.1137/13090540X.  Google Scholar

[10]

J. Lin and S. Li, Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO, Appl. Comput. Harmon. Anal., 37 (2014), 126-139.  doi: 10.1016/j.acha.2013.10.003.  Google Scholar

[11]

Y. LouS. Osher and J. Xin, Computational aspects of constrained $L_1$-$L_2$ minimization for compressive sensing, Modelling, Computation and Optimization in Information Systems and Management Sciences, 359 (2015), 169-180.  doi: 10.1007/978-3-319-18161-5_15.  Google Scholar

[12]

Y. Lou and M. Yan, Fast $L_1$-$L_2$ minimization via a proximal operator, J. Sci. Comput., 74 (2018), 767-785.  doi: 10.1007/s10915-017-0463-2.  Google Scholar

[13]

Y. LouP. YinQ. He and J. Xin, Computing sparse representation in a highly coherent dictionary based on difference of $L_1$ and $L_2$, J. Sci. Comput., 64 (2015), 178-196.  doi: 10.1007/s10915-014-9930-1.  Google Scholar

[14]

D. Needell and J. A. Tropp, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26 (2009), 301-321.  doi: 10.1016/j.acha.2008.07.002.  Google Scholar

[15]

Y. ShenB. Han and E. Braverman, Stable recovery of analysis based approaches, Appl. Comput. Harmon. Anal., 39 (2015), 161-172.  doi: 10.1016/j.acha.2014.08.001.  Google Scholar

[16]

R. Tibshirani, Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B, 58 (1996), 267-288.   Google Scholar

[17]

J. A. Tropp and A. C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inform. Theory, 53 (2007), 4655-4666.  doi: 10.1109/TIT.2007.909108.  Google Scholar

[18]

J. Wang, Support recovery with orthogonal matching pursuit in the presence of noise, IEEE Trans. Signal Process., 63 (2015), 5868-5877.  doi: 10.1109/TSP.2015.2468676.  Google Scholar

[19]

J. Wang and P. Li, Recovery of sparse signals using multiple orthogonal least squares, IEEE Trans. Signal Process., 65 (2017), 2049-2062.  doi: 10.1109/TSP.2016.2639467.  Google Scholar

[20]

W. Wang, F. Zhang, Z. Wang, and J. Wang, Coherence-based performance guarantee of regularized $\ell_1$-norm minimization and beyond, preprint, arXiv: 1812.03739. Google Scholar

[21]

J. WenD. Li and F. Zhu, Stable recovery of sparse signals via $\ell_p$ minimization, Appl. Comput. Harmon. Anal., 38 (2015), 161-176.  doi: 10.1016/j.acha.2014.06.003.  Google Scholar

[22]

J. WenJ. Wang and Q. Zhang, Nearly optimal bounds for orthogonal least squares, IEEE Trans. Signal Process., 65 (2017), 5347-5356.  doi: 10.1109/TSP.2017.2728502.  Google Scholar

[23]

J. WenJ. WengC. TongC. Ren and Z. Zhou, Sparse signal recovery with minimization of 1-norm minus 2-norm, IEEE Transactions on Vehicular Technology, 68 (2019), 6847-6854.  doi: 10.1109/TVT.2019.2919612.  Google Scholar

[24]

J. WenZ. ZhouJ. WangX. Tang and Q. Mo, A sharp condition for exact support recovery with orthogonal matching pursuit, IEEE Trans. Signal Process., 65 (2017), 1370-1382.  doi: 10.1109/TSP.2016.2634550.  Google Scholar

[25]

Y. Xia and S. Li, Analysis recovery with coherent frames and correlated measurements, IEEE Trans. Inform. Theory, 62 (2016), 6493-6507.  doi: 10.1109/TIT.2016.2606638.  Google Scholar

[26]

P. Yin, Y. Lou, Q. He and J. Xin, Minimization of $\ell_{1-2}$ for compressed sensing, SIAM J. Sci. Comput., 37 (2015), A536–A563. doi: 10.1137/140952363.  Google Scholar

Figure 1.  An illustration of the upper bounds of $ \mu $
Figure 2.  Success rate and $ \frac{\|\hat{x}\|_0}{\|x\|_0} $ as a function of $ \lambda $ for Case 1 with $ s = 20 $
Figure 3.  Success rate and $ \frac{\|\hat{x}\|_0}{\|x\|_0} $ as a function of $ \lambda $ for Case 1 with $ s = 40 $
Figure 4.  Success rate and $ \frac{\|\hat{x}\|_0}{\|x\|_0} $ as a function of $ \lambda $ for Case 2 with $ s = 20 $
Figure 5.  Success rate and $ \frac{\|\hat{x}\|_0}{\|x\|_0} $ as a function of $ \lambda $ for Case 2 with $ s = 40 $
[1]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

[2]

Denis Bonheure, Silvia Cingolani, Simone Secchi. Concentration phenomena for the Schrödinger-Poisson system in $ \mathbb{R}^2 $. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020447

[3]

Federico Rodriguez Hertz, Zhiren Wang. On $ \epsilon $-escaping trajectories in homogeneous spaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 329-357. doi: 10.3934/dcds.2020365

[4]

Mathew Gluck. Classification of solutions to a system of $ n^{\rm th} $ order equations on $ \mathbb R^n $. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5413-5436. doi: 10.3934/cpaa.2020246

[5]

Yichen Zhang, Meiqiang Feng. A coupled $ p $-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075

[6]

Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363

[7]

Lihong Zhang, Wenwen Hou, Bashir Ahmad, Guotao Wang. Radial symmetry for logarithmic Choquard equation involving a generalized tempered fractional $ p $-Laplacian. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020445

[8]

Mokhtar Bouloudene, Manar A. Alqudah, Fahd Jarad, Yassine Adjabi, Thabet Abdeljawad. Nonlinear singular $ p $ -Laplacian boundary value problems in the frame of conformable derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020442

[9]

Thabet Abdeljawad, Mohammad Esmael Samei. Applying quantum calculus for the existence of solution of $ q $-integro-differential equations with three criteria. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020440

[10]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[11]

Wenjun Liu, Yukun Xiao, Xiaoqing Yue. Classification of finite irreducible conformal modules over Lie conformal algebra $ \mathcal{W}(a, b, r) $. Electronic Research Archive, , () : -. doi: 10.3934/era.2020123

[12]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[13]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025

[14]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117

[15]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074

[16]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044

[17]

Justin Holmer, Chang Liu. Blow-up for the 1D nonlinear Schrödinger equation with point nonlinearity II: Supercritical blow-up profiles. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020264

[18]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[19]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[20]

Vieri Benci, Marco Cococcioni. The algorithmic numbers in non-archimedean numerical computing environments. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020449

 Impact Factor: 

Metrics

  • PDF downloads (58)
  • HTML views (205)
  • Cited by (0)

Other articles
by authors

[Back to Top]