Walking/gait speed is a key measure for daily mobility characterization. To date, various studies have attempted to design algorithms to estimate walking speed using an inertial sensor worn on the lower back, which is considered as a proper location for activity monitoring in daily life. However, these algorithms were rarely compared and validated on the same datasets, including people with different preferred walking speed. This study implemented several original, improved, and new algorithms for estimating cadence, step length and eventually speed. We designed comprehensive cross-validation to compare the algorithms for walking slow, normal, fast, and using walking aids. We used two datasets, including reference data for algorithm validation from an instrumented mat (40 subjects) and shanks-worn inertial sensors (88 subjects), with normal and impaired walking patterns. The results showed up to 50% performance improvements. Training of algorithms on data from people with different preferred speeds led to better performance. For the slow walkers, an average RMSE of 2.5 steps/min, 0.04 m, and 0.10 m/s were respectively achieved for cadence, step length, and speed estimation. For normal walkers, the errors were 3.5 steps/min, 0.08 m, and 0.12 m/s. An average RMSE of 1.3 steps/min, 0.05 m, and 0.10 m/s were also observed on fast walkers. For people using walking aids, the error significantly increased up to an RMSE of 14 steps/min, 0.18 m, and 0.27 m/s. The results demonstrated the robustness of the proposed combined speed estimation approach for different speed ranges. It achieved an RMSE of 0.10, 0.18, 0.15, and 0.32 m/s for slow, normal, fast, and using walking aids, respectively.