1. A retrieval method comprising: learning a projection for embedding an original image representation in an embedding space, the original image representation being based on features extracted from the image, the projection being learned from category-labeled training data to optimize a classification rate on the training data, the learning of the projection including, for a plurality of iterations: selecting a sample from the training data; embedding the sample with a current projection; scoring the embedded sample with current first and second classifiers, the first classifier corresponding to a category of the label of the sample, the second classifier corresponding to a different category, selected from a set of categories; updated the current projection and at least one of the current first and second classifier for iterations where the second classifier generates a higher score than the first classifier, the updated projection serving as the current projection for a subsequent iteration, each of the updated classifiers serving as the current classifier for the respective category for a subsequent iteration; and storing one of the updated projections as the learned projection; and with a processor, for each of plurality of database images, computing a comparison measure between a query image and the database image, the comparison measure being computed in the embedding space, respective original image representations of the query image and the database image being embedded in the embedding space with the projection; and providing for retrieving at least one of the database images based on the comparison.