Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-13T06:45:39.023Z Has data issue: false hasContentIssue false
  • English
  • Français

Large data limit for a phase transition model with the p-Laplacian on point clouds

Part of: Nonparametric inference Existence theories

Published online by Cambridge University Press:  14 November 2018

R. CRISTOFERI  and
M. THORPE
R. CRISTOFERI
Affiliation:
Department of Mathematics, Heriot-Watt University, Edinburgh, Scotland, EH14 4AS, UK e-mail: [email protected]
M. THORPE
Affiliation:
Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, CB3 0WA, UK e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The consistency of a non-local anisotropic Ginzburg–Landau type functional for data classification and clustering is studied. The Ginzburg–Landau objective functional combines a double well potential, that favours indicator valued functions, and the p-Laplacian, that enforces regularity. Under appropriate scaling between the two terms, minimisers exhibit a phase transition on the order of ɛ = ɛn, where n is the number of data points. We study the large data asymptotics, i.e. as n → ∝, in the regime where ɛn → 0. The mathematical tool used to address this question is Γ-convergence. It is proved that the discrete model converges to a weighted anisotropic perimeter.

Keywords

Ginzburg–Landau functionalPDEs on graphsnon-local variational problemsphase transitionsΓ-convergence

MSC classification

Primary: 49J55: Problems involving randomness
Secondary: 49J45: Methods involving semicontinuity and convergence; relaxation 62G20: Asymptotic properties
Type
Papers
Information
European Journal of Applied Mathematics , Volume 31 , Issue 2 , April 2020 , pp. 185 - 231
Copyright
© Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

The research of R. C. was funded by National Science Foundation under Grant No. DMS-1411646. Part of the research of M. T. was funded by the National Science Foundation under Grant No. CCT-1421502.

References

