TY - JOUR
T1 - Diverse power iteration embeddings
T2 - Theory and practice
AU - Huang, Hao
AU - Yoo, Shinjae
AU - Yu, Dantong
AU - Qin, Hong
N1 - Funding Information:
The authors gratefully thank all the anonymous reviewers for constructive suggestions toward paper improvement. This research is supported in part by US National Science Foundation (NSF) (Nos. IIS-0949467, IIS-1047715, and IIS-1049448), National Natural Science Foundation of China (Nos. 61190120, 61190121, and 61190125) and by Brookhaven National Lab. (BNL) PD 15-025. It is also supported by US DoE, Grant No. DESC0003361, funded through the American Recovery and Reinvestment Act of 2009, and BSA/DOE Prime Contract (DE-AC02-98CH10886) to BNL. This paper is an extension of the work published in ICDM 2014 [19]. S. Yoo is the corresponding author.
Publisher Copyright:
© 1989-2012 IEEE.
PY - 2016/10
Y1 - 2016/10
N2 - 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.
AB - 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.
KW - Approximated spectral analysis
KW - power iteration
UR - http://www.scopus.com/inward/record.url?scp=84991608547&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84991608547&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2015.2499184
DO - 10.1109/TKDE.2015.2499184
M3 - Article
AN - SCOPUS:84991608547
SN - 1041-4347
VL - 28
SP - 2606
EP - 2620
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 10
M1 - 7322265
ER -