Fast Manifold Landmarking Using Extreme Eigen-Pairs

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 of a submatrix of an alignment matrix $Phi$, which is equivalent to minimizing an interpolation error bound. Specifically, we design an efficient greedy scheme, where at iteration $t+1$ we choose one landmark (thus deleting one row-column pair of $\Phi_t$) so that the resulting submatrix $\Phi_{t+1}$ has the smallest condition number. Towards fast selection, we first compute the two extreme eignevectors $\v_1$ and $\v_N$ corresponding to $\lambda_{\min}$ and $\lambda_{\max}$ of $\Phi_t$ via known methods like LOBPCG. We show that $\lambda_{\min}$ ($\lambda_{\max}$) of submatrix $\bPhi_{t+1}$ can be approximated by an upper (lower) bound that is an easily computable function of eigen-pair $\{\v_1,\lambda_{\min}\}$ ($\{\v_N,\lambda_{\max}\}$) of $\bPhi_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 $\bPhi_{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.