Spectral analysis of alignment in manifold learning

Local manifold learning methods produce a collection of overlapping local coordinate systems from a given set of sample points. Alignment is the process to stitch those local systems together to produce a global coordinate system and is done through the computation of the eigensubspace of a so-called alignment matrix. In this paper, we present an analysis of the eigenstructure of the alignment matrix giving both necessary and sufficient conditions under which the space of the alignment matrix recovers the global coordinate system. We also show by analyzing examples that the gap in the spectrum of the alignment matrix is proportional to the size of the overlap of the local coordinate systems. Our results pave the way for gaining better understanding of the performance of local manifold learning methods.