×

Sparse signal inversion with impulsive noise by dual spectral projected gradient method. (English) Zbl 1426.94040

Summary: We consider sparse signal inversion with impulsive noise. There are three major ingredients. The first is regularizing properties; we discuss convergence rate of regularized solutions. The second is devoted to the numerical solutions. It is challenging due to the fact that both fidelity and regularization term lack differentiability. Moreover, for ill-conditioned problems, sparsity regularization is often unstable. We propose a novel dual spectral projected gradient (DSPG) method which combines the dual problem of multiparameter regularization with spectral projection gradient method to solve the nonsmooth \(\ell^1 + \ell^1\) optimization functional. We show that one can overcome the nondifferentiability and instability by adding a smooth \(\ell^2\) regularization term to the original optimization functional. The advantage of the proposed functional is that its convex duality reduced to a constraint smooth functional. Moreover, it is stable even for ill-conditioned problems. Spectral projected gradient algorithm is used to compute the minimizers and we prove the convergence. The third is numerical simulation. Some experiments are performed, using compressed sensing and image inpainting, to demonstrate the efficiency of the proposed approach.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
65J20 Numerical solutions of ill-posed problems in abstract spaces; regularization
47A52 Linear operators and ill-posed problems, regularization

Software:

Yall1
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Candès, E. J.; Romberg, J. K.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Communications on Pure and Applied Mathematics, 59, 8, 1207-1223, (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124
[2] Donoho, D. L., Compressed sensing, IEEE Transactions on Information Theory, 52, 4, 1289-1306, (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[3] Gao, H.; Zhao, H., Multilevel bioluminescence tomography based on radiative transfer equation part 1: 1 regularization, Optics Express, 18, 3, 1854-1871, (2010) · doi:10.1364/OE.18.001854
[4] Loris, I.; Nolet, G.; Daubechies, I.; Dahlen, F. A., Tomographic inversion using 1-norm regularization of wavelet coefficients, Geophysical Journal International, 170, 1, 359-370, (2007) · doi:10.1111/j.1365-246X.2007.03409.x
[5] Jin, B.; Maass, P., Sparsity regularization for parameter identification problems, Inverse Problems, 28, 12, (2012) · Zbl 1280.47063 · doi:10.1088/0266-5611/28/12/123001
[6] Daubechies, I.; Defrise, M.; De Mol, C., An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Communications on Pure and Applied Mathematics, 57, 11, 1413-1457, (2004) · Zbl 1077.65055 · doi:10.1002/cpa.20042
[7] Fornasier, M., Theoretical Foundations and Numerical Methods for Sparse Recovery, (2010), De Gruyter · Zbl 1195.94005
[8] Grasmair, M., Non-convex sparse regularisation, Journal of Mathematical Analysis and Applications, 365, 1, 19-28, (2010) · Zbl 1186.65067 · doi:10.1016/j.jmaa.2009.09.055
[9] Nikolova, M., Description of the minimizers of least squares regularized with l(0)-norm. Uniqueness of the global minimizer, SIAM Journal on Imaging Sciences, 6, 2, 904-937, (2013) · Zbl 1281.65092 · doi:10.1137/11085476X
[10] Zarzer, C. A., On Tikhonov regularization with non-convex sparsity constraints, Inverse Problems, 25, 2, (2009) · Zbl 1161.65044 · doi:10.1088/0266-5611/25/2/025006
[11] Wang, W.; Lu, S.; Mao, H.; Cheng, J., Multi-parameter Tikhonov regularization with the l(0) sparsity constraint, Inverse Problems, 29, 6, (2013) · Zbl 1273.65068 · doi:10.1088/0266-5611/29/6/065018
[12] Rousseeuw, P. J.; Leroy, A. M., Robust Regression and Outlier Detection, (1987), New York, NY, USA: John Wiley & Sons, New York, NY, USA · Zbl 0711.62030
[13] Alliney, S., Digital filters as absolute norm regularizers, IEEE Transactions on Signal Processing, 40, 6, 1548-1562, (1992) · Zbl 0859.93037 · doi:10.1109/78.139258
[14] Clason, C.; Jin, B.; Kunisch, K., A duality-based splitting method for l1-TV image restoration with automatic regularization parameter choice, SIAM Journal on Scientific Computing, 32, 3, 1484-1505, (2010) · Zbl 1216.94009 · doi:10.1137/090768217
[15] Nikolova, M., Minimizers of cost-functions involving nonsmooth data-fidelity terms. Application to the processing of outliers, SIAM Journal on Numerical Analysis, 40, 3, 965-994, (2002) · Zbl 1018.49025 · doi:10.1137/S0036142901389165
[16] Dong, Y.; Hintermüller, M.; Neri, M., An efficient primal-dual method for l1-TV image restoration, SIAM Journal on Imaging Sciences, 2, 4, 1168-1189, (2009) · Zbl 1187.68653 · doi:10.1137/090758490
[17] Yin, W.; Goldfarb, D.; Osher, S., The total variation regularized L1 model for multiscale decomposition, Multiscale Modeling and Simulation, 6, 1, 190-211, (2007) · Zbl 1355.49037 · doi:10.1137/060663027
[18] Yang, J.; Zhang, Y., Alternating direction algorithms for l1-problems in compressive sensing, SIAM Journal on Scientific Computing, 33, 1, 250-278, (2011) · Zbl 1256.65060 · doi:10.1137/090777761
[19] Yang, J.; Zhang, Y., A primal-dual interior-point framework for using the L1 or L2 norm on the data and regularization terms of inverse problems, SIAM Journal on Scientific Computing, 33, 1, 250-278, (2011) · Zbl 1256.65060
[20] Stanković, S.; Orović, I.; Amin, M., L-statistics based modification of reconstruction algorithms for compressive sensing in the presence of impulse noise, Signal Processing, 93, 11, 2927-2931, (2013) · doi:10.1016/j.sigpro.2013.04.022
[21] Ma, L.; Yu, J.; Zeng, T., Sparse representation prior and total variation-based image deblurring under impulse noise, SIAM Journal on Imaging Sciences, 6, 4, 2258-2284, (2013) · Zbl 1279.68334 · doi:10.1137/120866452
[22] Shang, J.; Wang, Z.; Huang, Q., A robust algorithm for joint sparse recovery in presence of impulsive noise, IEEE Signal Processing Letters, 22, 8, 1166-1170, (2015) · doi:10.1109/LSP.2014.2387435
[23] Chen, L.; Liu, L.; Philip Chen, C. L., A robust bi-sparsity model with non-local regularization for mixed noise reduction, Information Sciences, 354, 101-111, (2016) · doi:10.1016/j.ins.2016.03.014
[24] Burger, M.; Osher, S., Convergence rates of convex variational regularization, Inverse Problems, 20, 5, 1411-1421, (2004) · Zbl 1068.65085 · doi:10.1088/0266-5611/20/5/005
[25] Neubauer, A.; Hein, T.; Hofmann, B.; Kindermann, S.; Tautenhahn, U., Improved and extended results for enhanced convergence rates of Tikhonov regularization in Banach spaces, Applicable Analysis, 89, 11, 1729-1743, (2010) · Zbl 1214.65031 · doi:10.1080/00036810903517597
[26] Grasmair, M.; Haltmeier, M.; Scherzer, O., Necessary and sufficient conditions for linear convergence of l1-regularization, Communications on Pure and Applied Mathematics, 64, 2, 161-182, (2011) · Zbl 1217.65095 · doi:10.1002/cpa.20350
[27] Flemming, J.; Hegland, M., Convergence rates in l1-regularization when the basis is not smooth enough, Applicable Analysis, 94, 3, 464-476, (2015) · Zbl 1325.65076 · doi:10.1080/00036811.2014.886106
[28] König, C.; Werner, F.; Hohage, T., Convergence rates for exponentially ill-posed inverse problems with impulsive noise, SIAM Journal on Numerical Analysis, 54, 1, 341-360, (2016) · Zbl 1382.65161 · doi:10.1137/15M1022252
[29] Efron, B.; Hastie, T.; Johnstone, I.; Tibshirani, R., Least angle regression, The Annals of Statistics, 32, 2, 407-499, (2004) · Zbl 1091.62054 · doi:10.1214/009053604000000067
[30] Daubechies, I.; DeVore, R.; Fornasier, M.; Güntürk, C. S., Iteratively reweighted least squares minimization for sparse recovery, Communications on Pure and Applied Mathematics, 63, 1, 1-38, (2010) · Zbl 1202.65046 · doi:10.1002/cpa.20303
[31] Blumensath, T.; Davies, M. E., Iterative thresholding for sparse approximations, The Journal of Fourier Analysis and Applications, 14, 5-6, 629-654, (2008) · Zbl 1175.94060 · doi:10.1007/s00041-008-9035-z
[32] Blumensath, T.; Davies, M. E., Iterative hard thresholding for compressed sensing, Applied and Computational Harmonic Analysis, 27, 3, 265-274, (2009) · Zbl 1174.94008 · doi:10.1016/j.acha.2009.04.002
[33] Cullen, M.; Freitag, M. A.; Kindermann, S., Large Scale Inverse Problems: Computational Methods and Applications in the Earth Sciences, (2013), Austria: De Gruyter, Austria
[34] Xiao, Y.; Zhu, H.; Wu, S.-Y., Primal and dual alternating direction algorithms for l1-l1 norm minimization problems in compressive sensing, Computational Optimization and Applications, 54, 2, 441-459, (2013) · Zbl 1269.90081 · doi:10.1007/s10589-012-9475-x
[35] Lu, S.; Pereverzev, S. V., Multi-parameter regularization and its numerical realization, Numerische Mathematik, 118, 1, 1-31, (2011) · Zbl 1221.65128 · doi:10.1007/s00211-010-0318-3
[36] Lu, S.; Pereverzev, S. V.; Shao, Y.; Tautenhahn, U., Discrepancy curves for multi-parameter regularization, Journal of Inverse and Ill-Posed Problems, 18, 6, 655-676, (2010) · Zbl 1280.47016 · doi:10.1515/JIIP.2010.030
[37] Ito, K.; Jin, B.; Takeuchi, T., Multi-parameter Tikhonov regularization, Methods & Applications of Analysis, 18, 1, 31-46, (2011) · Zbl 1285.65032
[38] Scherzer, O.; Grasmair, M.; Grossauer, H.; Haltmeier, M.; Lenzen, F., Variational Methods in Imaging, (2011), Springer
[39] Schuster, T.; Kaltenbacher, B.; Hofmann, B.; Kazimierski, K. S., Regularization Methods in Banach Spaces, (2012), De Gruyter · Zbl 1259.65087
[40] Morozov, V. A., On the solution of functional equations by the method of regularization, Soviet Mathematics. Doklady, 7, 510-512, (1966) · Zbl 0187.12203
[41] Mallet, S. G., A Wavelet Tour of Signal Processing, (2010), Oxford, UK: Elsevier, Oxford, UK
[42] Loris, I.; Nolet, G.; Daubechies, I.; Dahlen, F. A., Tomographic inversion using l1-norm regularization of wavelet coefficients, Geophysical Journal International, 170, 1, 359-370, (2007) · doi:10.1111/j.1365-246X.2007.03409.x
[43] Ekeland, I.; Man, R., Convex Analysis and Variational Problems, (1999), Philadelphia, Pa, USA: SIAM, Philadelphia, Pa, USA · Zbl 0939.49002
[44] Birgin, E. G.; Martinez, J. M.; Raydan, M., Nonmonotone spectral projected gradient methods on convex sets, SIAM Journal on Optimization, 10, 4, 1196-1211, (2000) · Zbl 1047.90077 · doi:10.1137/S1052623497330963
[45] Kim, S. J.; Koh, K.; Lustig, M., A method for large-scale l1-regularized least squares, IEEE Journal on Selected Topics in Signal Processing, 1, 4, 606-617, (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.