August  2020, 19(8): 4055-4068. doi: 10.3934/cpaa.2020179

Analysis non-sparse recovery for relaxed ALASSO

School of Mathematical Sciences, Zhejiang University, Hangzhou 310027, China

* Corresponding author

Received  August 2019 Revised  November 2019 Published  May 2020

Fund Project: This work was supported in part by key project of NSF of China under grant number 11531013, the fundamental research funds for the central universities, and the NSAF of China under grant number U1630116

This paper considers recovery of signals that are corrupted with noise. We focus on a novel model which is called relaxed ALASSO (RALASSO) model introduced by Z. Tan et al. (2014). Compared to the well-known ALASSO, RALASSO can be solved better in practice. Z. Tan et al. (2014) used the $ D $-RIP to characterize the sparse or approximately sparse solutions for RALASSO when the $ D $-RIP constant $ \delta_{2k} < 0.1907 $, where the solution is sparse or approximately sparse in terms of a tight frame $ D $. However, their estimate of error bound for solution heavily depends on the term $ \Vert D^*D\Vert_{1, 1} $. Besides, compared to other works on signals recovering from ALASSO, the condition $ \delta_{2k} < 0.1907 $ is even stronger. Based on the RALASSO model, we use new methods to get a better estimate of error bound and give a weaker sufficient condition in this article for the inadequacies of the results by Z. Tan et al. (2014). One of the result of this paper is to use another method called the robust $ \ell_2 $ $ D $-Null Space Property to obtain the sparse or non-sparse solution of RALASSO and give the error estimation of RALASSO, where we eliminate the term $ \Vert D^*D\Vert_{1, 1} $ in the constants. Another result of the paper is to utilize the $ D $-RIP to obtain a new condition $ \delta_{2k} < 0.3162 $ which is weaker than the condition $ \delta_{2k} < 0.1907 $. To some extent, RALASSO is equivalent to ALASSO and the condition is also weaker than the similar one $ \delta_{3k} < 0.25 $ by J. Lin, and S. Li (2014) and $ \delta_{2k}<0.25 $ by Y. Xia, and S. Li (2016).

Citation: Hang Xu, Song Li. Analysis non-sparse recovery for relaxed ALASSO. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4055-4068. doi: 10.3934/cpaa.2020179
References:
[1]

M. V. AfonsoJ. M. Bioucas-Dias and and M. A. T. Figueiredo, Fast image recovery using variable splitting and constrained optimization, IEEE Trans. Image Process., 9 (2010), 2345-2356.  doi: 10.1109/TIP.2010.2047910.  Google Scholar

[2]

A. Beck and and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Imag. Sci., 2 (2009), 183-202.  doi: 10.1137/080716542.  Google Scholar

[3]

A. Beck and M. Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Trans. Image Process, 18 (2009), 2419-2434.  doi: 10.1109/TIP.2009.2028250.  Google Scholar

[4] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge Univ. Press, Cambridge, U.K., 2004.  doi: 10.1017/CBO9780511804441.  Google Scholar
[5]

S. BoydN. ParikhE. ChuB. Peleato and J. Eckstein, Distributed optimization and statistical learning via alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2010), 1-122.  doi: 10.1561/2200000016.  Google Scholar

[6]

T. Cai and A. Zhang, Sparse representation of a polytope and recovery of sparse signals and low-rank matrices, IEEE Trans. Inform. Theory, 60 (2014), 122-132.  doi: 10.1109/TIT.2013.2288639.  Google Scholar

[7]

E. J. CandèsJ. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52 (2006), 489-509.  doi: 10.1109/TIT.2005.862083.  Google Scholar

[8]

E. J. CandèsJ. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59 (2006), 1207-1223.  doi: 10.1002/cpa.20124.  Google Scholar

[9]

E. J. CandèsY. C. EldarD. Needell and P. Randall, Compressed sensing with coherent and redundant dictionaries, Appl. Comput. Harmon. Anal., 31 (2011), 59-73.  doi: 10.1016/j.acha.2010.10.002.  Google Scholar

