As traditional target tracking based on compressive sensing has poor robustness in texture change, scale variation and illumination change, a real-time tracking algorithm using compressing sensing based on Gaussian differential graph was proposed. Firstly, Gaussian differential graph is acquired from multi-scale space of image. The features are extracted from the graph and taken as input signals of impressive sensing. Secondly, by compressing, dimension reduction, target neighborhood traversal, parameters update, the optimal search window is estimated. Thirdly, the search window is mapped onto the corresponding original image, and target tracking in the video sequences is finished. Gaussian differential graph had some characteristics such as single-channel, small grayscale range, low value, simple structure, small dimensions, which make the algorithm have strong robustness in scaling, texture and illumination changing. The real-time performance was inherited from the traditional algorithm. Experiments proved that with the proposed algorithm the moving target can be tracked quickly and accurately in a complex environment.