Abstract: Object tracking has been one of the most important and active research areas in computer vision. A large number of tracking algorithms have been proposed in recent years with demonstrated success. Recently, some researchers employed compressive sensing which is originally used for efficiently acquiring and reconstructing a signal by finding solutions to underdetermined linear systems for object tracking to model object appearance. Since those existing fast compressive tracking algorithms were usually based on one fixed size search range to search for targets within a frame, it easily lead to fail when used to track one fast-moving target, especially which exceed the scope of the search. In order to solve this problem and search target successfully, a tracking algorithm based on compression sensing is proposed to use displacement speed feature to change the search range adaptively. The new method takes inter-frame motion in to account and utilizes it to represent the movement speed of target in one frame. Then the ratio between the movement speed of target in current frame and the average speed of a few frames before can be obtained to describe the scope changes of the search range. Last, the product of the ratio and the originally fixed size search range is defined as latest one in the next frame. In other word, if the target movement speed is stable, the size of search range remain; quickening up the target movement speed to increase search range or slow down to narrow, which make search range adapt to velocity. In the end of the paper, the performance of the proposed algorithm is test on datasets with the fast-motion attributes. As evaluated on challenging sequences in which the target object undergoes fast movements, the new proposed tracking algorithm performs favorably to adaptively change search range and always successfully to track target, especially when existing fast compressive tracking algorithm loses target.