10.4230/LIPICS.SOCG.2017.23
Buchet, Mickael
Mickael
Buchet
Dey, Tamal K.
Tamal K.
Dey
Wang, Jiayuan
Jiayuan
Wang
Wang, Yusu
Yusu
Wang
Declutter and Resample: Towards Parameter Free Denoising
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2017
denoising
parameter free
k-distance
compact sets
Aronov, Boris
Boris
Aronov
Katz, Matthew J.
Matthew J.
Katz
2017
2017-06-20
2017-06-20
2017-06-20
en
urn:nbn:de:0030-drops-72133
10.4230/LIPIcs.SoCG.2017
978-3-95977-038-5
1868-8969
10.4230/LIPIcs.SoCG.2017
LIPIcs, Volume 77, SoCG 2017
33rd International Symposium on Computational Geometry (SoCG 2017)
2017
77
23
23:1
23:16
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Aronov, Boris
Boris
Aronov
Katz, Matthew J.
Matthew J.
Katz
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2017
77
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
16 pages
1236262 bytes
application/pdf
Creative Commons Attribution 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 77, 33rd International Symposium on Computational Geometry (SoCG 2017), pages 23:1-23:16