This paper presents a new method for estimating the average heart rate from a foot/ankle worn photoplethysmography (PPG) sensor during fast bike activity. Placing the PPG sensor on the lower half of the body allows more energy to be collected from energy harvesting in order to give a power autonomous sensor node, but comes at the cost of introducing significant motion interference into the PPG trace. We present a normalised least mean square adaptive filter and short-time Fourier transform based algorithm for estimating heart rate in the presence of this motion contamination. Results from 8 subjects show the new algorithm has an average error of 9 beats-per-minute when compared to an ECG gold standard.