In this paper, we exploit the relationship between the translational image motion and the Compressive Sensing (CS) measurements in order to perform the camera motion estimation in the compressed domain. Various CS measurement matrices have been investigated, and most of them are random Gaussian/Bernoulli matrices. Data acquisition using such matrices becomes computationally expensive for real time applications. Data acquisition using circulant CS matrices can be efficiently implemented in hardware using shift registers. We propose to use a circulant CS matrix on image frames to obtain the CS measurements and then to perform motion estimation in the measurement domain. Experimental results show that our method guarantees high motion estimation accuracy with few measurements. Our proposed method finds its application in video shot segmentation and video tracking where fast camera motion estimation is needed. © 2013 IEEE.