Article Contents
Article Contents

# Discrete processes and their continuous limits

Supported in part by NSERC Discovery Grant 84306
• The possibility that a discrete process can be fruitfully approximated by a continuous one, with the latter involving a differential system, is fascinating. Important theoretical insights, as well as significant computational efficiency gains may lie in store. A great success story in this regard are the Navier-Stokes equations, which model many phenomena in fluid flow rather well. Recent years saw many attempts to formulate more such continuous limits, and thus harvest theoretical and practical advantages, in diverse areas including mathematical biology, economics, finance, computational optimization, image processing, game theory, and machine learning.

Caution must be applied as well, however. In fact, it is often the case that the given discrete process is richer in possibilities than its continuous differential system limit, and that a further study of the discrete process is practically rewarding. Furthermore, there are situations where the continuous limit process may provide important qualitative, but not quantitative, information about the actual discrete process. This paper considers several case studies of such continuous limits and demonstrates success as well as cause for caution. Consequences are discussed.

Mathematics Subject Classification: Primary: 65K05, 65L04; Secondary: 68U10.

 Citation:

• Figure 1.  Exponential filter $\omega (s) = 1 - e^{-ts}$ and Tikhonov filter $\omega_{\rm T} (s) = \frac {s}{s + \beta}$ for $t\beta = 1/2$

Figure 2.  Gradient descent with step sizes by (26) for the discretized heat equation with $N = 63^2$. The Calculated Step Sizes Are Displayed Vs Iteration Counter $K$. The stability limit for a constant step size gives the straight blue line

Figure 3.  Convergence behaviour of LSD for the model Poisson problem with $n = 63^2$. The errors $\| {\bf r}_k \|$ are displayed as a function of iteration counter $k$

Figure 4.  Convergence behaviour of LSD for the model Poisson problem with $n = 63^2$. The errors $f( {\bf x}_k) - f( {\bf x}^*)$ are displayed as a function of iteration counter $k$

Figure 5.  Convergence behaviour of monotonized LSD (LSDm) as well as SD, conjugate gradient (CG) and Nesterov's (Nes) for the model Poisson problem with $n = 63^2$. The errors $\| {\bf r}_k \|$ are displayed as a function of iteration counter $k$

Figure 6.  Convergence behaviour of monotonized LSD (LSDm) as well as SD, conjugate gradient (CG) and Nesterov's (Nes) for the model Poisson problem with $n = 63^2$. The errors $f( {\bf x}_k) - f( {\bf x}^*)$ are displayed as a function of iteration counter $k$

Table 1.  Maximum time step $h$ for the heat-to-Poisson process as a function of spatial step $\xi$

 $\xi$ $2^{-5}$ $2^{-6}$ $2^{-7}$ $2^{-8}$ $h$ .05 .039 .043 .035
