Optimized Laplacian Sparse Coding for Image Classification

Laplacian sparse coding exhibits good performance for image classification, because of its outstanding ability to preserve the locality and similarity information of the codes. However, there still exists two drawbacks during the Laplacian graph construction: (1) It has expensive computational cost, which significantly limits the applicability of the Laplacian sparse coding to large-scale data sets. (2) Euclidean distance does not necessarily reflect the inherent distribution of the data. To construct a more robust Laplacian graph, we introduce a local landmarks approximation method instead of the traditional k-nearest neighbor algorithm, and design a new form of adjacency matrix. Based on the Nesterov’s gradient projection algorithm, we develop an effective numerical solver to optimize the local landmarks approximation problem with guaranteed quadratic convergence. The obtained codes have more discriminating power compared with traditional sparse coding approaches for image classification. Comprehensive experimental results on publicly available datasets demonstrate the effectiveness of our method.