Vehicle verification in different scenes is a nontrivial problem that cannot be solved by simple correspondence matching. In the paper, the verification problem is treated as a binary classification problem. If the two vehicles in two views are the same, they are a positive pair; otherwise, a negative pair. Here, we propose an effective sparse representation (SR) method called Boost K-SVD to generate the feature vectors for vehicle representation. In Boost K-SVD, the particle filtering is first applied for the initial atom selection. Then, it finds the atoms satisfying the restricted isometry property (RIP). Finally, we propose a discrimination criterion to determine the optimal dictionary size. Instead of initial random atom selection, Boost K-SVD generates the atoms incrementally to create a more compact dictionary. Furthermore, the dictionary with RIP can produce sparser representation vectors with higher verification accuracy. Experimental results show that our method has better performance compared with the other methods.