An efficient projection method for nonlinear inverse problems with sparsity constraints

Deren  Han; Zehui  Jia; Yongzhong  Song; David Z. W.  Wang

doi:10.3934/ipi.2016017

Article Contents

2016, Volume 10, Issue 3: 689-709. Doi: 10.3934/ipi.2016017

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

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
2.
School of Civil and Environmental Engineering, Nanyang Technological University, 50 Nanyang Avenue, 639798 Singapore

Received: June 30, 2015

Revised: February 29, 2016

Published: July 2016

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.