American Institute of Mathematical Sciences

Advanced
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

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

Tools

Metrics

  • PDF downloads (195)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy