Fast Manifold Landmarking Using Extreme Eigen-Pairs

Fen Wang, Gene Cheung, Yongchao Wang, Wai-Tian Tan

Abstract

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 v1 and vN 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 {v1, λmin} ({vN, λ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.
BibTeX
@inproceedings{wang2021fast,
  author = {Fen Wang and Gene Cheung and Yongchao Wang and Wai-Tian Tan},
  title = {{Fast Manifold Landmarking Using Extreme Eigen-Pairs}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2021},
  doi = {10.1109/icassp39728.2021.9414679},
}

Loading related content...

Figure