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]

Victor Churchill, Rick Archibald, Anne Gelb. Edge-adaptive $ \ell_2 $ regularization image reconstruction from non-uniform Fourier data. Inverse Problems & Imaging, 2019, 13 (5) : 931-958. doi: 10.3934/ipi.2019042

[2]

Jun Wang, Xing Tao Wang. Sparse signal reconstruction via the approximations of $ \ell_{0} $ quasinorm. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1907-1925. doi: 10.3934/jimo.2019035

[3]

Ying Lin, Rongrong Lin, Qi Ye. Sparse regularized learning in the reproducing kernel banach spaces with the $ \ell^1 $ norm. Mathematical Foundations of Computing, 2020  doi: 10.3934/mfc.2020020

[4]

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

[5]

Lianjun Zhang, Lingchen Kong, Yan Li, Shenglong Zhou. A smoothing iterative method for quantile regression with nonconvex $ \ell_p $ penalty. Journal of Industrial & Management Optimization, 2017, 13 (1) : 93-112. doi: 10.3934/jimo.2016006

[6]

Martin Heida, Stefan Neukamm, Mario Varga. Stochastic homogenization of $ \Lambda $-convex gradient flows. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020328

[7]

Lingyan Cheng, Ruinan Li, Liming Wu. Exponential convergence in the Wasserstein metric $ W_1 $ for one dimensional diffusions. Discrete & Continuous Dynamical Systems - A, 2020, 40 (9) : 5131-5148. doi: 10.3934/dcds.2020222

[8]

Umberto De Maio, Peter I. Kogut, Gabriella Zecca. On optimal $ L^1 $-control in coefficients for quasi-linear Dirichlet boundary value problems with $ BMO $-anisotropic $ p $-Laplacian. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020021

[9]

Genni Fragnelli, Jerome A. Goldstein, Rosa Maria Mininni, Silvia Romanelli. Operators of order 2$ n $ with interior degeneracy. Discrete & Continuous Dynamical Systems - S, 2019  doi: 10.3934/dcdss.2020128

[10]

Guoyuan Chen, Yong Liu, Juncheng Wei. Nondegeneracy of harmonic maps from $ {{\mathbb{R}}^{2}} $ to $ {{\mathbb{S}}^{2}} $. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3215-3233. doi: 10.3934/dcds.2019228

[11]

Vladimir Chepyzhov, Alexei Ilyin, Sergey Zelik. Strong trajectory and global $\mathbf{W^{1,p}}$-attractors for the damped-driven Euler system in $\mathbb R^2$. Discrete & Continuous Dynamical Systems - B, 2017, 22 (5) : 1835-1855. doi: 10.3934/dcdsb.2017109

[12]

Abdeladim El Akri, Lahcen Maniar. Uniform indirect boundary controllability of semi-discrete $ 1 $-$ d $ coupled wave equations. Mathematical Control & Related Fields, 2019  doi: 10.3934/mcrf.2020015

[13]

Yong Zhou, Jia Wei He. New results on controllability of fractional evolution systems with order $ \alpha\in (1,2) $. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020077

[14]

Yi Peng, Jinbiao Wu. On the $ BMAP_1, BMAP_2/PH/g, c $ retrial queueing system. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020124

[15]

Teresa Alberico, Costantino Capozzoli, Luigi D'Onofrio, Roberta Schiattarella. $G$-convergence for non-divergence elliptic operators with VMO coefficients in $\mathbb R^3$. Discrete & Continuous Dynamical Systems - S, 2019, 12 (2) : 129-137. doi: 10.3934/dcdss.2019009

[16]

Shengbing Deng. Construction solutions for Neumann problem with Hénon term in $ \mathbb{R}^2 $. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 2233-2253. doi: 10.3934/dcds.2019094

[17]

James Montaldi, Amna Shaddad. Non-Abelian momentum polytopes for products of $ \mathbb{CP}^2 $. Journal of Geometric Mechanics, 2019, 11 (4) : 575-599. doi: 10.3934/jgm.2019029

[18]

Pak Tung Ho. Prescribing $ Q $-curvature on $ S^n $ in the presence of symmetry. Communications on Pure & Applied Analysis, 2020, 19 (2) : 715-722. doi: 10.3934/cpaa.2020033

[19]

Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020056

[20]

Jennifer D. Key, Bernardo G. Rodrigues. Binary codes from $ m $-ary $ n $-cubes $ Q^m_n $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020079

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]