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

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

[2]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380

[3]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101

[4]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012

[5]

Xiu Ye, Shangyou Zhang, Peng Zhu. A weak Galerkin finite element method for nonlinear conservation laws. Electronic Research Archive, 2021, 29 (1) : 1897-1923. doi: 10.3934/era.2020097

[6]

José Luiz Boldrini, Jonathan Bravo-Olivares, Eduardo Notte-Cuello, Marko A. Rojas-Medar. Asymptotic behavior of weak and strong solutions of the magnetohydrodynamic equations. Electronic Research Archive, 2021, 29 (1) : 1783-1801. doi: 10.3934/era.2020091

[7]

Lateef Olakunle Jolaoso, Maggie Aphane. Bregman subgradient extragradient method with monotone self-adjustment stepsize for solving pseudo-monotone variational inequalities and fixed point problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020178

[8]

Philipp Harms. Strong convergence rates for markovian representations of fractional processes. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020367

[9]

Martin Kalousek, Joshua Kortum, Anja Schlömerkemper. Mathematical analysis of weak and strong solutions to an evolutionary model for magnetoviscoelasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 17-39. doi: 10.3934/dcdss.2020331

[10]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[11]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[12]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136

[13]

Eduard Feireisl, Elisabetta Rocca, Giulio Schimperna, Arghir Zarnescu. Weak sequential stability for a nonlinear model of nematic electrolytes. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 219-241. doi: 10.3934/dcdss.2020366

[14]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105

[15]

Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021006

[16]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 61-79. doi: 10.3934/dcdsb.2020351

[17]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[18]

Yi-Hsuan Lin, Gen Nakamura, Roland Potthast, Haibing Wang. Duality between range and no-response tests and its application for inverse problems. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020072

[19]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074

[20]

Xinlin Cao, Huaian Diao, Jinhong Li. Some recent progress on inverse scattering problems within general polyhedral geometry. Electronic Research Archive, 2021, 29 (1) : 1753-1782. doi: 10.3934/era.2020090

2019 Impact Factor: 1.373

Metrics

  • PDF downloads (61)
  • HTML views (0)
  • Cited by (0)

[Back to Top]