Continuum limits of nonlocal \(p\)-Laplacian variational problems on graphs. (English) Zbl 1447.65056
The authors study numerical approximations of the nonlocal variational problem consisting of minimizing in \(L_2\) the sum of quadratic data fidelity and a regularization term corresponding to the \(L_p\)-norm of the nonlocal gradient. Discrete versions of continuum models based on nonlocal regularization are used frequently in the signal, image, data processing, machine learning, and computer vision. General error estimates in the \(L_2\) norm are given for the error between the continuum extension of the numerical solution to the discrete variational problem and its continuum analogue. Convergence rates are obtained under very mild conditions on the kernel and the initial data.
These results are applied, using the theory graph limits, to dynamical networks on simple and weighted dense graphs, showing that the minimizers of the sequence of discrete problems converge to that of the continuum problem. The authors also study networks on random inhomogeneous graphs, building upon the error estimates. The variational regularization problem is applied to point cloud denoising and to signal denoising problems and the error bounds are illustrated numerically.
These results are applied, using the theory graph limits, to dynamical networks on simple and weighted dense graphs, showing that the minimizers of the sequence of discrete problems converge to that of the continuum problem. The authors also study networks on random inhomogeneous graphs, building upon the error estimates. The variational regularization problem is applied to point cloud denoising and to signal denoising problems and the error bounds are illustrated numerically.
Reviewer: Bülent Karasözen (Ankara)
MSC:
| 65M12 | Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs |
| 65M15 | Error bounds for initial value and initial-boundary value problems involving PDEs |
| 41A17 | Inequalities in approximation (Bernstein, Jackson, Nikol’skiĭ-type inequalities) |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C90 | Applications of graph theory |
| 49M25 | Discrete approximations in optimal control |
| 65K15 | Numerical methods for variational inequalities and related problems |
| 35A15 | Variational methods applied to PDEs |
| 35Q35 | PDEs in connection with fluid mechanics |
| 35K20 | Initial-boundary value problems for second-order parabolic equations |
| 35R02 | PDEs on graphs and networks (ramified or polygonal spaces) |
| 35R09 | Integro-partial differential equations |
Keywords:
variational problems; nonlocal \(p\)-Laplacian; discrete solutions; error bounds; graph limitsReferences:
| [1] | F. Andreu-Vaillo, J. M. Mazón, J. D. Rossi, and J. J. Toledo-Melero, Nonlocal Diffusion Problems, Math. Surveys Monogr. 165, AMS, Providence, RI, 2010. · Zbl 1214.45002 |
| [2] | H. Attouch and J. Peypouquet, The rate of convergence of Nesterov’s accelerated forward-backward method is actually \(o(k^{-2})\), SIAM J. Optim., 26 (2016), pp. 1824-1834. · Zbl 1346.49048 |
| [3] | H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, New York, 2011. · Zbl 1218.47001 |
| [4] | A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183-202. · Zbl 1175.94009 |
| [5] | S. J. Béla Bollobás and O. Reordan, The Phase Transition in Inhomogeneous Random Graphs, , 2006. |
| [6] | M. Belkin and P. Niyogi, Convergence of Laplacian eigenmaps, in Advances in Neural Information Processing Systems, MIT Press, Cambridge, MA, 2007, pp. 129-136. |
| [7] | A. L. Bertozzi and A. Flenner, Diffuse interface models on graphs for analysis of high dimensional data, SIAM J. Multiscale Model. Simul., 10 (2012), pp. 1090-1118. · Zbl 1259.68215 |
| [8] | B. Bollobás and O. Riordan, Metrics for Sparse Graphs, , 2009. · Zbl 1182.05106 |
| [9] | C. Borgs, J. Chayes, L. Lovász, V. Sós, and K. Vesztergombi, Limits of randomly grown graph sequences, European J. Combin., 32 (2011), pp. 985-999, http://dx.doi.org/10.1016/j.ejc.2011.03.015. · Zbl 1229.05247 |
| [10] | C. Borgs, J. Chayes, L. Lovász, V. Sós, and K. Vesztergombi, Limits of randomly grown graph sequences, European J. Combin., 32 (2011), pp. 985-999, https://doi.org/10.1016/j.ejc.2011.03.015. · Zbl 1229.05247 |
| [11] | A. Buades, B. Coll, J. M. Morel, and C. Sbert, Non local demosaicing, 2007. |
| [12] | A. Buades, B. Coll, and J. M. Morel, On image denoising methods, SIAM Multiscale Model. Simul., 4 (2005), pp. 490-530. · Zbl 1108.94004 |
| [13] | T. Bühler and M. Hein, Spectral clustering based on the graph \(p\)-Laplacian, in Proceedings of the 26th Annual International Conference on Machine Learning, 2009, pp. 81-88. |
| [14] | J. Calder, Consistency of Lipschitz Learning with Infinite Unlabeled Data and Finite Labeled Data, , 2017. |
| [15] | A. Chambolle and C. Dossal, On the convergence of the iterates of the “fast iterative shrinkage/thresholding algorithm,” J. Optim. Theory Appl., 166 (2015), pp. 968-982. · Zbl 1371.65047 |
| [16] | R. R. Coifman and S. Lafon, Diffusion maps, Appl. Comput. Harmon. Anal, 21 (2006), pp. 5-30. · Zbl 1095.68094 |
| [17] | R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker, Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps, Proc. Nat. Acad. Sci., 102 (2005), pp. 7426-7431. · Zbl 1405.42043 |
| [18] | R. A. DeVore and G. G. Lorentz, Constructive Approximation, Grundlehren Math. Wiss. 303, Springer-Verlag, Berlin, 1993. · Zbl 0797.41016 |
| [19] | A. El Alaoui, X. Cheng, A. Ramdas, M. J. Wainwright, and M. I. Jordan, Asymptotic behavior of \(\ell_p\)-based laplacian regularization in semi-supervised learning, in Proceedings of the 29th Annual Conference on Learning Theory, 2016, pp. 879-906. |
| [20] | A. Elmoataz, O. Lezoray, and S. Bougleux, Nonlocal discrete regularization on weighted graphs: A framework for image and manifold processing, IEEE Trans. Image Process., 17 (2008). · Zbl 1143.94308 |
| [21] | A. Elmoataz, M. Toutain, and D. Tenbrinck, On the \(p\)-Laplacian and \(\infty \)-Laplacian on graphs with applications in image and data processing, SIAM J. Imaging Sci., 8 (2015), pp. 2412-2451, https://doi.org/10.1137/15M1022793. · Zbl 1330.35488 |
| [22] | G. Facciolo, P. Arias, V. Caselles, and G. Sapiro, Exemplar-based interpolation of sparsely sampled images, in Energy Minimization Methods in Computer Vision and Pattern Recognition, D. Cremers, Y. Boykov, A. Blake, and F. R. Schmidt, eds., Springer, Berlin, 2009, pp. 331-344. |
| [23] | M. J. Fadili and G. Peyré, Total variation projection with first order schemes, IEEE Trans. Image Process., 20 (2010), pp. 657-669. · Zbl 1372.94077 |
| [24] | K. J. Falconer, Fractal geometry: Mathematical foundations and applications, John Wiley & Sons, New York, 1990, http://opac.inria.fr/record=b1087702. · Zbl 0689.28003 |
| [25] | N. García Trillos and D. Slepčev, Continuum limit of total variation on point clouds, Arch. Ration. Mech. Anal., 220 (2016), pp. 193-241. · Zbl 1336.68215 |
| [26] | Y. V. Gennip and A. L. Bertozzi, Gamma-convergence of graph ginzburg-landau functionals, Adv. in Differential Equations, 17 (2012), pp. 1115-1180. · Zbl 1388.35200 |
| [27] | G. Gilboa and S. Osher, Nonlocal linear image regularization and supervised segmentation, SIAM J. Multiscale Model. Simul., 6 (2007), pp. 595-630. · Zbl 1140.68517 |
| [28] | G. Gilboa and S. Osher, Nonlocal operators with applications to image processing, SIAM J. Multiscale Model. Simul., 7 (2008), pp. 1005-1028. · Zbl 1181.35006 |
| [29] | Y. Hafiene, J. Fadili, C. Chesneau, and A. Elmoataz, Continuum Limit of the Nonlocal \(p\)-Laplacian Evolution Problem on Random Inhomogeneous Graphs, , 2018. · Zbl 1448.65200 |
| [30] | Y. Hafiene, J. Fadili, and A. Elmoataz, Nonlocal \(p\)-laplacian evolution problems on graphs, SIAM J. Numer. Anal., 56 (2018), pp. 1064-1090, https://doi.org/10.1137/17M1123596. · Zbl 1448.65200 |
| [31] | M. Hein, Uniform convergence of adaptive graph-based regularization, in Proceedings of the international Conference on Computational Learning Theory, 2006, pp. 50-64. · Zbl 1143.68416 |
| [32] | M. Hein, J.-Y. Audibert, and U. von Luxburg, From graphs to manifolds–weak and strong pointwise consistency of graph laplacians, in Proceedings of the 18th Annual Conference on Learning Theory, Springer, New York, 2005, pp. 470-485. · Zbl 1095.68097 |
| [33] | N. Kusolitsch, Why the theorem of Scheffé should be rather called a theorem of Riesz, Period. Math. Hungar., 61 (2010), pp. 225-229, https://doi.org/10.1007/s10998-010-3225-6. · Zbl 1240.01018 |
| [34] | L. Lovász and B. Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B, 96 (2006), pp. 933-957. · Zbl 1113.05092 |
| [35] | L. Lovász and B. Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B, 96 (2006), pp. 933 – 957. · Zbl 1113.05092 |
| [36] | U. V. Luxburg, A tutorial on spectral clustering, Statist. Comput., 17 (2007), pp. 395-416. |
| [37] | G. S. Medvedev, The nonlinear heat equation on dense graphs, SIAM J. Math. Anal., 46 (2014), pp. 2743-2766, https://doi.org/10.1007/s00205-013-0706-9. · Zbl 1307.34062 |
| [38] | Y. Nesterov, A method for solving the convex programming problem with convergence rate \(O(1/k^2)\), Dokl. Akad. Nauk SSSR, 269 (1983), pp. 543-547. |
| [39] | E. Pardoux, Cours intégration et probabilité, Lecture notes, Aix-Marseille Universtité, 2009. |
| [40] | G. Peyré, Image processing with nonlocal spectral bases, SIAM J. Multiscale Model. Simul., 7 (2008), pp. 703-730. · Zbl 1177.41016 |
| [41] | G. Peyré, S. Bougleux, and L. Cohen, Non-local regularization of inverse problems, Inverse Problems Imaging, 5 (2011), p. 511. · Zbl 1223.68116 |
| [42] | O. Scherzer, M. Grasmair, H. Grossauer, M. Haltmeier, and F. Lenzen, Variational Methods in Imaging, Appl. Math. Sci. 167, Springer, New York, 2009. · Zbl 1177.68245 |
| [43] | A. Singer, From graph to manifold laplacian: The convergence rate, Appl. Comput. Harmon. Anal., 21 (2006), pp. 128-134. · Zbl 1095.68102 |
| [44] | A. Singer and H.-T. Wu, Spectral convergence of the connection laplacian from random samples, Inform. Inference, 6 (2017), pp. 58-123. · Zbl 1386.94055 |
| [45] | D. Slepčev and M. Thorpe, Analysis of \(p\)-laplacian regularization in semi-supervised learning, SIAM J. Math. Anal., 51 (2019), pp. 2085-2120. · Zbl 1422.49020 |
| [46] | S. M. Smith and J. M. Brady, SUSAN–a new approach to low level image processing, Int. J. Comput. Vis., 23 (1997), pp. 45-78, https://doi.org/10.1023/A:1007963824710. |
| [47] | A. Spira, R. Kimmel, and N. Sochen, A short-time Beltrami kernel for smoothing images and manifolds, IEEE Trans. Image Process., 16 (2007), pp. 1628-1636, https://doi.org/10.1109/TIP.2007.894253. |
| [48] | S. O. Stefan Kindermann and P. W. Jones, Deblurring and denoising of images by nonlocal functionals, SIAM Multiscale Model. Simul., 4 (2005), pp. 1091-1115. · Zbl 1161.68827 |
| [49] | A. Szlam, M. Maggioni, and R. Coifman, A general framework for adaptive regularization based on diffusion processes on graphs, J. Mach. Learn. Res., 19 (2008), pp. 1711-1739. · Zbl 1225.68217 |
| [50] | D. Ting, L. Huang, and M. I. Jordan, An analysis of the convergence of graph laplacians, in Proceedings of the 27th International Conference on Machine Learning, 2010. |
| [51] | C. Tomasi and R. Manduchi, Bilateral filtering for gray and color images, in Sixth International Conference on Computer Vision, IEEE, 1998, pp. 839-846, https://doi.org/10.1109/ICCV.1998.710815. |
| [52] | S. Vaiter, G. Peyré, and M. J. Fadili, Low complexity regularization of linear inverse problems, in Sampling Theory, a Renaissance, G. Pfander, ed., Appl. Numer. Harmon. Anal., Birkhäuser, Basel, 2015, pp. 103-153. · Zbl 1358.94016 |
| [53] | U. von Luxburg, M. Belkin, and O. Bousquet, Consistency of spectral clustering, Ann. Statist., 36 (2008), pp. 555-586. · Zbl 1133.62045 |
| [54] | J. Wang and B. J. Lucier, Error bounds for finite-difference methods for Rudin-Osher-Fatemi image smoothing, SIAM J. Numer. Anal., 49 (2011), pp. 845-868. · Zbl 1339.94013 |
| [55] | Z. Yang and M. Jacob, Nonlocal regularization of inverse problems: A unified variational framework, IEEE Trans. Image Process., 22 (2013), pp. 3192-3203. |
| [56] | L. P. Yaroslavsky, Digital Picture Processing–an Introduction, Springer-Verlag, Berlin, 1985. · Zbl 0585.94001 |
| [57] | D. Zhou and B. Schölkopf, Regularization on discrete spaces, in Proceedings of the 27th DAGM Conference on Pattern Recognition, Springer-Verlag, Berlin, 2005, pp. 361-368. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
