# 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 and 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, New York, 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-193. 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-2186. 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-1457. 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-792. 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-46. 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-51. 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-5890. doi: 10.1109/TSP.2008.929872. [9] H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Springer, Netherlands, 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, Berlin, 2003. [11] M. Fornasier, Domain decomposition methods for linear inverse problems with sparsity constraints, Inverse Problems, 23 (2007), 2505-2526. 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-597. 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-613. 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-1026. 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-143. doi: 10.1023/A:1013048729944. [16] T. Hein and K. S. Kazimierski, Accelerated Landweber iteration in Banach spaces, Inverse Problems, 26 (2010), 055002 (17pp). 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), 065003 (19pp). 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-1592. 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-203. 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-60. 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), 025007 (23pp). 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-912. doi: 10.1137/080714488. [23] E. Zeidler, Nonlinear Functional Analysis and Its Applications III, Springer, New York, 1985. doi: 10.1007/978-1-4612-5020-3. [24] E. Zeidler, Nonlinear Functional Analysis and Its Applications I, Springer, New York, 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), 115001 (16pp). 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-456. doi: 10.7153/mia-07-45.

show all references

##### References:
 [1] J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer-Verlag, New York, 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-193. 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-2186. 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-1457. 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-792. 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-46. 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-51. 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-5890. doi: 10.1109/TSP.2008.929872. [9] H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Springer, Netherlands, 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, Berlin, 2003. [11] M. Fornasier, Domain decomposition methods for linear inverse problems with sparsity constraints, Inverse Problems, 23 (2007), 2505-2526. 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-597. 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-613. 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-1026. 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-143. doi: 10.1023/A:1013048729944. [16] T. Hein and K. S. Kazimierski, Accelerated Landweber iteration in Banach spaces, Inverse Problems, 26 (2010), 055002 (17pp). 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), 065003 (19pp). 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-1592. 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-203. 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-60. 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), 025007 (23pp). 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-912. doi: 10.1137/080714488. [23] E. Zeidler, Nonlinear Functional Analysis and Its Applications III, Springer, New York, 1985. doi: 10.1007/978-1-4612-5020-3. [24] E. Zeidler, Nonlinear Functional Analysis and Its Applications I, Springer, New York, 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), 115001 (16pp). 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-456. 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 and 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 and Continuous Dynamical Systems - B, 2009, 11 (2) : 459-477. doi: 10.3934/dcdsb.2009.11.459 [3] Hatim Tayeq, Amal Bergam, Anouar El Harrak, Kenza Khomsi. Self-adaptive algorithm based on a posteriori analysis of the error applied to air quality forecasting using the finite volume method. Discrete and Continuous Dynamical Systems - S, 2021, 14 (7) : 2557-2570. doi: 10.3934/dcdss.2020400 [4] Yuan Shen, Chang Liu, Yannian Zuo, Xingying Zhang. A modified self-adaptive dual ascent method with relaxed stepsize condition for linearly constrained quadratic convex optimization. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022101 [5] 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 and Management Optimization, 2020, 16 (4) : 1555-1569. doi: 10.3934/jimo.2019017 [6] Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $L^2-$norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077 [7] Zaki Chbani, Hassan Riahi. Weak and strong convergence of prox-penalization and splitting algorithms for bilevel equilibrium problems. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 353-366. doi: 10.3934/naco.2013.3.353 [8] Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030 [9] Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319 [10] Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control and Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023 [11] Xueling Zhou, Meixia Li, Haitao Che. Relaxed successive projection algorithm with strong convergence for the multiple-sets split equality problem. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2557-2572. doi: 10.3934/jimo.2020082 [12] Alexander Mielke. Weak-convergence methods for Hamiltonian multiscale problems. Discrete and Continuous Dynamical Systems, 2008, 20 (1) : 53-79. doi: 10.3934/dcds.2008.20.53 [13] Chunming Tang, Jinbao Jian, Guoyin Li. A proximal-projection partial bundle method for convex constrained minimax problems. Journal of Industrial and Management Optimization, 2019, 15 (2) : 757-774. doi: 10.3934/jimo.2018069 [14] Luchuan Ceng, Qamrul Hasan Ansari, Jen-Chih Yao. Extragradient-projection method for solving constrained convex minimization problems. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 341-359. doi: 10.3934/naco.2011.1.341 [15] Janosch Rieger. A learning-enhanced projection method for solving convex feasibility problems. Discrete and Continuous Dynamical Systems - B, 2022, 27 (1) : 555-568. doi: 10.3934/dcdsb.2021054 [16] Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial and Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117 [17] Abdulkarim Hassan Ibrahim, Poom Kumam, Min Sun, Parin Chaipunya, Auwal Bala Abubakar. Projection method with inertial step for nonlinear equations: Application to signal recovery. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021173 [18] Alexey Penenko. Convergence analysis of the adjoint ensemble method in inverse source problems for advection-diffusion-reaction models with image-type measurements. Inverse Problems and Imaging, 2020, 14 (5) : 757-782. doi: 10.3934/ipi.2020035 [19] Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial and Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529 [20] Weijun Zhou, Youhua Zhou. On the strong convergence of a modified Hestenes-Stiefel method for nonconvex optimization. Journal of Industrial and Management Optimization, 2013, 9 (4) : 893-899. doi: 10.3934/jimo.2013.9.893

2021 Impact Factor: 1.483