Towards Large Scale Spectral Problems via Diffusion Process
© 2017 IEEE. Spectral methods refer to the problem of finding eigenvectors of an affinity matrix. Despite promising performance on revealing manifold structure, they are limited in its applicability to large-scale problems due to the high computational cost of eigendecomposition. Nyström method, as...
| Main Authors: | , , , |
|---|---|
| Format: | Conference Paper |
| Published: |
2017
|
| Online Access: | http://hdl.handle.net/20.500.11937/69318 |
| _version_ | 1848762030331265024 |
|---|---|
| author | Li, Q. Liu, Wan-Quan Li, Ling Wang, R. |
| author_facet | Li, Q. Liu, Wan-Quan Li, Ling Wang, R. |
| author_sort | Li, Q. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | © 2017 IEEE. Spectral methods refer to the problem of finding eigenvectors of an affinity matrix. Despite promising performance on revealing manifold structure, they are limited in its applicability to large-scale problems due to the high computational cost of eigendecomposition. Nyström method, as a classic method, seeks an approximate solution by first solving a smaller eigenproblem defined on a subset of landmarks, and then extrapolating the eigenvectors of all points through the linear combinations of landmarks. In this paper, we embed a simple yet effective diffusion process into Nyström formula so that we can utilize all data points rather than only landmarks to set up the reduced eigenproblem and estimate the out-of-sample embedding. We apply our method on both dimension reduction and spectral clustering problems. Extensive experiments show that the proposed method can reduce the approximation error with fewer landmarks and less run time. |
| first_indexed | 2025-11-14T10:41:05Z |
| format | Conference Paper |
| id | curtin-20.500.11937-69318 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T10:41:05Z |
| publishDate | 2017 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-693182019-06-05T06:47:08Z Towards Large Scale Spectral Problems via Diffusion Process Li, Q. Liu, Wan-Quan Li, Ling Wang, R. © 2017 IEEE. Spectral methods refer to the problem of finding eigenvectors of an affinity matrix. Despite promising performance on revealing manifold structure, they are limited in its applicability to large-scale problems due to the high computational cost of eigendecomposition. Nyström method, as a classic method, seeks an approximate solution by first solving a smaller eigenproblem defined on a subset of landmarks, and then extrapolating the eigenvectors of all points through the linear combinations of landmarks. In this paper, we embed a simple yet effective diffusion process into Nyström formula so that we can utilize all data points rather than only landmarks to set up the reduced eigenproblem and estimate the out-of-sample embedding. We apply our method on both dimension reduction and spectral clustering problems. Extensive experiments show that the proposed method can reduce the approximation error with fewer landmarks and less run time. 2017 Conference Paper http://hdl.handle.net/20.500.11937/69318 10.1109/DICTA.2017.8227498 restricted |
| spellingShingle | Li, Q. Liu, Wan-Quan Li, Ling Wang, R. Towards Large Scale Spectral Problems via Diffusion Process |
| title | Towards Large Scale Spectral Problems via Diffusion Process |
| title_full | Towards Large Scale Spectral Problems via Diffusion Process |
| title_fullStr | Towards Large Scale Spectral Problems via Diffusion Process |
| title_full_unstemmed | Towards Large Scale Spectral Problems via Diffusion Process |
| title_short | Towards Large Scale Spectral Problems via Diffusion Process |
| title_sort | towards large scale spectral problems via diffusion process |
| url | http://hdl.handle.net/20.500.11937/69318 |