The structures of feature vectors-based semisupervised/supervised learning have gained considerable interest in recent years due to their effectiveness for better object modeling and classification. In many machine learning and computer vision tasks, a critical issue is the similarity between two feature vectors. In this paper, we present a novel technique to measure similarities among feature vectors by decomposing each feature vector as an $\ell _{1}$ sparse linear combination of the rest of the feature vectors. The main idea is that the coefficients in such sparse decomposition reflect the features’ neighborhood structure, thus providing better similarity measures among the decomposed feature vector and the rest of the feature vectors. The proposed approach is applied to label propagation and action recognition, and is evaluated on several commonly used datasets. The experimental results show that the proposed sparsity-induced similarity measure significantly improves the performance of both label propagation and action recognition.