Obtained by wide band radar system, high resolution range profile (HRRP) is the projection of scatterers of target to the radar line-of-sight (LOS). HRRP reconstruction is unavoidable for inverse synthetic aperture radar (ISAR) imaging, and of particular usage for target recognition, especially in cases that the ISAR image of target is not able to be achieved. For the high-speed moving target, however, its HRRP is stretched by the high order phase error. To obtain well-focused HRRP, the phase error induced by target velocity should be compensated, utilizing either measured or estimated target velocity. Noting in case of under-sampled data, the traditional velocity estimation and HRRP reconstruction algorithms become invalid, a novel HRRP reconstruction of high-speed target for under-sampled data is proposed. The Laplacian scale mixture (LSM) is used as the sparse prior of HRRP, and the variational Bayesian inference is utilized to derive its posterior, so as to reconstruct it with high resolution from the under-sampled data. Additionally, during the reconstruction of HRRP, the target velocity is estimated via joint constraint of entropy minimization and sparseness of HRRP to compensate the high order phase error brought by the target velocity to concentrate HRRP. Experimental results based on both simulated and measured data validate the effectiveness of the proposed Bayesian HRRP reconstruction algorithm.