Witnessed k-Distance

详细信息    查看全文

• 作者：Leonidas Guibas (1)
  Dmitriy Morozov (2)
  Quentin Mérigot (3)
  
• 关键词：Distance function ; Order ; k Voronoi diagram ; Geometric inference ; Surface reconstruction ; Wasserstein noise
• 刊名：Discrete and Computational Geometry
• 出版年：2013
• 出版时间：January 2013
• 年：2013
• 卷：49
• 期：1
• 页码：22-45
• 全文大小：970KB
• 参考文献：1. Amenta, N., Bern, M.: Surface reconstruction by Voronoi filtering. Discrete Comput. Geom. 22(4), 481-04 (1999) CrossRef
  2. Arya, S., Mount, D.: Computational geometry: proximity and location. In: Handbook of Data Structures and Applications, pp.?63.1-3.22 (2005)
  3. Aurenhammer, F.: A new duality result concerning Voronoi diagrams. Discrete Comput. Geom. 5(1), 243-54 (1990) CrossRef
  4. Bolley, F., Guillin, A., Villani, C.: Quantitative concentration inequalities for empirical measures on non-compact spaces. Probab. Theory Relat. Fields 137(3), 541-93 (2007) CrossRef
  5. Chazal, F., Cohen-Steiner, D., Lieutier, A.: A sampling theory for compact sets in Euclidean space. Discrete Comput. Geom. 41(3), 461-79 (2009) CrossRef
  6. Chazal, F., Cohen-Steiner, D., Mérigot, Q.: Geometric inference for probability measures. Found. Comput. Math. 11, 733-51 (2011) CrossRef
  7. Chazal, F., Oudot, S.: Towards persistence-based reconstruction in Euclidean spaces. In: Proceedings of the ACM Symposium on Computational Geometry, pp.?232-41 (2008)
  8. Clarkson, K.: Nearest-neighbor searching and metric space dimensions. In: Shakhnarovich, G., Darrell, T., Indyk, P. (eds.) Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pp.?15-9. MIT Press, Cambridge (2006)
  9. Clarkson, K., Shor, P.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387-21 (1989) CrossRef
  10. Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. Discrete Comput. Geom. 37(1), 103-20 (2007) CrossRef
  11. Cohen-Steiner, D., Edelsbrunner, H., Morozov, D.: Vines and vineyards by updating persistence in linear time. In: Proceedings of the ACM Symposium on Computational Geometry, pp. 119-26 (2006)
  12. Dasgupta, S.: Learning mixtures of Gaussians. In: Proceedings of the IEEE Symposium on Foundations of Computer Science, p. 634 (1999)
  13. Dey, T., Goswami, S.: Provable surface reconstruction from noisy samples. Comput. Geom. 35(1-), 124-41 (2006) CrossRef
  14. Edelsbrunner, H.: The union of balls and its dual shape. Discrete Comput. Geom. 13, 415-40 (1995) CrossRef
  15. Edelsbrunner, H., Harer, J.: Persistent homology—a survey. In: Goodman, J.E., Pach, J., Pollack, R. (eds.) Surveys on Discrete and Computational Geometry. Twenty Years Later, Contemporary Mathematics, vol.?453, pp.?257-82. Amer. Math. Soc., Providence (2008) CrossRef
  16. Edelsbrunner, H., Harer, J.: Computational Topology. Am. Math. Soc., Providence (2010)
  17. Indyk, P.: Nearest neighbors in high-dimensional spaces. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn. pp.?877-92. CRC Press, Boca Raton (2004)
  18. Kloeckner, B.: Approximation by finitely supported measures. arXiv:1003.1035 (2010)
  19. Laurent, B., Massart, P.: Adaptive estimation of a quadratic functional by model selection. Ann. Stat. 28(5), 1302-338 (2000) CrossRef
  20. Niyogi, P., Smale, S., Weinberger, S.: Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom. 39(1), 419-41 (2008) CrossRef
  21. Niyogi, P., Smale, S., Weinberger, S.: A topological view of unsupervised learning from noisy data. SIAM J. Comput. 40(4), 646-63 (2011) CrossRef
  22. Rubner, Y., Tomasi, C., Guibas, L.: The earth mover’s distance as a metric for image retrieval. Int. J. Comput. Vis. 40(2), 99-21 (2000) CrossRef
  23. Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. arXiv:1011.3027 (2010)
  24. Villani, C.: Topics in Optimal Transportation. Am. Math. Soc., Providence (2003)
  
• 作者单位：Leonidas Guibas (1)
  Dmitriy Morozov (2)
  Quentin Mérigot (3)
  
  1. Department of Computer Science, Stanford University, Stanford, CA, USA
  2. Lawrence Berkeley National Laboratory, Berkeley, CA, USA
  3. Laboratoire Jean Kuntzmann, Université de Grenoble and CNRS, Saint-Martin d’Hères, France
  
• ISSN：1432-0444

文摘

Distance functions to compact sets play a central role in several areas of computational geometry. Methods that rely on them are robust to the perturbations of the data by the Hausdorff noise, but fail in the presence of outliers. The recently introduced distance to a measure offers a solution by extending the distance function framework to reasoning about the geometry of probability measures, while maintaining theoretical guarantees about the quality of the inferred information. A combinatorial explosion hinders working with distance to a measure as an ordinary power distance function. In this paper, we analyze an approximation scheme that keeps the representation linear in the size of the input, while maintaining the guarantees on the inference quality close to those for the exact but costly representation.