# American Institute of Mathematical Sciences

August  2016, 10(3): 689-709. doi: 10.3934/ipi.2016017

## An efficient projection method for nonlinear inverse problems with sparsity constraints

 1 School of Mathematical Sciences, Key Laboratory for NSLSCS of Jiangsu Province, Nanjing Normal University, Nanjing 210023, China, China, China 2 School of Civil and Environmental Engineering, Nanyang Technological University, 50 Nanyang Avenue, 639798 Singapore

Received  July 2015 Revised  March 2016 Published  August 2016

In this paper, we propose a modification of the accelerated projective steepest descent method for solving nonlinear inverse problems with an $\ell_1$ constraint on the variable, which was recently proposed by Teschke and Borries (2010 Inverse Problems 26 025007). In their method, there are some parameters need to be estimated, which is a difficult task for many applications. We overcome this difficulty by introducing a self-adaptive strategy in choosing the parameters. Theoretically, the convergence of their algorithm was guaranteed under the assumption that the underlying mapping $F$ is twice Fréchet differentiable together with some other conditions, while we can prove weak and strong convergence of the proposed algorithm under the condition that $F$ is Fréchet differentiable, which is a relatively weak condition. We also report some preliminary computational results and compare our algorithm with that of Teschke and Borries, which indicate that our method is efficient.
Citation: Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
##### References:
 [1] J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems,, Springer-Verlag, (2000). doi: 10.1007/978-1-4612-1394-9. [2] K. Bredies, D. A. Lorenz and P. Maass, A generalized conditional gradient method and its connection to an iterative shrinkage method,, Comput. Optim. Appl., 42 (2009), 173. doi: 10.1007/s10589-007-9083-3. [3] X. J. Cai, G. Y. Gu and B. S. He, A proximal point algorithm revisit on the alternating direction method of multipliers,, Sci. China Math., 56 (2013), 2179. doi: 10.1007/s11425-013-4683-0. [4] I. Daubechies, M. Defrise and C. DeMol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,, Commun. Pure Appl. Math., 57 (2004), 1413. doi: 10.1002/cpa.20042. [5] I. Daubechies, M. Fornasier and I. Loris, Accelerated projected gradient methods for linear inverse problems with sparsity constraints,, J. Fourier Anal. Appl., 14 (2008), 764. doi: 10.1007/s00041-008-9039-8. [6] I. Daubechies, G. Teschke and L. Vese, Iteratively solving linear inverse problems with general convex constraints,, Inverse Problems Imag., 1 (2007), 29. doi: 10.3934/ipi.2007.1.29. [7] I. Daubechies, G. Teschke and L. Vese, On some iterative concepts for image restoration,, Adv. Imag. Electron Phys., 150 (2008), 1. doi: 10.1016/S1076-5670(07)00001-8. [8] Y. C. Eldar, T. G. Dvorkind and E. Matusiak, Nonlinear and non-ideal sampling: Theory and methods,, IEEE Trans. Signal Process., 56 (2008), 5874. doi: 10.1109/TSP.2008.929872. [9] H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems,, Springer, (1996). doi: 10.1007/978-94-009-1740-8. [10] F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes I and II,, Springer-Verlag, (2003). [11] M. Fornasier, Domain decomposition methods for linear inverse problems with sparsity constraints,, Inverse Problems, 23 (2007), 2505. doi: 10.1088/0266-5611/23/6/014. [12] M. A. T. Figueiredo, R. D. Nowak and S. J. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems,, IEEE J. Sel. Top. Signal Process., 1 (2007), 586. doi: 10.1109/JSTSP.2007.910281. [13] M. Fornasier and H. Rauhut, Recovery algorithms for vector valued data with joint sparsity constraint,, SIAM J. Numer. Anal., 46 (2008), 577. doi: 10.1137/0606668909. [14] Z. L. Ge, G. Qian and D. R. Han, Global convergence of an inexact operator splitting method for monotone variational inequalities,, J. Ind. Man. Optim., 7 (2011), 1013. doi: 10.3934/jimo.2011.7.1013. [15] B. S. He, H. Yang, Q. Meng and D. R. Han, Modified Goldstein-Levitin-Polyak projection method for asymmetric strong monotone variational inequality,, J. Optim. Theory Appl., 112 (2002), 129. doi: 10.1023/A:1013048729944. [16] T. Hein and K. S. Kazimierski, Accelerated Landweber iteration in Banach spaces,, Inverse Problems, 26 (2010). doi: 10.1088/0266-5611/26/5/055002. [17] B. Kaltenbacher, F. Schöpfer and T. Schuster, Iterative methods for nonlinear ill-posed problems in Banach spaces: convergence and applications to parameter identification problems,, Inverse Problems, 25 (2009). doi: 10.1088/0266-5611/25/6/065003. [18] R. Ramlau and G. Teschke, Tikhonov replacement functionals for iteratively solving nonlinear operator equations,, Inverse Problems, 21 (2005), 1571. doi: 10.1088/0266-5611/21/5/005. [19] R. Ramlau and G. Teschke, A Tikhonov-based projection iteration for nonlinear Ill-posed problems with sparsity constraints,, Numer. Math., 104 (2006), 177. doi: 10.1007/s00211-006-0016-3. [20] G. Teschke, Multi-frame representations in linear inverse problems with mixed multi-constraints,, Appl. Comput. Harmon. Anal., 22 (2007), 43. doi: 10.1016/j.acha.2006.05.003. [21] G. Teschke and C. Borries, Accelerated projected steepest descent method for nonlinear inverse problems with sparsity constraints,, Inverse Problems, 26 (2010). doi: 10.1088/0266-5611/26/2/025007. [22] E. van den Berg and M. P. Friedlander, Probing the Pareto frontier for basic pursuit solutions,, SIAM J. Sci. Comput., 31 (2008), 890. doi: 10.1137/080714488. [23] E. Zeidler, Nonlinear Functional Analysis and Its Applications III,, Springer, (1985). doi: 10.1007/978-1-4612-5020-3. [24] E. Zeidler, Nonlinear Functional Analysis and Its Applications I,, Springer, (1986). doi: 10.1007/978-1-4612-4838-5. [25] W. X. Zhang, D. R. Han and Z. B. Li, A self-adaptive projection method for solving the multiple-sets split feasibility problem,, Inverse Problems, 25 (2009). doi: 10.1088/0266-5611/25/11/115001. [26] T. Zhu and Z. Yu, A simple proof for some important properties of the projection mapping,, Mathematical Inequalities and Applications, 7 (2004), 453. doi: 10.7153/mia-07-45.

