Abstract
Many recent algorithmic approaches involve the construction of a differential equation model for computational purposes, typically by introducing an artificial time variable. The actual computational model involves a discretization of the now time-dependent differential system, usually employing forward Euler. The resulting dynamics of such an algorithm is then a discrete dynamics, and it is expected to be “close enough” to the dynamics of the continuous system (which is typically easier to analyze) provided that small – hence many – time steps, or iterations, are taken. Indeed, recent papers in inverse problems and image processing routinely report results requiring thousands of iterations to converge. This makes one wonder if and how the computational modeling process can be improved to better reflect the actual properties sought.
In this article we elaborate on several problem instances that illustrate the above observations. Algorithms may often lend themselves to a dual interpretation, in terms of a simply discretized differential equation with artificial time and in terms of a simple optimization algorithm; such a dual interpretation can be advantageous. We show how a broader computational modeling approach may possibly lead to algorithms with improved efficiency.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Y. I. Alber, Continuous processes of the newton type, Differ. Equations, 7 (1971), pp. 1461–1471.
U. Ascher, DAEs that should not be solved, in IMA Proceedings Dynamics of Algorithms, vol. 118, pp. 55–68, Springer, New York, 1999.
U. Ascher and E. Haber, Computational methods for large distributed parameter estimation problems with possible discontinuities, in Proc. Symp. Inverse Problems, Design & Optimization, M. Colaco, H. Orlande and G. Dulikravich, eds., pp. 201–208, Rio de Janeiro, 2004.
U. Ascher, E. Haber, and H. Huang, On effective methods for implicit piecewise smooth surface recovery, SIAM J. Scient. Comput., 28 (2006), pp. 339–358.
U. Ascher, R. Mattheij, and R. Russell, Numerical Solution of Boundary Value Problems for Ordinary Differential Equations, SIAM, Philadelphia, 1995.
U. Ascher and L. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, SIAM, Philadelphia, PA, 1998.
C. Bajaj and G. Xu, Adaptive surface fairing by geometric diffusion, in Symp. Computer Aided Geometric Design, pp. 731–737, IEEE Computer Society, Washington, D. C.,, 2001.
C. Bajaj and G. Xu, Anisotropic diffusion on surfaces and functions on surfaces, ACM Trans. Graph., 22(1) (2003), pp. 4–32.
D. Barash, A fundamental relationship between bilateral filtering, adaptive smoothing and the nonlinear diffusion equation, IEEE Trans. PAMI, 24 (2002), pp. 844–847.
A. Bhaya and E. Kaszkurewicz, Iterative methods as dynamical systems with feedback control, in 42nd IEEE Conf. on Decision and Control, pp. 2347–2380, IEEE, Hawaii, 2003.
A. Bhaya and E. Kaszkurewicz, Control Perspectives on Numerical Algorithms and Matrix Problems, SIAM, Philadelphia, 2006.
P. Boggs and J. E. Dennis, A stability analysis for perturbed nonlinear analysis methods, Math. Comput., 30 (1976), pp. 199–215.
L. Borcea, J. G. Berryman, and G. C. Papanicolaou, High-contrast impedance tomography, Inverse Probl., 12 (1996), pp. 835–858.
L. Borcea, G. Gray, and Y. Zhang, Variationally constrained numerical solution of electrical impedance tomography, Inverse Probl., 19 (2003), pp. 1159–1184.
A. Brandt, Multigrid techniques: 1984 Guide with applications to fluid Dynamics, The Weizmann Institute of Science, Rehovot, Israel, 1984.
M. Burger, Levenberg–Marquardt level set methods for inverse obstacle problems, Inverse Probl., 20 (2004), pp. 259–282.
M. Burger and S. J. Osher, A survey on level set methods for inverse problems and optimal design, Eur. J. Appl. Math., 16 (2005), pp. 263–301.
D. Calvetti, B. Lewis, and L. Reichel, Smooth or abrupt: a comparison of regularization methods, in Advanced Signal Processing Algorithms, Architectures and Implementations VIII, F. T. Luk, ed., Proceedings of the Society of Photo-Optical Instrumentation Engineers (SPIE), vol. 3461, pp. 286–295, The International Society for Optical Engineering, Bellingham, WA, 1998.
D. Calvetti and L. Reichel, Lanczos-based exponential filtering for discrete ill-posed problems, Numer. Algorithms, 29 (2002), pp. 45–65.
D. Calvetti, L. Reichel, and Q. Zhang, Iterative exponential filtering for large discrete ill-posed problems, Numer. Math., 83 (1999), pp. 535–556.
M. P. Calvo, A. Iserles, and A. Zanna, Numerical solution of isospectral flows, Math. Comput., 66 (1997), pp. 1461–1486.
T. Chan and J. Shen, Image Processing and Analysis: Variational, PDE, Wavelet and Stochastic Methods, SIAM, Philadelphia, 2005.
T. Chan and X. Tai, Level set and total variation regularization for elliptic inverse problems with discontinuous coefficients, J. Comput. Phys., 193 (2003), pp. 40–66.
M. Cheney, D. Isaacson, and J. C. Newell, Electrical impedance tomography, SIAM Rev., 41 (1999), pp. 85–101.
M. T. Chu, On the continuous realization of iterative processes, SIAM Rev., 30 (1988), pp. 375–387.
E. Chung, T. Chan, and X. Tai, Electrical impedance tomography using level set representations and total variation regularization, J. Comput. Phys., 205 (2005), pp. 357–372.
U. Clarenz, U. Diewald, and M. Rumpf, Anisotropic geometric diffusion in surface processing, in Proceedings IEEE Visualization, pp. 397–405, IEEE Computer Society and ACM, Utah, 2000.
U. Clarenz, U. Diewald, and M. Rumpf, Processing textured surfaces via anisotropic geometric diffusion, IEEE Trans. on Image Process., 13(2) (2004), pp. 248–261.
M. Desbrun, M. Meyer, P. Schröder, and A. H. Barr, Anisotropic feature–preserving denoising of height fields and bivariate data, Graphics Interface, pp. 145–152, Canadian Human-Computer Communications Society, Montréal, Québec, 2000.
M. Desbrun, M. Meyer, P. Schroeder, and A. Barr, Implicit fairing of arbitrary meshes using diffusion and curvature flow, ACM SIGGRAPH, Los Angeles, 1999.
A. J. Devaney, The limited-view problem in diffraction tomography, Inverse Probl., 5 (1989), pp. 510–523.
M. P. Do-Carmo, Riemannian Geometry, Birkhäuser, Boston-Basel-Berlin, 1992.
O. Dorn, E. L. Miller, and C. M. Rappaport, A shape reconstruction method for electromagnetic tomography using adjoint fields and level sets, Inverse Probl., 16 (2000), pp. 1119–1156.
R. Ewing (ed.), The Mathematics of Reservoir Simulation, SIAM, Philadelphia, 1983.
H. W. Engl, M. Hanke, and A. Neubauer, Regularization of Inverse Problems, Kluwer, Dordrecht, 1996.
S. Fleishman, I. Drori, and D. Cohen-Or, Bilateral mesh denoising, ACM Trans. Graph., 22(3) (2003), pp. 950–953.
V. Fridman, An iteration process with minimum errors for a nonlinear operator equation, Dokl. Akad. Nauk. SSSR, 139 (1961), pp. 1063–1066.
F. Fruhauf, O. Scherzer, and A. Leitao, Analysis of regularization methods for the solution of ill-posed problems involving unbounded operators and a relation to constraint optimization, SIAM J. Numer. Anal., 43 (2005), pp. 767–786.
M. K. Gavurin, Nonlinear equations and continuous analogs of iterative methods, Izv. Vyssh. Uchebn. Zaved., Mat., 5 (1958), pp. 18–31 (in Russian).
S. Gomez, A. Perez, and R. Alvarez, Multiscale optimization for aquifer parameter identification with noisy data, in Comput. Methods Water Resources XII, vol. 2, pp. 353–360, Computational Mechanics, Southampton, 1998.
E. Haber, A multilevel, level-set method for optimizing eigenvalues in shape design problems, J. Comput. Phys., 198 (2004), pp. 518–534.
E. Haber, U. Ascher, D. Aruliah, and D. Oldenburg, Fast simulation of 3D electromagnetic using potentials, J. Comput. Phys., 163 (2000), pp. 150–171.
E. Haber, U. Ascher, and D. Oldenburg, Inversion of 3D electromagnetic data in frequency and time domain using an inexact all-at-once approach, Geophysics, 69 (2004), pp. 1216–1228.
E. Hairer, C. Lubich, and G. Wanner, Geometric Numerical Integration, Springer, 2002.
F. Hettlich and W. Rundell, Iterative methods for the reconstruction of an inverse potential problem, Inverse Probl., 12 (1996), pp. 251–266.
K. Hildebrandt and K. Polthier, Anisotropic filtering of non-linear surface features, EUROGRAPHICS, 23(3) (2004), pp. 391–400.
M. W. Hirsch and S. Smale, On algorithms for solving f(x)=0, Commun. Pure Appl. Math., 32 (1979), pp. 281–312.
H. Huang and U. Ascher, Fast denoising of surface meshes with intrinsic texture, Preprint, 2006.
T. Jones, F. Durand, and M. Desbrun, Non-iterative, feature preserving mesh smoothing, ACM Trans. Graph., 22(3) (2003), pp. 943–949.
N. Karmarkar, A new polynomial time algorithm for linear programming, Combinatorica, 4 (1984), pp. 373–395.
B. Leimkuhler and S. Reich, Simulating Hamiltonian Dynamics, Cambridge University Press, Cambridge, 2004.
B. Leimkuhler and R. Skeel, Symplectic integrators in constrained Hamiltonian systems, J. Comput. Phys., 112 (1994), pp. 117–125.
A. Leitao and O. Scherzer, On the relation between constraint regularization, level sets, and shape optimization, Inverse Probl., 19 (2003), pp. L1–L11.
A. Marquina and S. Osher, Explicit algorithms for a new time dependent model based on level set motion for nonlinear deblurring and noise removel, SIAM J. Scient. Comput., 22 (2000), pp. 387–405.
S. Maruster, The stability of gradient-like methods, Appl. Math. Comput., 117 (2001), pp. 103–115.
S. Mehrotra, On the implementation of a primal-dual interior point method, SIAM J. Optim., 2 (1992), pp. 575–601.
J. Nagy and K. Palmer, Steepest descent, cg and iterative regularization of ill-posed problems, BIT, 43 (2003), pp. 1003–1017.
G. A. Newman and D. L. Alumbaugh, Three-dimensional magnetotelluric inversion using nonlinear conjugate gradients, Geophys. J. Int., 140 (2000), pp. 410–418.
J. Nocedal and S. Wright, Numerical Optimization, Springer, New York, 1999.
J. M. Ortega and W. C. Rheinboldt, Iterative Solutions of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
S. Osher, M. Burger, D. Goldfarb, J. Xu, and W. Yin, An iterative regularization method for total variation based image restoration, SIAM J. Multiscale Model. Simul., 4 (2005), pp. 460–489.
S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Springer, New York, 2003.
R. L. Parker, Geophysical Inverse Theory, Princeton University Press, Princeton NJ, 1994.
P. Perona and J. Malik, Scale-space and edge detection using anisotropic diffusion, IEEE Trans. Pattern Anal. Machine Intell., 12(7) (1990), pp. 629–639.
L. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), pp. 259–268.
F. Santosa, A level-set approach for inverse problems involving obstacles, ESAIM Control Optim. Calc. Var., 1 (1996), pp. 17–33.
G. Sapiro, Geometric Partial Differential Equations and Image Analysis, Cambridge University Press, Cambridge, 2001.
O. Scherzer, Scale-space methods and regularization for denoising and inverse problems, Adv. Image and Electron Physics, 128 (2003), pp. 445–530.
J. A. Sethian, Level Set Methods and Fast Marching Methods: Evolving Interfaces in Geometry, Fluid Mechanics, Computer Vision, and Material Sciences, Cambridge University Press, Cambridge, 1996.
R. Sincovec and N. Madsen, Software for nonlinear partial differential equations, ACM Trans. Math. Softw., 1 (1975), pp. 232–260.
S. Smale, A convergent process of price adjustment and global Newton methods, J. Math. Econ., 3 (1976), pp. 107–120.
N. C. Smith and K. Vozoff, Two dimensional DC resistivity inversion for dipole-dipole data, IEEE Trans. on Geoscience and Remote Sensing, GE 22 (1984), pp. 21–28.
E. Tadmor, S. Nezzar, and L. Vese, A multiscale image representation using hierarchical ( bv,l 2 ) decompositions, SIAM J. Multiscale Model. Simul., 2 (2004), pp. 554–579.
T. Tasdizen, R. Whitaker, P. Burchard, and S. Osher, Geometric surface smoothing via anisotropic diffusion of normals, in Proceedings IEEE Visualization, pp. 125–132, IEEE Computer Society, Washington, D.C., 2002.
A. N. Tikhonov and V. Y. Arsenin, Methods for Solving Ill-posed Problems, John Wiley and Sons, Inc., Mississauga, Ontario, 1977.
C. Tomasi and R. Manduchi, Bilateral filtering for gray and color images, in IEEE Intl. Conf. Computer Vision, pp. 839–846, IEEE Computer Society, Bombay, India, 1998.
U. Trottenberg, C. Oosterlee, and A. Schuller, Multigrid, Academic Press, Orlando, FL, 2001.
K. van den Doel and U. Ascher, On level set regularization for highly ill-posed distributed parameter estimation problems, J. Comput. Phys., 216 (2006), pp. 707–723.
C. Vogel, Computational methods for inverse problem, SIAM, Philadelphia, 2002.
L. T. Watson, M. Sosonkina, R. C. Melville, A. P. Morgan, and H. F. Walker, Alg 777: HOMPACK90: A suite of FORTRAN 90 codes for globally convergent homotopy algorithms, ACM Trans. Math. Softw., 23 (1997), pp. 514–549.
J. Weickert, Anisotropic Diffusion in Image Processing, B.G Teubner, Stuttgart, 1998.
S. Wright, Primal-Dual Interior Point Methods, SIAM, Philadelphia, PA, 1997.
Author information
Authors and Affiliations
Corresponding author
Additional information
AMS subject classification (2000)
65L05, 65M32, 65N21, 65N22, 65D18
Rights and permissions
About this article
Cite this article
Ascher, U., Huang, H. & van den Doel, K. Artificial time integration . Bit Numer Math 47, 3–25 (2007). https://doi.org/10.1007/s10543-006-0112-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10543-006-0112-x