Abstract
Manifold learning, especially spectral embedding, is known as one of the most effective learning approaches on high dimensional data, but for real-world applications it raises a serious computational burden in constructing spectral embeddings for large datasets. To overcome this computational complexity, we propose a novel efficient embedding construction, Diverse Power Iteration Embedding (DPIE). DPIE shows almost the same effectiveness of spectral embeddings and yet is three order of magnitude faster than spectral embeddings computed from eigen-decomposition. Our DPIE is unique in that 1) it finds linearly independent embeddings and thus shows diverse aspects of dataset; 2) the proposed regularized DPIE is effective if we need many embeddings; 3) we show how to efficiently orthogonalize DPIE if one needs; and 4) Diverse Power Iteration Value (DPIV) provides the importance of each DPIE like an eigen value. Such various aspects of DPIE and DPIV ensure that our algorithm is easy to apply to various applications, and we also show the effectiveness and efficiency of DPIE on clustering, anomaly detection, and feature selection as our case studies.
Original language | English (US) |
---|---|
Article number | 7322265 |
Pages (from-to) | 2606-2620 |
Number of pages | 15 |
Journal | IEEE Transactions on Knowledge and Data Engineering |
Volume | 28 |
Issue number | 10 |
DOIs | |
State | Published - Oct 2016 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics
Keywords
- Approximated spectral analysis
- power iteration