show all references

##### References:
 [1] J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems,, Springer-Verlag, (2000). doi: 10.1007/978-1-4612-1394-9. [2] K. Bredies, D. A. Lorenz and P. Maass, A generalized conditional gradient method and its connection to an iterative shrinkage method,, Comput. Optim. Appl., 42 (2009), 173. doi: 10.1007/s10589-007-9083-3. [3] X. J. Cai, G. Y. Gu and B. S. He, A proximal point algorithm revisit on the alternating direction method of multipliers,, Sci. China Math., 56 (2013), 2179. doi: 10.1007/s11425-013-4683-0. [4] I. Daubechies, M. Defrise and C. DeMol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,, Commun. Pure Appl. Math., 57 (2004), 1413. doi: 10.1002/cpa.20042. [5] I. Daubechies, M. Fornasier and I. Loris, Accelerated projected gradient methods for linear inverse problems with sparsity constraints,, J. Fourier Anal. Appl., 14 (2008), 764. doi: 10.1007/s00041-008-9039-8. [6] I. Daubechies, G. Teschke and L. Vese, Iteratively solving linear inverse problems with general convex constraints,, Inverse Problems Imag., 1 (2007), 29. doi: 10.3934/ipi.2007.1.29. [7] I. Daubechies, G. Teschke and L. Vese, On some iterative concepts for image restoration,, Adv. Imag. Electron Phys., 150 (2008), 1. doi: 10.1016/S1076-5670(07)00001-8. [8] Y. C. Eldar, T. G. Dvorkind and E. Matusiak, Nonlinear and non-ideal sampling: Theory and methods,, IEEE Trans. Signal Process., 56 (2008), 5874. doi: 10.1109/TSP.2008.929872. [9] H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems,, Springer, (1996). doi: 10.1007/978-94-009-1740-8. [10] F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes I and II,, Springer-Verlag, (2003). [11] M. Fornasier, Domain decomposition methods for linear inverse problems with sparsity constraints,, Inverse Problems, 23 (2007), 2505. doi: 10.1088/0266-5611/23/6/014. [12] M. A. T. Figueiredo, R. D. Nowak and S. J. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems,, IEEE J. Sel. Top. Signal Process., 1 (2007), 586. doi: 10.1109/JSTSP.2007.910281. [13] M. Fornasier and H. Rauhut, Recovery algorithms for vector valued data with joint sparsity constraint,, SIAM J. Numer. Anal., 46 (2008), 577. doi: 10.1137/0606668909. [14] Z. L. Ge, G. Qian and D. R. Han, Global convergence of an inexact operator splitting method for monotone variational inequalities,, J. Ind. Man. Optim., 7 (2011), 1013. doi: 10.3934/jimo.2011.7.1013. [15] B. S. He, H. Yang, Q. Meng and D. R. Han, Modified Goldstein-Levitin-Polyak projection method for asymmetric strong monotone variational inequality,, J. Optim. Theory Appl., 112 (2002), 129. doi: 10.1023/A:1013048729944. [16] T. Hein and K. S. Kazimierski, Accelerated Landweber iteration in Banach spaces,, Inverse Problems, 26 (2010). doi: 10.1088/0266-5611/26/5/055002. [17] B. Kaltenbacher, F. Schöpfer and T. Schuster, Iterative methods for nonlinear ill-posed problems in Banach spaces: convergence and applications to parameter identification problems,, Inverse Problems, 25 (2009). doi: 10.1088/0266-5611/25/6/065003. [18] R. Ramlau and G. Teschke, Tikhonov replacement functionals for iteratively solving nonlinear operator equations,, Inverse Problems, 21 (2005), 1571. doi: 10.1088/0266-5611/21/5/005. [19] R. Ramlau and G. Teschke, A Tikhonov-based projection iteration for nonlinear Ill-posed problems with sparsity constraints,, Numer. Math., 104 (2006), 177. doi: 10.1007/s00211-006-0016-3. [20] G. Teschke, Multi-frame representations in linear inverse problems with mixed multi-constraints,, Appl. Comput. Harmon. Anal., 22 (2007), 43. doi: 10.1016/j.acha.2006.05.003. [21] G. Teschke and C. Borries, Accelerated projected steepest descent method for nonlinear inverse problems with sparsity constraints,, Inverse Problems, 26 (2010). doi: 10.1088/0266-5611/26/2/025007. [22] E. van den Berg and M. P. Friedlander, Probing the Pareto frontier for basic pursuit solutions,, SIAM J. Sci. Comput., 31 (2008), 890. doi: 10.1137/080714488. [23] E. Zeidler, Nonlinear Functional Analysis and Its Applications III,, Springer, (1985). doi: 10.1007/978-1-4612-5020-3. [24] E. Zeidler, Nonlinear Functional Analysis and Its Applications I,, Springer, (1986). doi: 10.1007/978-1-4612-4838-5. [25] W. X. Zhang, D. R. Han and Z. B. Li, A self-adaptive projection method for solving the multiple-sets split feasibility problem,, Inverse Problems, 25 (2009). doi: 10.1088/0266-5611/25/11/115001. [26] T. Zhu and Z. Yu, A simple proof for some important properties of the projection mapping,, Mathematical Inequalities and Applications, 7 (2004), 453. doi: 10.7153/mia-07-45.
 [1] Gang Qian, Deren Han, Lingling Xu, Hai Yang. Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities. Journal of Industrial & Management Optimization, 2013, 9 (1) : 255-274. doi: 10.3934/jimo.2013.9.255 [2] Zhao-Han Sheng, Tingwen Huang, Jian-Guo Du, Qiang Mei, Hui Huang. Study on self-adaptive proportional control method for a class of output models. Discrete & Continuous Dynamical Systems - B, 2009, 11 (2) : 459-477. doi: 10.3934/dcdsb.2009.11.459 [3] Ya-Zheng Dang, Zhong-Hui Xue, Yan Gao, Jun-Xiang Li. Fast self-adaptive regularization iterative algorithm for solving split feasibility problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2019017 [4] Zaki Chbani, Hassan Riahi. Weak and strong convergence of prox-penalization and splitting algorithms for bilevel equilibrium problems. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 353-366. doi: 10.3934/naco.2013.3.353 [5] Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030 [6] Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319 [7] Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023 [8] Alexander Mielke. Weak-convergence methods for Hamiltonian multiscale problems. Discrete & Continuous Dynamical Systems - A, 2008, 20 (1) : 53-79. doi: 10.3934/dcds.2008.20.53 [9] Luchuan Ceng, Qamrul Hasan Ansari, Jen-Chih Yao. Extragradient-projection method for solving constrained convex minimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 341-359. doi: 10.3934/naco.2011.1.341 [10] Chunming Tang, Jinbao Jian, Guoyin Li. A proximal-projection partial bundle method for convex constrained minimax problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 757-774. doi: 10.3934/jimo.2018069 [11] Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial & Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117 [12] Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529 [13] Weijun Zhou, Youhua Zhou. On the strong convergence of a modified Hestenes-Stiefel method for nonconvex optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 893-899. doi: 10.3934/jimo.2013.9.893 [14] Adela Capătă. Optimality conditions for strong vector equilibrium problems under a weak constraint qualification. Journal of Industrial & Management Optimization, 2015, 11 (2) : 563-574. doi: 10.3934/jimo.2015.11.563 [15] Simopekka Vänskä. Stationary waves method for inverse scattering problems. Inverse Problems & Imaging, 2008, 2 (4) : 577-586. doi: 10.3934/ipi.2008.2.577 [16] Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems & Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033 [17] Michael Anderson, Atsushi Katsuda, Yaroslav Kurylev, Matti Lassas and Michael Taylor. Metric tensor estimates, geometric convergence, and inverse boundary problems. Electronic Research Announcements, 2003, 9: 69-79. [18] Davide Guidetti. Convergence to a stationary state of solutions to inverse problems of parabolic type. Discrete & Continuous Dynamical Systems - S, 2013, 6 (3) : 711-722. doi: 10.3934/dcdss.2013.6.711 [19] Daniel Gerth, Andreas Hofinger, Ronny Ramlau. On the lifting of deterministic convergence rates for inverse problems with stochastic noise. Inverse Problems & Imaging, 2017, 11 (4) : 663-687. doi: 10.3934/ipi.2017031 [20] Stanisław Migórski, Biao Zeng. Convergence of solutions to inverse problems for a class of variational-hemivariational inequalities. Discrete & Continuous Dynamical Systems - B, 2018, 23 (10) : 4477-4498. doi: 10.3934/dcdsb.2018172

2018 Impact Factor: 1.469