Abstract
Estimating probability distributions for sparse, heavy-tailed data on large supports is challenging for standard non-parametric tools. We propose a fast, automated method that treats the data as a signal on a graph and applies a data-dependent low-pass filter. By utilizing the spectral properties of a modified Laplacian matrix, the approach captures sharp peaks and heavy tails that typically baffle Kernel Density Estimators (KDEs). The method is computationally efficient, scaling linearly with the support size, and provides a robust alternative for production data pipelines.
Introduction
Nonparametric Probability Mass Function (PMF) estimation on large discrete supports (where the number of possible values $N$ ranges from thousands to millions) is a common but difficult task. Standard methods often struggle in this regime:
- Histograms: Choosing the right bin size for heavy-tailed data is difficult; too large a bin loses detail, while too small a bin retains too much noise.
- Gaussian KDEs: These tend to "over-smooth" spiky distributions, blurring distinct modes into a single blob.
- Logspline: While accurate, it can be computationally expensive and numerically unstable on complex real-world datasets.
The goal is a method that is fast, automated (no manual bandwidth tuning), and robust enough for production environments.
Methodology: The Schrödinger Connection
The core innovation is treating the empirical PMF as a signal on a line graph and applying a data-dependent spectral filter. The method constructs a symmetric tridiagonal matrix $H = L - \text{diag}(p)$, where $L$ is a standard path graph Laplacian and $p$ is the vector of empirical frequencies (the "potential").
This operator $H$ is essentially a discrete version of a Schrödinger operator. In physics, the "potential" (the data $p$) traps the "wavefunction" (the eigenvectors). Consequently, the basis vectors naturally concentrate their mass where the data is most frequent. This allows the model to fit sharp spikes while remaining smooth elsewhere.
The noisy empirical PMF is projected onto the subspace spanned by the $k$ eigenvectors corresponding to the smallest eigenvalues of $H$. Because $H$ is tridiagonal, this eigen-decomposition is extremely efficient, requiring only $O(kN)$ time and memory. The authors also provide a data-driven heuristic to select the optimal $k$ based on an orthogonal series risk estimate, removing the need for human intervention.
Results and Performance
The method was evaluated on a variety of synthetic distributions, including bimodal/trimodal power laws, Zipf distributions, and "rippled" power laws. On "spiky" distributions, the method significantly outperforms Gaussian KDEs, which fail to capture the height and isolation of the peaks.
In real-world tests using the Spambase and Bank Marketing datasets, the Laplacian method remained stable across all features, whereas the popular logspline method occasionally failed to converge or produced unreasonable estimates. The proposed method is generally as accurate as logspline but faster and more reliable for automated pipelines, performing excellently even with small sample sizes (e.g., 250 samples for a support of 5,000).
Discussion and Limitations
While the method excels at capturing spikes, it struggles with abrupt discontinuities, such as the "Mid plateau" synthetic case. Because it is fundamentally a smoothness-based spectral approach, it tends to "ring" or blur sharp edges, as seen in the projections for the plateau distribution. Future work may involve exploring different graph structures or rewards (like KL-divergence) to improve results, although the current tridiagonal structure is key to its $O(kN)$ efficiency.
Summary updated