An improved set covering problem for Isomap supervised landmark selection

• A novel algorithm for Isomap supervised landmark selection is presented.
• It relies on a weighted set covering problem solved via Lagrangian relaxation with subgradient optimization.
• The proposed technique empirically dominated prominent competing methods.
• It also emerged as a valuable alternative to Isomap for the projection of large labeled data sets.

In this paper we present a novel method for supervised landmark selection to be framed within Landmark Isomap algorithm (L-Isomap). It is based on a weighted set covering problem aimed at finding a set of landmarks whose neighborhoods cover all the points at minimum cost. The cost associated to each neighborhood is a function of two indices measuring, respectively, the closeness of the points within the neighborhood and its class homogeneity. The resulting set covering problem is solved by means of a heuristic procedure based on Lagrangian relaxation with subgradient optimization. Computational tests performed on five labeled data sets showed the usefulness of L-Isomap combined with the new landmark selection technique. Indeed, it dominated effective competing methods and emerged as a valuable alternative to Isomap for efficient dimensionality reduction in supervised learning contexts.