[10]

S. S. ChenD. L. Donoho and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM Rev., 43 (2001), 129-159.  doi: 10.1137/S003614450037906X.  Google Scholar

[11]

D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[12]

D. L. DonohoY. TsaigI. Drori and J. L. Starck, Sparse solution of underdetermined linear equations by stagewise Orthogonal Matching Pursuit, IEEE Trans. Inform. Theory, 58 (2012), 1094-1121.  doi: 10.1109/TIT.2011.2173241.  Google Scholar

[13]

I. Drori, Fast $\ell_1$-minimization by iterative thresholding for multidimensional NMR spectroscopy, EURASIP J. Adv. Signal Process., 2007 (2007), 1-10.  doi: 10.1155/2007/20248.  Google Scholar

[14]

M. EladP. Milanfar and R. Rubinstein, Analysis versus synthesis in signal priors, Inverse Probl., 23 (2007), 947-968.  doi: 10.1088/0266-5611/23/3/007.  Google Scholar

[15]

S. Fourcart, Stability and robustness of $\ell_1$-minimization with Weibull matrices and redundant dictionaries, Linear Alg. Appl., 441 (2014), 4-21.  doi: 10.1016/j.laa.2012.10.003.  Google Scholar

[16]

M. Herman and T. Strohmer, High-resolution radar via compressed sensing, IEEE Trans. Signal Process, 57 (2009), 2275-2284.  doi: 10.1109/TSP.2009.2014277.  Google Scholar

[17]

J. Lin and S. Li, Sparse recovery with coherent tight frame 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

[18]

M. LustigD. L. DonohoJ. M. Santos and J. M. Pauly, Compressed sensing MRI, IEEE Signal Process Mag., 27 (2008), 72-82.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[19]

S. NamM. E. DaviesM. Elad and R. Gribonval, The cosparse analysis model and algorithms, Appl. Comput. Harmon. Anal., 34 (2013), 30-56.  doi: 10.1016/j.acha.2012.03.006.  Google Scholar

[20]

B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput., 24 (1995), 227-234.  doi: 10.1137/S0097539792240406.  Google Scholar

[21]

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

[22]

H. RauhutK. Schnass and P. Vandergheynst, Compressed sensing and redundant dictionaries, IEEE Trans. Inform. Theory, 54 (2008), 2210-2219.  doi: 10.1109/TIT.2008.920190.  Google Scholar

[23]

Z. TanY. C. EldarA. Beck and A. Nehorai, Smoothing and decomposition for analysis sparse recovery, IEEE Trans. Signal Process, 62 (2014), 1762-1774.  doi: 10.1109/TSP.2014.2304932.  Google Scholar

[24]

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

[25]

R. TibshiraniM. SaundersS. RossetJ. Zhu and K. Knight, Sparsity and smoothness via the fused Lasso, J. R. Statist. Soc. B. Stat. Meth., 67 (2005), 91-108.  doi: 10.1111/j.1467-9868.2005.00490.x.  Google Scholar

[26]

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

[27]

R. Zhang and S. Li, Optimal RIP bounds for sparse signals recovery via $\ell_p$ minimization, Appl. Comput. Harmon. Anal., 47 (2019), 566-584.  doi: 10.1016/j.acha.2017.10.004.  Google Scholar

show all references

References:
[1]

M. V. AfonsoJ. M. Bioucas-Dias and and M. A. T. Figueiredo, Fast image recovery using variable splitting and constrained optimization, IEEE Trans. Image Process., 9 (2010), 2345-2356.  doi: 10.1109/TIP.2010.2047910.  Google Scholar

[2]

A. Beck and and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Imag. Sci., 2 (2009), 183-202.  doi: 10.1137/080716542.  Google Scholar

[3]

A. Beck and M. Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Trans. Image Process, 18 (2009), 2419-2434.  doi: 10.1109/TIP.2009.2028250.  Google Scholar

