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

American Institute of Mathematical Sciences