| Paper ID | MLSP-34.4 |
| Paper Title |
Fast Manifold Landmarking Using Extreme Eigen-pairs |
| Authors |
Fen Wang, Xidian University, China; Gene Cheung, York University, Canada; Yongchao Wang, Xidian University, China; Wai-Tian Tan, Innovation Labs, Cisco Systems, United States |
| Session | MLSP-34: Subspace Learning and Applications |
| Location | Gather.Town |
| Session Time: | Thursday, 10 June, 15:30 - 16:15 |
| Presentation Time: | Thursday, 10 June, 15:30 - 16:15 |
| Presentation |
Poster
|
| Topic |
Machine Learning for Signal Processing: [MLR-SBML] Subspace and manifold learning |
| IEEE Xplore Open Preview |
Click here to view in IEEE Xplore |
| Virtual Presentation |
Click here to watch in the Virtual Conference |
| 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 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. |
