M²NuFFT-A computationally efficient suboptimal power spectrum estimator for fast exploration of nonuniformly sampled...

Nonuniformly sampled signals are prevalent in real-world applications. However, estimating their power spectra from finite samples poses a significant challenge. The optimal solution-Generalized Prolate Spheroidal Sequence (GPSS) by solving the associated Generalized Eigenvalue Problem (GEP)-is computationally intensive and thus impractical for large datasets. This paper describes a fast, nonparametric method: Multiband-Multitaper Nonuniform Fast Fourier Transform (M²NuFFT), which substantially reduces computational burden while maintaining statistical efficiency. The algorithm partitions the signal frequency band into multiple sub-bands. Within each sub-band, optimal tapers are computed at a nominal analysis band and shifted to other analysis bands using the Nonuniform Fast Fourier Transform (NuFFT), avoiding repeated GEP computations. Spectral power within the analysis band is then estimated as the average power across the taper outputs. For the special case where the nominal band is centered at zero frequency, tapers can be approximated via cubic spline interpolation of Discrete Prolate Spheroidal Sequence (DPSS), eliminating GEP computation entirely. This reduces the complexity from $O\left(N^4\right)$ to as low as $O(N\text{log}N+N\text{log}(1/ϵ\left)\right)$ . Statistical properties of the estimator, assessed using Bronez GPSS theory, reveal that the bias and variance bound of the M²NuFFT estimator are identical to those of the optimal estimator. Additionally, the degradation of bias bound indicates deviation from optimality. Finally, we propose an extension of Thomson $F$ -test to test periodicity in nonuniform samples. The estimator's performance is validated through simulation and real-world data, demonstrating its practical applicability. The Matlab code of the fast algorithm is available on GitHub [1].