Hostname: page-component-745bb68f8f-hvd4g Total loading time: 0 Render date: 2025-01-27T12:44:16.125Z Has data issue: false hasContentIssue false
  • English
  • Français

On the game p-Laplacian on weighted graphs with applications in image processing and data clustering†

Published online by Cambridge University Press:  03 July 2017

A. ELMOATAZ ,
X. DESQUESNES  and
M. TOUTAIN
A. ELMOATAZ
Affiliation:
Université de Caen Normandie and the ENSICAEN in the GREYC Laboratory, Image Team, 6 Boulevard Maréchal Juin, F-14050 Caen Cedex, France email: [email protected]
X. DESQUESNES
Affiliation:
University of ORLEANS, Orleans, France email: [email protected]
M. TOUTAIN
Affiliation:
Datexim SAS, 51 Avenue de la Côte de Nacre, 14000 Caen Cedex, France email: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Game-theoretic p-Laplacian or normalized p-Laplacian operator is a version of classical variational p-Laplacian which was introduced recently in connection with stochastic games called Tug-of-War with noise (Peres et al. 2008, Tug-of-war with noise: A game-theoretic view of the p-laplacian. Duke Mathematical Journal145(1), 91–120). In this paper, we propose an adaptation and generalization of this operator on weighted graphs for 1 ≤ p ≤ ∞. This adaptation leads to a partial difference operator which is a combination between 1-Laplace, infinity-Laplace and 2-Laplace operators on graphs. Then we consider the Dirichlet problem associated to this operator and we prove the uniqueness and existence of the solution. We show that the solution leads to an iterative non-local average operator on graphs. Finally, we propose to use this operator as a unified framework for interpolation problems in signal processing on graphs, such as image processing and machine learning.

Keywords

Game p-Laplaciangraph signal processingimage processingmachine learningTug-of-War games
Type
Papers
Information
European Journal of Applied Mathematics , Volume 28 , Special Issue 6: Big Data and Partial Differential Equations , December 2017 , pp. 922 - 948
Copyright
Copyright © Cambridge University Press 2017 

Footnotes

†

This work was funded under a doctoral grant supported by the Coeur et Cancer association, the regional council of Normandy, the European FEDER Grant (PLANUCA Project) and the project ANR GRAPHSIP.

References

