The rotating blade is a key wearing part of aero-engine, so it is necessary to monitor its condition. Blade tip timing (BTT) is an effective non-contact monitoring method for rotating blades. However, the traditional BTT relies heavily on the once-per-revolution signal, and the BTT signal has serious under-sampling problem. In this paper, Orthogonal matching pursuit (OMP) method based on blade vibration difference is proposed to extract blade natural frequency. Firstly, a BTT sensor is used to calculate the blade vibration difference. Then, the sparse model of blade vibration difference is constructed, and the blade vibration difference signal is decomposed by OMP method under the condition of varying speed, and the vibration amplitude and natural frequency of the blades are extracted. The effectiveness and robustness of the proposed method are verified by numerical simulation, and experiments are carried out on the blade tip timing test bench. The results show that this method can accurately identify the amplitude and natural frequency of blade asynchronous vibration.