Objective pain assessment methods pose an advantage over the currently used subjective pain rating tools. Advanced signal processing methodologies, including the wavelet transform (WT) and the orthogonal matching pursuit algorithm (OMP), were developed in the past two decades. The aim of this study was to apply and compare these time-specific methods to heart rate samples of healthy subjects for acute pain detection. Fifteen adult volunteers participated in a study conducted in the pain clinic at a single center. Each subject's heart rate was sampled for 5-min baseline, followed by a cold pressor test (CPT). Analysis was done by the WT and the OMP algorithm with a Fourier/Wavelet dictionary separately. Data from 11 subjects were analyzed. Compared to baseline, The WT analysis showed a significant coefficients' density increase during the pain incline period (p < 0.01) and the entire CPT (p < 0.01), with significantly higher coefficient amplitudes. The OMP analysis showed a significant wavelet coefficients' density increase during pain incline and decline periods (p < 0.01, p < 0.05) and the entire CPT (p < 0.001), with suggestive higher amplitudes. Comparison of both methods showed that during the baseline there was a significant reduction in wavelet coefficient density using the OMP algorithm (p < 0.001). Analysis by the two-way ANOVA with repeated measures showed a significant proportional increase in wavelet coefficients during the incline period and the entire CPT using the OMP algorithm (p < 0.01). Both methods provided accurate and non-delayed detection of pain events. Statistical analysis proved the OMP to be by far more specific allowing the Fourier coefficients to represent the signal's basic harmonics and the wavelet coefficients to focus on the time-specific painful event. This is an initial study using OMP for pain detection; further studies need to prove the efficiency of this system in different settings.