Graph regularized nonnegative sparse coding using incoherent dictionary for approximate nearest neighbor search

In this paper, we consider the problem of approximate nearest neighbor (ANN) retrieval with the method of sparse coding, which is a promising tool of discovering compact representation of high-dimensional data. A new study, exploiting the indices of the active set of sparse coded data as retrieval code, exhibits an appealing ANN route. Here our work aims to enhance the method via considering its shortages of the local structure of the data. Our primary innovation is two-fold: We introduce the graph Laplacian regularization to preserve the local structure of the original data into reduced space, which is indeed beneficial to ANN. And we impose non-negativity constraints such that the retrieval code can more effectively reflect the neighborhood relation, thereby cutting down on unnecessary hash collision. To this end, we learn an incoherent dictionary with both rules via a novel formulation of sparse coding. The resulting optimization problem can be provided with an available solution by the widely used iterative scheme, where we resort to the feature-sign search algorithm in the sparse coding step and exploit the method that uses a Lagrange dual for dictionary learning step. Experimental results on publicly available image data sets manifest that the rules are positive to promote the classification and ANN accuracies. Compared with several state-of-the-art ANN techniques, our methods can achieve an interesting improvement in retrieval accuracy.