抄録
ID-002
Scaling Locally Linear Embedding
Yasuhiro Fujiwara(NTT/Osaka Univ.)・Naoki Marumo・Mathieu Blondel・Koh Takeuchi(NTT)・Hideaki Kim(NTTデータ)・Tomoharu Iwata・Naonori Ueda(NTT)
Locally Linear Embedding (LLE) is a popular approach to dimensionality reduction.
For dimensionality reduction, it computes a nearest neighbor graph from a given dataset where edge weights are obtained by applying the Lagrange multiplier method, and it then computes eigenvectors of the LLE kernel where the edge weights are used to obtain the kernel.
Although LLE is used in many applications, its computation cost is significantly high.
Our approach, Ripple, is based on two ideas:
(1) it incrementally updates the edge weights by exploiting the Woodbury formula and
(2) it efficiently computes eigenvectors of the LLE kernel by exploiting the LU decomposition-based inverse power method.
Experiments show that Ripple is significantly faster than the original approach of LLE by guaranteeing the same results of dimensionality reduction.