Document Open Access Logo

Declutter and Resample: Towards Parameter Free Denoising

Authors Mickael Buchet, Tamal K. Dey, Jiayuan Wang, Yusu Wang

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.23.pdf
  • Filesize: 1.17 MB
  • 16 pages

Document Identifiers

Author Details

Mickael Buchet
Tamal K. Dey
Jiayuan Wang
Yusu Wang

Cite As Get BibTex

Mickael Buchet, Tamal K. Dey, Jiayuan Wang, and Yusu Wang. Declutter and Resample: Towards Parameter Free Denoising. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.23

Abstract

In many data analysis applications the following scenario is commonplace: we are given a point set that is supposed to sample a hidden ground truth K in a metric space, but it got corrupted with noise so that some of the data points lie far away from K creating outliers also termed as ambient noise. One of the main goals of denoising algorithms is to eliminate such noise so that the curated data lie within a bounded Hausdorff distance of K. Popular denoising approaches such as deconvolution and thresholding often require the user to set several parameters and/or to choose an appropriate noise model while guaranteeing only asymptotic convergence. Our goal is to lighten this burden as much as possible while ensuring theoretical guarantees in all cases.

Specifically, first, we propose a simple denoising algorithm that requires only a single parameter but provides a theoretical guarantee on the quality of the output on general input points. We argue that this single parameter cannot be avoided. We next present a simple algorithm that avoids even this parameter by paying for it with a slight strengthening of the sampling condition on the input points which is not unrealistic. We also provide some preliminary empirical evidence that our algorithms
are effective in practice.

Subject Classification

Keywords
  • denoising
  • parameter free
  • k-distance,compact sets

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Amenta and M. Bern. Surface reconstruction by voronoi filtering. Discr. Comput. Geom., 22:481-504, 1999. Google Scholar
  2. G. Biau et al. A weighted k-nearest neighbor density estimate for geometric inference. Electronic Journal of Statistics, 5:204-237, 2011. Google Scholar
  3. J.-D. Boissonnat, L. J. Guibas, and S. Y. Oudot. Manifold reconstruction in arbitrary dimensions using witness complexes. Discr. Comput. Geom., 42(1):37-70, 2009. Google Scholar
  4. M. Buchet. Topological inference from measures. PhD thesis, Paris 11, 2014. Google Scholar
  5. M. Buchet, F. Chazal, T. K. Dey, F. Fan, S. Y. Oudot, and Y. Wang. Topological analysis of scalar fields with outliers. In Proc. 31st Sympos. Comput. Geom., pages 827-841, 2015. Google Scholar
  6. M. Buchet, T. K. Dey, J. Wang, and Y. Wang. Declutter and resample: Towards parameter free denoising. arXiv version of this paper: arXiv 1511.05479, 2015. Google Scholar
  7. C. Caillerie, F. Chazal, J. Dedecker, and B. Michel. Deconvolution for the wasserstein metric and geometric inference. In Geom. Sci. Info., pages 561-568. 2013. Google Scholar
  8. T.-H. H. Chan, M. Dinitz, and A. Gupta. Spanners with slack. In Euro. Sympos. Algo., pages 196-207, 2006. Google Scholar
  9. F. Chazal, D. Cohen-Steiner, and A. Lieutier. A sampling theory for compact sets in Euclidean space. Discr. Comput. Geom., 41(3):461-479, 2009. Google Scholar
  10. F. Chazal, D. Cohen-Steiner, and Q. Mérigot. Geometric inference for probability measures. Found. Comput. Math., 11(6):733-751, 2011. Google Scholar
  11. D. Comaniciu and P. Meer. Mean shift: A robust approach toward feature space analysis. IEEE Trans. Pattern Anal. Machine Intelligence, 24(5):603-619, 2002. Google Scholar
  12. T. K. Dey, Z. Dong, and Y. Wang. Parameter-free topology inference and sparsification for data on manifolds. In Proc. ACM-SIAM Sympos. Discr. Algo., pages 2733-2747, 2017. Google Scholar
  13. T. K. Dey, J. Giesen, S. Goswami, and W. Zhao. Shape dimension and approximation from samples. Discr. Comput. Geom., 29:419-434, 2003. Google Scholar
  14. D. L. Donoho. De-noising by soft-thresholding. IEEE Trans. Info. Theory., 41(3):613-627, 1995. Google Scholar
  15. C. R. Genovese et al. On the path density of a gradient field. The Annal. Statistics, 37(6A):3236-3271, 2009. Google Scholar
  16. V. J. Hodge and J. Austin. A survey of outlier detection methodologies. Artificial Intelligence Review, 22(2):85-126, 2004. Google Scholar
  17. H. Jiang and S. Kpotufe. Modal-set estimation with an application to clustering. arXiv preprint arXiv:1606.04166, 2016. Google Scholar
  18. A. Meister. Deconvolution problems in nonparametric statistics. Lecture Notes in Statistics. Springer, 2009. Google Scholar
  19. U. Ozertem and D. Erdogmus. Locally defined principal curves and surfaces. J. Machine Learning Research, 12:1249-1286, 2011. Google Scholar
  20. B. W. Silverman. Density estimation for statistics and data analysis, volume 26. CRC press, 1986. Google Scholar
  21. J. Zhang. Advancements of outlier detection: A survey. EAI Endorsed Trans. Scalable Information Systems, 1(1):e2, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact