A tiny spectral PMF estimator for large discrete supports (arxiv.org)

Researchers propose a simple, fast method for nonparametric PMF estimation on very large discrete supports by treating the empirical histogram as a signal on a line graph and applying a data-driven low-pass filter. Concretely, they form a symmetric tridiagonal operator — the path-graph Laplacian plus a diagonal perturbation built from the empirical PMF — and compute the eigenvectors corresponding to the smallest few eigenvalues. Projecting the noisy empirical PMF onto that low-dimensional eigenspace yields a smooth, multi-modal estimate; a brief clipping-and-renormalization step enforces a valid PMF. Because the matrix is tridiagonal and symmetric, eigenpair computation is numerically stable and runs in time and memory proportional to support size times the chosen subspace dimension. The approach is significant because it scales to large discrete domains, requires little tuning, and is robust across sample sizes — suitable for automated pipelines and exploratory analysis where heavy-tailed and multi-modal distributions occur. The authors give a practical, data-driven rule for selecting subspace dimension via an orthogonal-series risk estimate, and empirically show better noise suppression than logspline and Gaussian-KDE baselines in intended regimes. Known failure modes include handling abrupt discontinuities, but overall the method is lightweight to implement, interpretable (low-frequency filtering), and computationally attractive for ML tasks needing reliable discrete density estimates.