Alberti, G. & Bellettini, G. (1998) A nonlocal anisotropic model for phase transitions: Asymptotic behaviour of rescaled energies. Eur. J. Appl. Math. 9, 261–284.CrossRefGoogle Scholar
Alberti, G. & Bellettini, G. (1998) A nonlocal anisotropic model for phase transitions I. The optimal profile problem. Math. Ann. 310, 527–560.CrossRefGoogle Scholar
Ambrosio, L., Fusco, N. & Pallara, D. (2000) Functions of Bounded Variation and Free Discontinuity Problems. Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York.Google Scholar
Arora, S., Rao, S. & Vazirani, U. (2009) Expander flows, geometric embeddings and graph partitioning. J. ACM 56, Art. 5, 37.CrossRefGoogle Scholar
Baldo, S. (1990) Minimal interface criterion for phase transitions in mixtures of Cahn-Hilliard fluids. Annales de l’Institut Henri Poincaré. Analyse Non Linéaire 7, 67–90.CrossRefGoogle Scholar
Barroso, A. C. & Fonseca, I. (1994) Anisotropic singular perturbations the vectorial case. Proc. R. Soc. Edinburgh Sect. A: Math. 124, 527–571.CrossRefGoogle Scholar
Bertozzi, A. L. & Flenner, A. (2012) Diffuse interface models on graphs for classification of high dimensional data. Multiscale Model. Simul. 10, 1090–1118.CrossRefGoogle Scholar
Bouchitte, G. (1990) Singular perturbations of variational problems arising from a two-phase transition model. Appl. Math. Optim. 21, 289–314.CrossRefGoogle Scholar
Bourgain, J., Brezis, H. & Mironescu, P. (2001) Another look at Sobolev spaces. In: Menaldi, J. L., Rofman, E. and Sulem, A. (editors), Optimal control and partial differential equations. In honour of Professor Alain Bensoussan’s 60th birthday. Proceedings of the conference, Paris, France, December 4, 2000, IOS Press, Amsterdam; Ohmsha, Tokyo, pp. 439–455.Google Scholar
Boykov, Y., Veksler, O. & Zabih, R. (2001) Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23, 1222–1239.CrossRefGoogle Scholar
Braides, A. (2002) Γ-Convergence for Beginners, Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford.CrossRefGoogle Scholar
Braides, A. & Yip, N. K. (2012) A quantitative description of mesh dependence for the discretization of singularly perturbed nonconvex problems. SIAM Journal on Numerical Analysis 50, 1883–1898.CrossRefGoogle Scholar
Bresson, X. & Laurent, T. (2012) Asymmetric Cheeger cut and application to multi-class unsupervised clustering. Technical report UCLA CAM Report 12–27, Los Angeles.Google Scholar
Bresson, X., Laurent, T., Uminsky, D. & von Brecht, J. H. (2012) Convergence and energy landscape for Cheeger cut clustering. In: Proceedings of the 25th International Conference on Neural Information Processing Systems (NIPS), pp. 1385–1393.Google Scholar
Bresson, X., Laurent, T., Uminsky, D. & von Brecht, J. H. (2013) Multiclass total variation clustering. In: Proceedings of the 26th International Conference on Neural Information Processing Systems (NIPS), pp. 1421–1429.Google Scholar
Bresson, X., Tai, X.-C., Chan, T. F. & Szlam, A. (2014) Multi-class transductive learning based on l1 relaxations of Cheeger cut and Mumford-Shah-Potts model. J. Math. Imaging Vis. 49, 191–201.CrossRefGoogle Scholar
Calatroni, L., van Gennip, Y., Schönlieb, , Rowland, H. M. & Flenner, A. (2017) Graph clustering, variational image segmentation methods and Hough transform scale detection for object measurement in images. J. Math. Imaging Vis. 57, 269–291.CrossRefGoogle Scholar
Chambolle, A., Giacomini, A. & Lussardi, L. (2010) Continuous limits of discrete perimeters. M2AN Math. Modell. Numer. Anal. 44, 207–230.CrossRefGoogle Scholar
Dal Maso, G. (1993) An Introduction to Γ-Convergence, Birkhäuser, Basel.CrossRefGoogle Scholar
Davis, E. & Sethuraman, S. (2018) Consistency of modularity clustering on random geometric graphs. Ann. Appl. Probab. 28, 2003–2062.CrossRefGoogle Scholar
De Giorgi, E. & Franzoni, T. (1975) Su un tipo di convergenza variazionale. Atti della Accademia Nazionale dei Lincei. Rendiconti. Classe di Scienze Fisiche, Matematiche e Naturali 58, 842–850.Google Scholar
Dudley, R. M. (2010) Real Analysis and Probability, Cambridge University Press, Cambridge.Google Scholar
Dunlop, M. M., Slepčev, D., Stuart, A. M. & Thorpe, M. (2018) Large data and zero noise limits of graph-based semi-supervised learning algorithms, https://arxiv.org/abs/1805.09450.Google Scholar
Egger, A. & Huotari, R. (1990) Rate of convergence of the discrete pólya algorithm. J. Approx. Theory 60, 24–30.CrossRefGoogle Scholar
Esedoḡlu, S. & Otto, F. (2015) Threshold dynamics for networks with arbitrary surface tensions. Commun. Pure Appl. Math. 68, 808–864.CrossRefGoogle Scholar
Fonseca, I. & Müller, S. (1993) Relaxation of quasiconvex functionals in BV( Ω,Rp) for integrands f(x,u,∇u). Arch. Ration. Mech. Anal. 123, 1–49.CrossRefGoogle Scholar
Fonseca, I. & Popovici, C. (2005) Coupled singular perturbations for phase transitions. Asymptotic Anal. 44, 299–325.Google Scholar
Fonseca, I. & Tartar, L. (1989) The gradient theory of phase transitions for systems with two potential wells. Proc. R. Soc. Edinburgh Sect. A: Math. 111, 89–102.CrossRefGoogle Scholar
Gangbo, W. & McCann, R. J. (1996) The geometry of optimal transportation. Acta Math. 177, 113–161.CrossRefGoogle Scholar
Garcia-Cardona, C., Merkurjev, E., Bertozzi, A. L., Flenner, A. & Percus, A. G. (2014) Multiclass data segmentation using diffuse interface methods on graphs. IEEE Trans. Pattern Anal. Mach. Intell. 36, 1600–1613.CrossRefGoogle ScholarPubMed
García-Trillos, N. (2016) Variational limits of k-NN graph based functionals on data clouds, https://arxiv.org/abs/1607.00696.Google Scholar
García Trillos, N. & Murray, R. (2017) A new analytical approach to consistency and overfitting in regularized empirical risk minimization. Eur. J. Appl. Math. 28, 886–921.CrossRefGoogle Scholar
García Trillos, N. & Slepčev, D. (2015) On the rate of convergence of empirical measures in ∝-transportation distance. Can. J. Math. 67, 1358–1383.CrossRefGoogle Scholar
García Trillos, N. & Slepčev, D. (2016) Continuum limit of total variation on point clouds. Arch. Ration. Mech. Anal. 220, 193–241.CrossRefGoogle Scholar
García Trillos, N. & Slepčev, D. (2018) A variational approach to the consistency of spectral clustering. Appl. Comput. Harmon. Anal. 45, 239–281.CrossRefGoogle Scholar
García Trillos, N., Slepčev, D., von Brecht, J., Laurent, T. & Bresson, X. (2016) Consistency of Cheeger and ratio graph cuts. J. Mach. Learn. Res. 17, 6268–6313.Google Scholar
Kohn, R. & Sternberg, P. (1989) Local minimizers and singular perturbations. Proc. R. Soc. Edinburgh Sect. A: Math. 111, 69–84.CrossRefGoogle Scholar
Kyng, R., Rao, A., Sachdeva, S. & Spielman, D. A. (2015) Algorithms for Lipschitz learning on graphs. In: Proceedings of the 28th Conference on Learning Theory, JMLR: Workshop and Conference Proceedings, Vol. 40:1–34, pp. 1190–1223.Google Scholar
Merkurjev, E., Kostić, T. & Bertozzi, A. L. (2013) An MBO scheme on graphs for classification and image processing. SIAM J. Imaging Sci. 6, 1903–1930.CrossRefGoogle Scholar
Modica, L. (1987) The gradient theory of phase transitions and the minimal interface criterion. Arch. Ration. Mech. Anal. 98, 123–142.CrossRefGoogle Scholar
Modica, L. & Mortola, S. (1977) Un esempio di Γ-convergenza. Bollettino dell’Unione Matematica Italiana B 14, 285–299.Google Scholar
Ng, A. Y., Jordan, M. I. & Weiss, Y. (2001) On spectral clustering: Analysis and an algorithm. In: Proceedings of the 15th International Conference on Neural Information Processing Systems (NIPS), pp. 849–856.Google Scholar
Owen, N. C. & Sternberg, P. (1991) Nonconvex variational problems with anisotropic perturbations. Nonlinear Anal. 16, 705–719.CrossRefGoogle Scholar
Penrose, M. (2003) Random Geometric Graphs. Oxford Studies in Probability, Vol. 5, Oxford University Press, Oxford.CrossRefGoogle Scholar
Ponce, A. C. (2004) A new approach to Sobolev spaces and connections to Γ-convergence. Calculus Var. Partial Differ. Equ. 19, 229–255.CrossRefGoogle Scholar
Savin, O. & Valdinoci, E. (2012) Γ-convergence for nonlocal phase transitions. Annales de l’Institut Henri Poincaré. Analyse Non Linéaire 29, 479–500.CrossRefGoogle Scholar
Shi, J. & Malik, J. (2000) Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22, 888–905.Google Scholar
Slepčev, D. & Thorpe, M. (2017) Analysis of p-Laplacian regularization in semi-supervised learning, https://arxiv.org/abs/1707.06213.Google Scholar
Sternberg, P. (1988) The effect of a singular perturbation on nonconvex variational problems. Arch. Ration. Mech. Anal. 101, 209–260.CrossRefGoogle Scholar
Szlam, A. & Bresson, X. (2009) A total variation-based graph clustering algorithm for cheeger ratio cuts. Technical report UCLA CAM Report 9–68, Los Angeles, pp. 1–12.Google Scholar
Szlam, A. & Bresson, X. (2010) Total variation and Cheeger cuts. In: Proceedings of the 27th International Conference on International Conference on Machine Learning (ICML), Omnipress, USA, pp. 1039–1046.Google Scholar
Thorpe, M., Park, S., Kolouri, S., Rohde, G. K. & Slepčev, D. (2017) A transportation Lp distance for signal analysis. J. Math. Imaging Vis. 59, 187–210.CrossRefGoogle ScholarPubMed
Thorpe, M. & Slepčev, D. (2017, in preparation) Transportation Lp distances: Properties and extensions.Google Scholar
Thorpe, M. & Theil, F. (2017, to appear) Asymptotic analysis of the Ginzburg-Landau functional on point clouds. Proc. R. Soc. Edinburgh Sect. A: Math. https://arxiv.org/abs/1604.04930.Google Scholar
van Gennip, Y. & Bertozzi, A. L. (2012) Γ-convergence of graph Ginzburg-Landau functionals. Adv. Differ. Equ. 17, 1115–1180.Google Scholar
van Gennip, Y. & Schönlieb, C.-B. (2017) Introduction: Big data and partial differential equations. Eur. J. Appl. Math. 28, 877–885.CrossRefGoogle Scholar
Villani, C. (2003) Topics in Optimal Transportation. Graduate Studies in Mathematics, Vol. 58, American Mathematical Society, Providence, RI.Google Scholar