•  [1] H. Akaike, On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method, Ann. Inst. Statist. Math. Tokyo, 11 (1959), 1-16.  doi: 10.1007/BF01831719. [2] U. Ascher, On symmetric schemes and differential-algebraic equations, SIAM J. Sci. Statist. Comput., 10 (1989), 937-949.  doi: 10.1137/0910054. [3] U. Ascher, J. Christiansen and R. D. Russell, Collocation software for boundary-value ODEs, ACM Trans. Math. Software, 7 (1981), 209-222.  doi: 10.1145/355945.355950. [4] U. Ascher and C. Greif, A First Course in Numerical Methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011. doi: 10.1137/1.9780898719987. [5] U. Ascher, E. Haber and H. Huang, On effective methods for implicit piecewise smooth surface recovery, SIAM J. Sci. Comput., 28 (2006), 339-358.  doi: 10.1137/040617261. [6] U. Ascher, H. Huang and K. van den Doel, Artificial time integration, BIT, 47 (2007), 3-25.  doi: 10.1007/s10543-006-0112-x. [7] U. Ascher, R. Mattheij and R. Russell, Numerical Solution of Boundary Value Problems for Ordinary Differential Equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1995. doi: 10.1137/1.9781611971231. [8] U. Ascher and L. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. doi: 10.1137/1.9781611971392. [9] U. Ascher and S. Reich, The midpoint scheme and variants for Hamiltonian systems: Advantages and pitfalls, SIAM J. Sci. Comput., 21 (1999), 1045-1065.  doi: 10.1137/S1064827597316059. [10] U. Ascher and H. Huang, Numerical analysis in visual computing: What we can learn from each other, Vietnam J. Math, 46 (2018) 745-759. doi: 10.1007/s10013-018-0299-6. [11] D. Baraff and A. Witkin, Large steps in cloth simulation, In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, Association for Computing Machinery, New York, New York, 1998, 43-54. doi: 10.1145/280814.280821. [12] C. Barnes, E. Shechtman, A. Finkelstein and D. Goldman, Patchmatch: A randomized correspondence algorithm for structural image editing, ACM Trans. Graph., 27 (2009), Art. 24, 11 pp. doi: 10.1145/1576246.1531330. [13] J. Barzilai and J. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141-148.  doi: 10.1093/imanum/8.1.141. [14] A. Beck, First-Order Methods in Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2017. doi: 10.1137/1.9781611974997.ch1. [15] M. Betancourt, M. Jordan and A. Wilson, On symplectic optimization, preprint, 2018, arXiv: 1802.03653v2. [16] M. Burger, M. Di Francesco, P. A. Markowich and M. T. Wolfram, On a mean field game optimal control approach modeling fast exit scenarios in human crowds, In 52nd IEEE Conference on Decision and Control, Florence, 2013, 3128-3133. doi: 10.1109/CDC.2013.6760360. [17] D. Calvetti and L. Reichel, Lanczos-based exponential filtering for discrete ill-posed problems, Numer. Algorithms, 29 2002, 45-65. doi: 10.1023/A:1014899604567. [18] D. Calvetti, L. Reichel, and Q. Zhang., Iterative exponential filtering for large discrete ill-posed problems., Numer. Math., 83: 535-556, 1999. doi: 10.1007/s002119900077. [19] A. Chambolle and T. Pock, An introduction to continuous optimization for imaging, Acta Numer., 25 (2016), 161-319.  doi: 10.1017/S096249291600009X. [20] T. Chan and J. Shen, Image Processing and Analysis: Variational, PDE, Wavelet and Stochastic Methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. doi: 10.1137/1.9780898717877. [21] D. Chen, D. Levin, L. Matusic and D. Kaufman, Dynamics-aware numerical coarsening for fabrication design, ACM Trans. Graphics, 36 (2017), Art. 84, 15 pp. doi: 10.1145/3072959.3073669. [22] A. J. Chorin, Numerical solution of the Navier-Stokes equations, Math. Comp., 22 (1968), 745-762.  doi: 10.1090/S0025-5718-1968-0242392-2. [23] A. J. Chorin and J. E. Marsden, A Mathematical Introduction to Fluid Mechanics, 3rd edition, Springer-Verlag, New York, 1993. doi: 10.1007/978-1-4612-0883-9. [24] S. Darabi, E. Shechtman, C. Barnes, D. Goldman and P. Sen, Image melding: Combining inconsistent images using patch-based synthesis, ACM Trans. Graph., 31 (2012), Art. 82, 1-82. doi: 10.1145/2185520.2185578. [25] P. Deuflhard, Newton's Method for Nonlinear Problems, Springer-Verlag, Berlin, 2004. [26] J. Diakonikolas and L. Orecchia, The approximate duality gap technique: A unified theory of first-order methods, SIAM J. Optim., 29 (2019), 660-689.  doi: 10.1137/18M1172314. [27] K. van den Doel and U. Ascher, Dynamic level set regularization for large distributed parameter estimation problems, Inverse Problems, 23 (2007), 1271-1288.  doi: 10.1088/0266-5611/23/3/025. [28] K. van den Doel and U. Ascher, The chaotic nature of faster gradient descent methods, J. Sci. Comput., 51 (2011), 560-581.  doi: 10.1007/s10915-011-9521-3. [29] H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Kluwer Academic Publishers Group, Dordrecht, 1996. [30] Z. Farbman, R. Fattal, D. Lischinski and R. Szeliski, Edge-preserving decompositions for multi-scale tone and detail manipulation, in ACM SIGGRAPH 2008 Papers, Association for Computing Machinery, New York, New York, 2008. doi: 10.1145/1399504.1360666. [31] D. A. Gomez and J. Saúde, Mean field games models - A brief survey, Dyn. Games Appl., 4 (2014), 110-154.  doi: 10.1007/s13235-013-0099-2. [32] D. A. Gomez, J. Mohr and R. R. Souza, Continuous time finite state mean field games, Appl. Math. Optim., 68 (2013), 99-143.  doi: 10.1007/s00245-013-9202-8. [33] I. Goodfellow,  Y. Bengio and  A. Courville,  Deep Learning, MIT Press, Cambridge, MA, 2016. [34] A. Greenbaum, Iterative Methods for Solving Linear Systems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. doi: 10.1137/1.9781611970937. [35] E. Hairer, C. Lubich and G. Wanner, Geometric Numerical Integration, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-662-05018-7. [36] E. Hairer and G. Wanner, Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems, 2nd edition, Springer-Verlag, Berlin, 1996. doi: 10.1007/978-3-642-05221-7. [37] H. Huang and U. Ascher, Fast denoising of surface meshes with intrinsic texture, Inverse Problems, 24 (2008), 034003, 18 pp. doi: 10.1088/0266-5611/24/3/034003. [38] H. Huang and U. Ascher, Surface mesh smoothing, regularization, and feature detection, SIAM J. Sci. Comput., 31 (2008), 74-93.  doi: 10.1137/060676684. [39] H. Huang, D. Li, R. Zhang, U. Ascher and D. Cohen-Or, Consolidation of unorganized point clouds for surface reconstruction, ACM Trans. Graph., 28 (2009), 1-7.  doi: 10.1109/TIP.2010.2076297. [40] H. Huang, S. Wu, M. Gong, D. Cohen-Or, U. Ascher and H. Zhang, Edge-aware point set resampling, ACM Trans. Graph., 32 (2013), Art. 9, 12 pp. doi: 10.1145/2421636.2421645. [41] H. Huang, K. Yin, M. Gong, D. Lischinski, D. Cohen-Or, U. M. Ascher, and B. Chen, "Mind the gap": Tele-registration for structure-driven image completion, ACM Trans. Graph., 32 (2013), Art. 174, 10 pp. doi: 10.1145/2508363.2508373. [42] J. Kaipo and E. Somersalo, Statistical and Computational Inverse Problems, Springer-Verlag, New York, 2005. [43] H.-O. Kreiss, Centered difference approximation to singular systems of odes, in Symposia Mathematica X, 1972. [44] J.-M. Lasry and P.-L. Lions, Mean field games, Jpn. J. Math., 2 (2007), 229-260.  doi: 10.1007/s11537-007-0657-8. [45] R. Malhamé, M. Huang and P. Caines, Large population stochastic dynamic games: Closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle, Commun. Inf. Syst., 6 (2006), 221-252.  doi: 10.4310/CIS.2006.v6.n3.a5. [46] M. Markowich, C. Ringhofer and C. Schmeiser, Semi-conductor Equations, Springer-Verlag, Vienna, 1990. doi: 10.1007/978-3-7091-6961-2. [47] Y. Nesterov, A method of solving a convex programming problem with convergence rate $O(1/k^{2})$, Dokl. Akad. Nauk SSSR, 269 (1983), 543-547. [48] Y. Nesterov, Lectures on Convex Optimization, Springer, Cham, 2018. doi: 10.1007/978-3-319-91578-4. [49] J. Nocedal and S. Wright, Numerical Optimization, Springer-Verlag, New York, 1999. doi: 10.1007/b98874. [50] S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Springer-Verlag, New York, 2003. doi: 10.1007/b98879. [51] B. T. Polyak, Some methods of speeding up the convergence of iteration methods, Z. Vycisl. Mat i Mat. Fiz., 4 (1964), 791-803. [52] M. Raydan and B. Svaiter, Relaxed steepest descent and Cauchy-Barzilai-Borwein method, Comput. Optim. Appl., 21 (2002), 155-167.  doi: 10.1023/A:1013708715892. [53] F. Roosta-Khorasani, K. van den Doel and U. Ascher, Stochastic algorithms for inverse problems involving PDEs and many measurements, SIAM J. Sci. Comput., 36 (2014), S3-S22. doi: 10.1137/130922756. [54] L. Ruthotto and E. Haber, Deep neural networks motivated by partial differential equations, J. Math. Imaging Vision, 62 (2019), 352-364.  doi: 10.1007/s10851-019-00903-1. [55] G. Sapiro,  Geometric Partial Differential Equations and Image Analysis, Cambridge University Press, Cambridge, 2001.  doi: 10.1017/CBO9780511626319. [56] W. Su, S. Boyd, and E. Candes, A differential equation for modelling Nesterov's accelerated gradient method, Advances in Neural Information Processing Systems (NIPS), 27 (2014). [57] W. Su, S. Boyd and E. Candes, A differential equation for modelling Nesterov's accelerated gradient method: Theory and insights, J. Mach. Learn. Res., 17 (2016), 1-43. [58] E. Tadmor, S. Nezzar and L. Vese, A multiscale image representation using hierarchical (BV, ${L}^2$) decompositions, Multiscale Model. Simul., 2 (2004), 554-579.  doi: 10.1137/030600448. [59] A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-posed Problems, John Wiley and Sons, Inc., New York-Toronto, Ont.-London, 1977. [60] G. Wanner, Kepler, Newton and numerical analysis, Acta Numer., 19 (2010), 561-598.  doi: 10.1017/S0962492910000073. [61] A. Wibisono, A. Wilson and M. Jordan, A variational perspective on accelerated methods in optimization, Proc. Natl. Acad. Sci. U. S. A., 113 (2016), E7351-E7358. doi: 10.1073/pnas.1614734113. [62] W. I. Zangwill, Nonlinear programming: A unified approach, Prentice-Hall, Inc., Englewood Cliffs, N. J., 1969. [63] J. Zhang, A. Mokhtari, S. Sra and A. Jadbabai, Direct Runge-Kutta discretization achieves acceleration, preprint, 2018, arXiv: 1805.00521.

Figures(6)

Tables(1)