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 and 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.

[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.

[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.

[4] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge Univ. Press, Cambridge, U.K., 2004.  doi: 10.1017/CBO9780511804441.
[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.

[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.

[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.

[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.

[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.

[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.

[11]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[20]

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

[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.

[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.

[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.

[24]

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

[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.

[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.

[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.

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.

[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.

[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.

[4] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge Univ. Press, Cambridge, U.K., 2004.  doi: 10.1017/CBO9780511804441.
[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.

[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.

[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.

[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.

[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.

[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.

[11]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[20]

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

[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.

[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.

[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.

[24]

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

[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.

[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.

[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.

[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 and Management Optimization, 2012, 8 (1) : 163-178. doi: 10.3934/jimo.2012.8.163

[3]

Liang Ding, Weimin Han. Morozov's discrepancy principle for $ \alpha\ell_1-\beta\ell_2 $ sparsity regularization. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2022035

[4]

Qing Ma, Yanjun Wang. Distributionally robust chance constrained svm model with $\ell_2$-Wasserstein distance. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021212

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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 and Imaging, 2018, 12 (3) : 545-572. doi: 10.3934/ipi.2018024

[11]

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 and Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057

[12]

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

[13]

Ting Chen, Fusheng Lv, Wenchang Sun. Uniform Approximation Property of Frames with Applications to Erasure Recovery. Communications on Pure and Applied Analysis, 2022, 21 (3) : 1093-1107. doi: 10.3934/cpaa.2022011

[14]

Peili Li, Xiliang Lu, Yunhai Xiao. Smoothing Newton method for $ \ell^0 $-$ \ell^2 $ regularized linear inverse problem. Inverse Problems and Imaging, 2022, 16 (1) : 153-177. doi: 10.3934/ipi.2021044

[15]

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

[16]

Francesco Grotto, Umberto Pappalettera. Gaussian invariant measures and stationary solutions of 2D primitive equations. Discrete and Continuous Dynamical Systems - B, 2022, 27 (5) : 2683-2699. doi: 10.3934/dcdsb.2021154

[17]

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

[18]

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

[19]

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

[20]

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

2021 Impact Factor: 1.273

Metrics

  • PDF downloads (232)
  • HTML views (80)
  • Cited by (0)

Other articles
by authors

[Back to Top]