| Popis: |
Manifold landmarking is the problem of selecting a subset of discrete locations on a continuous manifold for label assignment, in order to reduce interpolation error of subsequent semi-supervised learning. In this paper, we select landmarks to minimize the condition number (λ max /λ min ) of a submatrix of an alignment matrix Φ, which is equivalent to minimizing an interpolation error bound. Specifically, we design an efficient greedy scheme, where at each iteration t + 1 we choose one landmark i (thus deleting the corresponding row and column i of Φ t ) so that the resulting submatrix Φ t+1 has the smallest condition number. Towards fast landmark selection, at iteration t + 1, we first compute the two extreme eignevectors v 1 and v N corresponding to λ min and λ max of Φ t via known methods like LOBPCG. We show that λ min (λ max ) of submatrix Φ t+1 , from deleting the chosen row-column pair, can be approximated by an upper (lower) bound that is an easily computable function of eigen-pair {v 1 , λ min } ({v N , λ max }) of Φ t . The error bounds of the obtained approximations can be numerically computed during the greedy step. Leveraging these proofs, we minimize a bound of the condition number for submatrix Φ t+1 at each greedy step t + 1. Experiments on synthetic and real-world manifold data demonstrate the superiority of our proposed landmarking algorithm compared to several state-of-the-art schemes. |
