nips nips2001 nips2001-88 nips2001-88-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Marzia Polito, Pietro Perona
Abstract: Locally Linear Embedding (LLE) is an elegant nonlinear dimensionality-reduction technique recently introduced by Roweis and Saul [2]. It fails when the data is divided into separate groups. We study a variant of LLE that can simultaneously group the data and calculate local embedding of each group. An estimate for the upper bound on the intrinsic dimension of the data set is obtained automatically. 1
[1] C. Bishop, Neural Networks for Pattern Recognition, Oxford Univ. Press, (1995).
[2] S. T. Roweis, L.K.Saul, Science, 290, p. 2323-2326, (2000).
[3] J. Tenenbaum , V. de Silva, J. Langford, Science, 290, p. 2319-2323, (2000). A Appendix In Proposition 2 of Section 4 we proved that during the LLE procedure we can automatically detect the number of K -connected components, in case there is no noise. Similarly, in Proposition 1 of Section 3 we proved that under ideal conditions (no noise, locally flat data), we can determine an estimate for the intrinsic dimension of the data. Our next goal is to establish a certain robustness of these results in the case there is numerical noise, or the components are not completely separated, or the data is not exactly locally flat . In general, suppose we have a non degenerate matrix A, and an orthonormal basis of eigenvectors VI, ... , V m , with eigenvalues AI , ... Am. As a consequence of a small perturbation of the matrix into A + dA, we will have eigenvectors Vi + dVi with eigenvalues Ai + dAi' The unitary norm constraint makes sure that dVi is orthogonal to Vi and could be therefore written as dVi = L:k#i O'.ikVk. Using again the orthonormality, one can derive expressions for the perturbations of Ai and Vi : dAi O'.ij (Ai - Aj) < vi,dAvi > < Vj,dAVi > . This shows that if the perturbation dA has order E, then the perturbations dA and are also of order E. Notice that we are not interested in perturbations O'.ij within the eigenspace of eigenvalue 0, but rather those orthogonal to it, and therefore Ai =j:. Aj. O'.ij