Sparse representation is a potential image representation method, which has been applied to target detection for images. The process to calculate sparse coefficients is complex when the orthogonal matching pursuit (OMP) algorithm is used, which cannot satisfy the requirement of rapid processing. An idea of recursive Kalman filter is introduced, and a fast OMP (FastOMP) algorithm is proposed to calculate the sparse coefficient. The Hermitian lemma is used to update the current information from the last status. The FastOMP algorithm can avoid repeated calculation of higher-dimension matrix data. In order to further improve the efficiency of the algorithm, the parallel computation method is proposed based on GPU/CUDA (graphics processing unit/compute unified device architecture). The parallel computation capacity of GPU is utilized to accelerate the FastOMP algorithm. The experimental results show that the FastOMP algorithm saves the processing time notably and improves the detection accuracy compared to the traditional OMP algorithm.