[1] Alpaydin, E. & Alimoglu, F. (1998) Pen-based recognition of handwritten digits data set. University of California, Irvine, Machine Learning Repository.Google Scholar
[2] Alpaydin, E. & Kaynak, C. (1995) Optical Recognition of Handwritten Digits Data Set. UCI Machine Learning Repository.Google Scholar
[3] Andreu, F., Mazón, J., Rossi, J. & Toledo, J. (2008) A nonlocal p-laplacian evolution equation with neumann boundary conditions. J. Math. pures et Appl. 90 (2), 201–227.Google Scholar
[4] Andreu-Vaillo, F., Mazón, J. M., Rossi, J. D. & Toledo-Melero, J. J. (2010) Nonlocal Diffusion Problems, Mathematical surveys and monographs; Vol. 165, American Mathematical Society.Google Scholar
[5] Arias, P., Facciolo, G., Caselles, V. & Sapiro, G. (2011) A variational framework for exemplar-based image inpainting. Int. J. Comput. Vis. 93 (3), 319–347.CrossRefGoogle Scholar
[6] Barrett, J. W. & Liu, W. (1993) Finite element approximation of the ∞-laplacian. Math. Comput. 61 (204), 523–537.Google Scholar
[7] Bertozzi, A. L. & Flenner, A. (2016) Diffuse interface models on graphs for classification of high dimensional data. SIAM Rev. 58 (2), 293–328.CrossRefGoogle Scholar
[8] Bougleux, S., Elmoataz, A. & Melkemi, M. (2007) Discrete regularization on weighted graphs for image and mesh filtering. In: Sgallari, F., Murli, A. & Paragios, N. (editors), Scale Space and Variational Methods in Computer Vision, Springer, pp. 128–139.Google Scholar
[9] Bougleux, S., Elmoataz, A. & Melkemi, M. (2009) Local and nonlocal discrete regularization on weighted graphs for image and mesh processing. Int. J. Comput. Vis. 84 (2), 220–236.Google Scholar
[10] Bresson, X., Thomas, L., Uminsky, D. & von Brecht, J. H. (2013) Multiclass total variation clustering. In: Bottou, L., Ghahramani, Z. & Weinberger, K. Q. (editors), Advances in Neural Information Processing Systems, Lake Tahoe, Nevada, USA, pp. 1421–1429.Google Scholar
[11] Buades, A., Coll, B. & Morel, J.-M. (2008) Nonlocal image and movie denoising. Int. J. Comput. Vis. 76 (2), 123–139.Google Scholar
[12] Bühler, T. & Hein, M. (2009) Spectral clustering based on the graph p-laplacian. In: Proceedings of the 26th Annual International Conference on Machine Learning, Montreal, Quebec, Canada, ACM, pp. 81–88.CrossRefGoogle Scholar
[13] Chambolle, A., Lindgren, E. & Monneau, R. (2012) A hölder infinity laplacian. ESAIM: Control, Optimisation Calculus Variations 18 (03), 799–835.Google Scholar
[14] Coifman, R. R. & Lafon, S. (2006) Diffusion maps. Appl. Comput. Harmon. Anal. 21 (1), 5–30.Google Scholar
[15] Couprie, C., Grady, L., Najman, L. & Talbot, H. (2011) Power watershed: A unifying graph-based optimization framework. IEEE Trans. Pattern Anal. Mach. Intell. 33 (7), 1384–1399.Google Scholar
[16] Desquesnes, X., Elmoataz, A. & Lézoray, O. (2013) Eikonal equation adaptation on weighted graphs: Fast geometric diffusion process for local and non-local image and data processing. J. Math. Imaging Vis. 46 (2), 238–257.Google Scholar
[17] Drábek, P. (2007) The p-laplacian–mascot of nonlinear analysis. Acta Math. Univ. Comenianae 76 (1), 85–98.Google Scholar
[18] Elmoataz, A., Desquesnes, X., Lakhdari, Z. & Lézoray, O. (2014) Nonlocal infinity laplacian equation on graphs with applications in image processing and machine learning. Math. Comput. Simul. 102, 153–163.Google Scholar
[19] Elmoataz, A., Desquesnes, X. & Lézoray, O. (2012) Non-local morphological pdes and-laplacian equation on graphs with applications in image processing and machine learning. IEEE J. Sel. Topics Signal Process. 6 (7), 764–779.Google Scholar
[20] Elmoataz, A., Lezoray, O. & Bougleux, S. (2008) Nonlocal discrete regularization on weighted graphs: A framework for image and manifold processing. IEEE Trans. Image Process. 17 (7), 1047–1060.Google Scholar
[21] Elmoataz, A., Lézoray, O., Bougleux, S. & Ta, V. T. (2008) Unifying local and nonlocal processing with partial difference operators on weighted graphs. In: Proceedings of the International Workshop Local and Non-Local Approximation in Image Processing, Switzerland, pp. 11–26.Google Scholar
[22] Elmoataz, A., Lozes, F. & Toutain, M. (2016) Nonlocal pdes on graphs: From tug-of-war games to unified interpolation on images and point clouds. J. Math. Imaging Vis. 57 (3), 381–401.Google Scholar
[23] Elmoataz, A., Toutain, M. & Tenbrinck, D. (2015) On the p-laplacian and ∞-laplacian on graphs with applications in image and data processing. SIAM J. Imaging Sci. 8 (4), 2412–2451.Google Scholar
[24] Falcone, M., Vita, S. F., Giorgi, T. & Smits, R. (2013) A semi-lagrangian scheme for the game p-laplacian via p-averaging. Appl. Number. Math. 73, 63–80.Google Scholar
[25] Ghoniem, M., Elmoataz, A. & Lezoray, O. (2011) Discrete infinity harmonic functions: Towards a unified interpolation framework on graphs. In: Proceedings of the 18th IEEE International Conference Image Processing (ICIP), Brussels, Belgium, IEEE, pp. 1361–1364.Google Scholar
[26] Gilboa, G. & Osher, S. (2007) Nonlocal linear image regularization and supervised segmentation. Multiscale Model. Simul. 6 (2), 595–630.Google Scholar
[27] Gilboa, G. & Osher, S. (2008) Nonlocal operators with applications to image processing. Multiscale Model. Simul. 7 (3), 1005–1028.Google Scholar
[28] Hein, M. & Bühler, T. (2010) An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse pca. In: Advances in Neural Information Processing Systems, Curran Associates Inc., pp. 847–855.Google Scholar
[29] Kawohl, B. (2011) Variations on the p-laplacian. In: Bonheure, D., Takac, P. et al. (editors), Nonlinear Elliptic Partial Differential Equations, Contemporary Mathematics, Vol. 540, pp. 35–46.Google Scholar
[30] Kervrann, C. (2004) An adaptive window approach for image smoothing and structures preserving. In: Pajdla, T. and Matas, J. (editors), ECCV, Lecture Notes in Computer Science, Vol. 3023, Prague, Czech Republic, Springer, pp. 132–144.Google Scholar
[31] Keysers, D., Dahmen, J., Theiner, T. & Ney, H. (2000) Experiments with an extended tangent distance. In Pattern Recognition, 2000. Proceedings. 15th International Conference on, Vol. 2, IEEE, pp. 38–42.CrossRefGoogle Scholar
[32] LeCun, Y. & Cortes, C. (2010) MNIST handwritten digit database. URL: http://yann.lecun.com/exdb/mnist/. (last access end 2016).Google Scholar
[33] Manfredi, J. J., Parviainen, M. & Rossi, J. D. (2012) Dynamic programming principle for tug-of-war games with noise. ESAIM: Control, Optimisation Calculus Variations 18 (01), 81–90.Google Scholar
[34] Oberman, A. (2005) A convergent difference scheme for the infinity laplacian: Construction of absolutely minimizing lipschitz extensions. Math. Comput. 74 (251), 1217–1230.Google Scholar
[35] Oberman, A. M. (2013) Finite difference methods for the infinity laplace and p-laplace equations. J. Comput. Appl. Math. 254, 65–80.Google Scholar
[36] Peres, Y., Schramm, O., Sheffield, S. & Wilson, D. (2009) Tug-of-war and the infinity laplacian. J. Am. Math. Soc. 22 (1), 167–210.Google Scholar
[37] Peres, Y. & Sheffield, S. (2008) Tug-of-war with noise: A game-theoretic view of the p-laplacian. Duke Math. J. 145 (1), 91–120.Google Scholar
[38] Rudd, M. (2014) Statistical exponential formulas for homogeneous diffusion. Comm. Pure Appl. Anal. 1, 269–284.Google Scholar
[39] Schönlieb, C.-B. & Bertozzi, A. (2011) Unconditionally stable schemes for higher order inpainting. Commun. Math. Sci. 9 (2), 413–457.Google Scholar
[40] Ta, V.-T., Elmoataz, A. & Lézoray, O. (2011) Nonlocal pdes-based morphology on weighted graphs for image and data processing. IEEE Trans. Image Process. 20 (6), 1504–1516.Google Scholar
[41] Van Gennip, Y., Guillen, N., Osting, B. & Bertozzi, A. L. (2014) Mean curvature, threshold dynamics, and phase field theory on finite graphs. Milan J. Math. 82 (1), 3–65.Google Scholar
[42] Zelnik-manor, L. & Perona, P. (2004) Self-tuning spectral clustering. In: Saul, L. K., Weiss, Y. & Bottou, L. (editors), Advances in Neural Information Processing Systems, Vol. 17, MIT Press, pp. 1601–1608.Google Scholar