Sample complexity of the distinct elements problem
Mathematical Statistics and Learning · 2018
DOI: 10.4171/msl/1-1-2 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Statistics and Learning, 2018. Verfasst von Yihong Wu und 1 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref).
Abstract (Originalsprache)
We consider the distinct elements problem, where the goal is to estimate the number of distinct colors in an urn containing k balls based on n samples drawn with replacements. Based on discrete polynomial approximation and interpolation, we propose an estimator with additive error guarantee that achieves the optimal sample complexity within O(\mathrm {log\:log}\: k) factors, and in fact within constant factors for most cases. The estimator can be computed in O(n) time for an accurate estimation. The result also applies to sampling without replacement provided the sample size is a vanishing fraction of the urn size. One of the key auxiliary results is a sharp bound on the minimum singular values of a real rectangular Vandermonde matrix, which might be of independent interest.
Zitieren
APA
Wu, Y., & Yang, P. (2018). Sample complexity of the distinct elements problem. Mathematical Statistics and Learning. https://doi.org/10.4171/msl/1-1-2
Vancouver
Wu Y, Yang P. Sample complexity of the distinct elements problem. Mathematical Statistics and Learning. 2018. doi:10.4171/msl/1-1-2
BibTeX
@article{Wu2018,
author = {Wu, Yihong and Yang, Pengkun},
title = {Sample complexity of the distinct elements problem},
journal = {Mathematical Statistics and Learning},
year = {2018},
doi = {10.4171/msl/1-1-2}
}
EUVIMED