Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-11T07:08:46.106Z Has data issue: false hasContentIssue false
  • English
  • Français

Estimating perimeter using graph cuts

Part of: Discrete mathematics in relation to computer science Geometric probability and stochastic geometry Nonparametric inference

Published online by Cambridge University Press:  17 November 2017

Nicolás García Trillos ,
Dejan Slepčev  and
James von Brecht
Nicolás García Trillos*
Affiliation:
Brown University
Dejan Slepčev*
Affiliation:
Carnegie Mellon University
James von Brecht*
Affiliation:
California State University, Long Beach
*
* Postal address: Division of Applied Mathematics, Brown University, Providence, RI 02912, USA. Email address: nicolas_garcia_trillos@brown.edu
** Postal address: Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA.
*** Postal address: Department of Mathematics and Statistics, California State University, Long Beach, CA 90840, USA.
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.

We investigate the estimation of the perimeter of a set by a graph cut of a random geometric graph. For Ω ⊆ D = (0, 1)d with d ≥ 2, we are given n random independent and identically distributed points on D whose membership in Ω is known. We consider the sample as a random geometric graph with connection distance ε > 0. We estimate the perimeter of Ω (relative to D) by the, appropriately rescaled, graph cut between the vertices in Ω and the vertices in D ∖ Ω. We obtain bias and variance estimates on the error, which are optimal in scaling with respect to n and ε. We consider two scaling regimes: the dense (when the average degree of the vertices goes to ∞) and the sparse one (when the degree goes to 0). In the dense regime, there is a crossover in the nature of the approximation at dimension d = 5: we show that in low dimensions d = 2, 3, 4 one can obtain confidence intervals for the approximation error, while in higher dimensions one can obtain only error estimates for testing the hypothesis that the perimeter is less than a given number.

Keywords

Perimeternonparametric estimationgraph cutpoint cloudrandom geometric graphconcentration inequality

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry
Secondary: 62G20: Asymptotic properties 68R10: Graph theory (including graph drawing)
Type
Research Article
Information
Advances in Applied Probability , Volume 49 , Issue 4 , December 2017 , pp. 1067 - 1090
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Alberti, G. and Bellettini, G. (1998). A non-local anisotropic model for phase transitions: asymptotic behaviour of rescaled energies. Europ. J. Appl. Math. 9, 261–284. Google Scholar
[2] Ambrosio, L., Fusco, N. and Pallara, D. (2000). Functions of Bounded Variation and Free Discontinuity Problems. Oxford University Press. Google Scholar
[3] Arias-Castro, E., Pelletier, B. and Pudlo, P. (2012). The normalized graph cut and Cheeger constant: from discrete to continuous. Adv. Appl. Prob. 44, 907–937. Google Scholar
[4] Armendáriz, I., Cuevas, A. and Fraiman, R. (2009). Nonparametric estimation of boundary measures and related functionals: asymptotic results. Adv. Appl. Prob. 41, 311–322. Google Scholar
[5] Belkin, M., Narayanan, H. and Niyogi, P. (2006). Heat flow and a faster algorithm to compute the surface area of a convex body. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), IEEE, New York, pp. 47–56. Google Scholar
[6] Bernstein, S. (1924). On a modification of Chebyshev's inequality and of the error formula of Laplace. Ann. Sci. Inst. Sav. Ukraine Sect. Math. 1, 38–49 (in Russian). Google Scholar
[7] Bresson, X., Laurent, T., Uminsky, D. and von Brecht, J. H. (2012). Convergence and energy landscape for Cheeger cut clustering. In Advances in Neural Information Processing Systems (NIPS), pp. 1394–1402. Google Scholar
[8] Cuevas, A., Fraiman, R. and Györfi, L. (2013). Towards a universally consistent estimator of the Minkowski content. ESAIM Prob. Statist. 17, 359–369. Google Scholar
[9] Cuevas, A., Fraiman, R. and Rodríguez-Casal, A. (2007). A nonparametric approach to the estimation of lengths and surface areas. Ann. Statist. 35, 1031–1051. CrossRefGoogle Scholar
[10] García Trillos, N. and Slepčev, D. (2016). Continuum limit of total variation on point clouds. Arch. Rational Mech. Anal. 220, 193–241. Google Scholar
[11] García Trillos, N. et al. (2016). Consistency of Cheeger and ratio graph cuts. J. Machine Learning Res. 17, 181. Google Scholar
[12] Giné, E., Latała, R. and Zinn, J. (2000). Exponential and moment inequalities for U-statistics. In High Dimensional Probability, II, (Seattle, WA, 1999; Progr. Prob. 47), Birkhäuser, Boston, MA, pp. 13–38. Google Scholar
[13] Gray, A. (2004). Tubes, 2nd edn. Birkhäuser, Basel. Google Scholar
[14] Hagen, L. and Kahng, A. B. (1992). New spectral methods for ratio cut partitioning and clustering. IEEE Trans. Comput. Aided Design 11, 1074–1085. Google Scholar
[15] Hein, M. and Setzer, S. (2011). Beyond spectral clustering – tight relaxations of balanced graph cuts. In Advances in Neural Information Processing Systems (NIPS), pp. 2366–2374. Google Scholar
[16] Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58, 13–30. Google Scholar
[17] Jiménez, R. and Yukich, J. E. (2011). Nonparametric estimation of surface integrals. Ann. Statist. 39, 232–260. Google Scholar
[18] Kannan, R., Vempala, S. and Vetta, A. (2004). On clusterings: good, bad and spectral. J. ACM 51, 497–515. Google Scholar
[19] Kearns, M. and Ron, D. (2000). Testing problems with sublearning sample complexity. J. Comput. System Sci. 61, 428–456. CrossRefGoogle Scholar
[20] Koroljuk, V. S. and Borovskich, Y. V. (1994). Theory of U-Statistics (Math. Appl. 273). Kluwer, Dordrecht. Google Scholar
[21] Kothari, P., Nayyeri, A., O'Donnell, R. and Wu, C. (2014). Testing surface area. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, pp. 1204–1214. Google Scholar
[22] Leoni, G. (2009). A First Course in Sobolev Spaces (Graduate Studies Math. 105). American Mathematical Society, Providence, RI. Google Scholar
[23] Neeman, J. (2014). Testing surface area with arbitrary accuracy. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, New York, pp. 393–397. Google Scholar
[24] Pateiro-López, B. and Rodríguez-Casal, A. (2008). Length and surface area estimation under smoothness restrictions. Adv. Appl. Prob. 40, 348–358. Google Scholar
[25] Shi, J. and Malik, J. (1997). Normalized cuts and image segmentation. In Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, IEEE, New York, pp. 731–737. Google Scholar
[26] Szlam, A. and Bresson, X. (2010). Total variation and Cheeger cuts. In ICML'10, ACM, New York, pp. 1039–1046. Google Scholar
[27] Von Luxburg, U. (2007). A tutorial on spectral clustering. Statist. Comput. 17, 395–416. Google Scholar
[28] Wei, Y.-C. and Cheng, C.-K. (1989). Towards efficient hierarchical designs by ratio cut partitioning. In 1989 IEEE International Conference on Computer-Aided Design, IEEE, New York, pp. 298–301. Google Scholar