In this paper, a new technique that estimates velocity using sparse representation is suggested. The CW radar is effective for velocity estimation because it uses the Doppler frequency shift. Traditional Doppler shifts are calculated using a Fast Fourier Transform (FFT), which is needed to obtain a sufficient number of received signals for high-resolution. The maximum frequency resolution is proportional to the number of received signals, and accurate velocity estimation requires a long integration time. When a moving target has a velocity of 30km/h and a carrier frequency is 10GHz, received signal has a Doppler frequency of 55Hz and noise. The length of the dictionary and the receive signal can be reduced to 0.2% by multiplying a normalized random matrix. If the received Doppler frequency is close to a frequency in the dictionary and unique which means that the sparsity is one, then the least square error is small between the received signal and the dictionary. A minimum least square error of the frequency is represented by the best fit solution instead of L1 minimization because the sparsity of the solution is well known. The solution has a dependency with noise but the proposed method is much faster and more robust. This study proves that in Doppler estimation, a proposed method improves frequency accuracy even though the received data reduce to 0.2% of samples.