Photoplethysmography (PPG) signals collected from wearable sensing devices during physical exercise are easily corrupted by motion artifact (MA), which poses great challenge on heart rate (HR) estimation. This paper proposes a new framework to accurately estimate HR using two leads of PPG signals in combination with accelerometer (ACC) data in the presence of MA. A moving time window is first used to segment PPG signals and ACC signals. Then, MA is attenuated by joint sparse spectrum reconstruction in each time window, where maximum spectrum frequencies of ACC are subtracted from the spectrum frequency of PPG signals. Further, HR for each cleansed PPG is estimated from the frequency with maximum amplitude in the sparse spectrum. The actual HR is determined using spectral band powers calculated from each reconstructed PPG signals. The proposed method was validated using the 2015 IEEE Signal Processing Cup dataset. The average absolute error is 1.15 beats per minutes (BPM) (standard deviation: 2.00 BPM), and the average absolute error percentage is 0.95% (standard deviation: 1.86%). The proposed method outperforms the previously reported work in terms of accuracy.