Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-27T19:58:40.526Z 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: [email protected]
** 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.
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

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.)

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