Diverse power iteration embeddings: Theory and practice

Hao Huang, Shinjae Yoo, Dantong Yu, Hong Qin

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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 languageEnglish (US)
Article number7322265
Pages (from-to)2606-2620
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume28
Issue number10
DOIs
StatePublished - Oct 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Keywords

  • Approximated spectral analysis
  • power iteration

Fingerprint

Dive into the research topics of 'Diverse power iteration embeddings: Theory and practice'. Together they form a unique fingerprint.

Cite this