Accurate estimation of the instantaneous heart rate (HR) using a reflectance-type photoplethysmography (PPG) sensor is challenging because the dominant frequency observed in the PPG signal corrupted by motion artifacts (MAs) does not usually overlap the true HR, especially during high-intensity exercise. Recent studies have proposed various MA cancellation and HR estimation algorithms that use simultaneously measured acceleration signals as noise references for accurate HR estimation. These algorithms provide accurate results with a mean absolute error (MAE) of approximately 2 beats per minute (bpm). However, some of their results deviate significantly from the true HRs by more than 5 bpm. To overcome this problem, the present study modifies the power spectrum of the PPG signal by emphasizing the power of the frequency corresponding to the true HR. The modified power spectrum is obtained using a Gaussian kernel function and a previous estimate of the instantaneous HR. Because the modification is effective only when the previous estimate is accurate, a recently reported finite state machine framework is used for real-time validation of each instantaneous HR result. The power spectrum of the PPG signal is modified only when the previous estimate is validated. Finally, the proposed algorithm is verified by rigorous comparison of its results with those of existing algorithms using the ISPC dataset (n = 23). Compared to the method without MA cancellation, the proposed algorithm decreases the MAE value significantly from 6.73 bpm to 1.20 bpm (p < 0.001). Furthermore, the resultant MAE value is lower than that obtained by any other state-of-the-art method. Significant reduction (from 10.89 bpm to 2.14 bpm, p < 0.001) is also shown in a separate experiment with 24 subjects.