An efficient projection method for nonlinear inverse problems with sparsity constraints

Previous Article
Local inverse scattering at fixed energy in spherically symmetric asymptotically hyperbolic manifolds
IPI Home
This Issue
Next Article
Reconstructing a function on the sphere from its means along vertical slices

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

An efficient projection method for nonlinear inverse problems with sparsity constraints

Deren Han ^1, , Zehui Jia ^1, , Yongzhong Song ^1, and David Z. W. Wang ^2,

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

Abstract
Related Papers

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.

Keywords: weak and strong convergence., sparsity, self-adaptive, nonlinear inverse problems, Projection method.

Mathematics Subject Classification: Primary: 90C33, 94A08, 97M5.

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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[9]	H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems,, Springer, (1996). doi: 10.1007/978-94-009-1740-8. Google Scholar
[10]	F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes I and II,, Springer-Verlag, (2003). Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[23]	E. Zeidler, Nonlinear Functional Analysis and Its Applications III,, Springer, (1985). doi: 10.1007/978-1-4612-5020-3. Google Scholar
[24]	E. Zeidler, Nonlinear Functional Analysis and Its Applications I,, Springer, (1986). doi: 10.1007/978-1-4612-4838-5. Google Scholar
[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. Google Scholar
[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. Google Scholar

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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[9]	H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems,, Springer, (1996). doi: 10.1007/978-94-009-1740-8. Google Scholar
[10]	F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes I and II,, Springer-Verlag, (2003). Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[23]	E. Zeidler, Nonlinear Functional Analysis and Its Applications III,, Springer, (1985). doi: 10.1007/978-1-4612-5020-3. Google Scholar
[24]	E. Zeidler, Nonlinear Functional Analysis and Its Applications I,, Springer, (1986). doi: 10.1007/978-1-4612-4838-5. Google Scholar
[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. Google Scholar
[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. Google Scholar

[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

American Institute of Mathematical Sciences