Diverse power iteration embeddings: Theory and practice

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.