Power Spectral Analysis (PSA) of Heart Rate Variability (HRV) is widely used to detect various heart related health disorders such as sinus arrhythmia but also brain related such as epileptic seizures. The latest PSA systems are based on Lomb periodogram, which may have proven suitable for processing unevenly sampled signals, such as ECGs/RR-intervals, however it comes with high complexity that hinders its implementation in wearable devices. In fact, the initial phase of the Lagrange based interpolation requires oversampling of the input signals, typically by a factor of 4 or higher, which results in significant increase of the size of the applied Fast-Fourier-Transform (FFT). In this paper, we propose an approach that allows the significant reduction of the Lomb periodogram by up-to 4 times without compromising the output accuracy. This is achieved by replacing the Lagrange based interpolation with a Fast Gaussian Gridding method (FGG), and integrating it for the first time within the Lomb periodogram. The FGG method allows the transformation of the initial unevenly sampled grid of input samples to a regular one, leading to an accurate grid for a much smaller oversampling factor than the one required in the original Lomb periodogram. Our results using synthetic and real RR interval samples from the MIT-Arrythmia database show significant reduction of the total complexity without compromising the accuracy when compared with the original Lomb periodogram. In particular, we show that for 10−5 digits output precision: we can reduce the FFT size that is the most computationally intensive component by up-to 4 times (due to the smaller oversampling of the initial signal), the total execution time of the Lomb periodogram by 74% and the total operations by 76%. The proposed approach opens up the avenues for performing PSA of HRV on portable devices, enabling new, insightful health monitoring applications.