[4] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge Univ. Press, Cambridge, U.K., 2004.  doi: 10.1017/CBO9780511804441.  Google Scholar
[5]

S. BoydN. ParikhE. ChuB. Peleato and J. Eckstein, Distributed optimization and statistical learning via alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2010), 1-122.  doi: 10.1561/2200000016.  Google Scholar

[6]

T. Cai and A. Zhang, Sparse representation of a polytope and recovery of sparse signals and low-rank matrices, IEEE Trans. Inform. Theory, 60 (2014), 122-132.  doi: 10.1109/TIT.2013.2288639.  Google Scholar

[7]

E. J. CandèsJ. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52 (2006), 489-509.  doi: 10.1109/TIT.2005.862083.  Google Scholar

[8]

E. J. CandèsJ. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59 (2006), 1207-1223.  doi: 10.1002/cpa.20124.  Google Scholar

[9]

E. J. CandèsY. C. EldarD. Needell and P. Randall, Compressed sensing with coherent and redundant dictionaries, Appl. Comput. Harmon. Anal., 31 (2011), 59-73.  doi: 10.1016/j.acha.2010.10.002.  Google Scholar

[10]

S. S. ChenD. L. Donoho and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM Rev., 43 (2001), 129-159.  doi: 10.1137/S003614450037906X.  Google Scholar

[11]

D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289-1306.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[12]

D. L. DonohoY. TsaigI. Drori and J. L. Starck, Sparse solution of underdetermined linear equations by stagewise Orthogonal Matching Pursuit, IEEE Trans. Inform. Theory, 58 (2012), 1094-1121.  doi: 10.1109/TIT.2011.2173241.  Google Scholar

[13]

I. Drori, Fast $\ell_1$-minimization by iterative thresholding for multidimensional NMR spectroscopy, EURASIP J. Adv. Signal Process., 2007 (2007), 1-10.  doi: 10.1155/2007/20248.  Google Scholar

[14]

M. EladP. Milanfar and R. Rubinstein, Analysis versus synthesis in signal priors, Inverse Probl., 23 (2007), 947-968.  doi: 10.1088/0266-5611/23/3/007.  Google Scholar

[15]

S. Fourcart, Stability and robustness of $\ell_1$-minimization with Weibull matrices and redundant dictionaries, Linear Alg. Appl., 441 (2014), 4-21.  doi: 10.1016/j.laa.2012.10.003.  Google Scholar

[16]

M. Herman and T. Strohmer, High-resolution radar via compressed sensing, IEEE Trans. Signal Process, 57 (2009), 2275-2284.  doi: 10.1109/TSP.2009.2014277.  Google Scholar

[17]

J. Lin and S. Li, Sparse recovery with coherent tight frame 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

[18]

M. LustigD. L. DonohoJ. M. Santos and J. M. Pauly, Compressed sensing MRI, IEEE Signal Process Mag., 27 (2008), 72-82.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[19]

S. NamM. E. DaviesM. Elad and R. Gribonval, The cosparse analysis model and algorithms, Appl. Comput. Harmon. Anal., 34 (2013), 30-56.  doi: 10.1016/j.acha.2012.03.006.  Google Scholar

[20]

B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput., 24 (1995), 227-234.  doi: 10.1137/S0097539792240406.  Google Scholar

[21]

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

[22]

H. RauhutK. Schnass and P. Vandergheynst, Compressed sensing and redundant dictionaries, IEEE Trans. Inform. Theory, 54 (2008), 2210-2219.  doi: 10.1109/TIT.2008.920190.  Google Scholar

[23]

Z. TanY. C. EldarA. Beck and A. Nehorai, Smoothing and decomposition for analysis sparse recovery, IEEE Trans. Signal Process, 62 (2014), 1762-1774.  doi: 10.1109/TSP.2014.2304932.  Google Scholar

[24]

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

[25]

R. TibshiraniM. SaundersS. RossetJ. Zhu and K. Knight, Sparsity and smoothness via the fused Lasso, J. R. Statist. Soc. B. Stat. Meth., 67 (2005), 91-108.  doi: 10.1111/j.1467-9868.2005.00490.x.  Google Scholar

[26]

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

[27]

R. Zhang and S. Li, Optimal RIP bounds for sparse signals recovery via $\ell_p$ minimization, Appl. Comput. Harmon. Anal., 47 (2019), 566-584.  doi: 10.1016/j.acha.2017.10.004.  Google Scholar

[1]

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

[2]

Huining Qiu, Xiaoming Chen, Wanquan Liu, Guanglu Zhou, Yiju Wang, Jianhuang Lai. A fast $\ell_1$-solver and its applications to robust face recognition. Journal of Industrial & Management Optimization, 2012, 8 (1) : 163-178. doi: 10.3934/jimo.2012.8.163

[3]

Hui Huang, Eldad Haber, Lior Horesh. Optimal estimation of $\ell_1$-regularization prior from a regularized empirical Bayesian risk standpoint. Inverse Problems & Imaging, 2012, 6 (3) : 447-464. doi: 10.3934/ipi.2012.6.447

[4]

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

[5]

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, 3 (3) : 205-218. doi: 10.3934/mfc.2020020

[6]

Peng Gao. Carleman estimates and Unique Continuation Property for 1-D viscous Camassa-Holm equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (1) : 169-188. doi: 10.3934/dcds.2017007

[7]

Julia García-Luengo, Pedro Marín-Rubio. Pullback attractors for 2D Navier–Stokes equations with delays and the flattening property. Communications on Pure & Applied Analysis, 2020, 19 (4) : 2127-2146. doi: 10.3934/cpaa.2020094

[8]

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

[9]

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

[10]

Henri Schurz. Stochastic heat equations with cubic nonlinearity and additive space-time noise in 2D. Conference Publications, 2013, 2013 (special) : 673-684. doi: 10.3934/proc.2013.2013.673

[11]

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

[12]

Géry de Saxcé, Claude Vallée. Structure of the space of 2D elasticity tensors. Discrete & Continuous Dynamical Systems - S, 2013, 6 (6) : 1525-1537. doi: 10.3934/dcdss.2013.6.1525

[13]

Patrick Fischer. Multiresolution analysis for 2D turbulence. Part 1: Wavelets vs cosine packets, a comparative study. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 659-686. doi: 10.3934/dcdsb.2005.5.659

[14]

A. Naga, Z. Zhang. The polynomial-preserving recovery for higher order finite element methods in 2D and 3D. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 769-798. doi: 10.3934/dcdsb.2005.5.769

[15]

François Delarue, Franco Flandoli. The transition point in the zero noise limit for a 1D Peano example. Discrete & Continuous Dynamical Systems - A, 2014, 34 (10) : 4071-4083. doi: 10.3934/dcds.2014.34.4071

[16]

H. T. Banks, R.C. Smith. Feedback control of noise in a 2-D nonlinear structural acoustics model. Discrete & Continuous Dynamical Systems - A, 1995, 1 (1) : 119-149. doi: 10.3934/dcds.1995.1.119

[17]

Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems & Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487

[18]

Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems & Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761

[19]

Yang Yang, Xiaohu Tang, Guang Gong. New almost perfect, odd perfect, and perfect sequences from difference balanced functions with d-form property. Advances in Mathematics of Communications, 2017, 11 (1) : 67-76. doi: 10.3934/amc.2017002

[20]

Steven L. Brunton, Joshua L. Proctor, Jonathan H. Tu, J. Nathan Kutz. Compressed sensing and dynamic mode decomposition. Journal of Computational Dynamics, 2015, 2 (2) : 165-191. doi: 10.3934/jcd.2015002

2019 Impact Factor: 1.105

Metrics

  • PDF downloads (83)
  • HTML views (68)
  • Cited by (0)

Other articles
by authors

[Back to Top]