Abstract: Learning algorithm of spectral manifold aims at discovering a low-dimensional representation in the high-dimensional vector space, which has been widely used recently. Although it has achieved many proud achievements, there is a very big bottleneck that computational complexity is very high, which limits its application in practice. This paper proposes a novel approach, called fast learning algorithm of spectral manifold (FSM). FSM includes two technologies to reduce high computational complexity: (1) FSM selects p anchor points from n data points through random selection or k-means selection and represents the data points as the linear combinations of these anchor points. Thus this paper designs a new form of adjacency matrix, which reduces the computational complexity of adjacency graph. (2) Linear manifold learning can be used for computing the low-dimensional parameterization of high-dimensional data effectively, which reduces the computational complexity of the optimal eigenvalue. The experimental results on face databases (Yale, ORL and extended Yale B) show the effectiveness of the proposed FSM method.

Key words: spectral method, manifold learning, anchor points, adjacency matrix

摘要： 谱流形学习算法的目标是发现嵌入在高维数据空间中的低维表示，其近年来得到了广泛的应用。虽然已经取得了许多令人骄傲的成绩，但是却存在一个很大的瓶颈——计算复杂度太高，这严重阻碍了算法在实际中的应用。提出了谱流形快速学习算法，该算法包括两个降低算法复杂度的技术：（1）通过随机选择或者k-means方法从n个样本点中选出p个锚点，把每个样本点表达为由锚点的邻域点线性组合的形式，从而设计了邻接矩阵的新形式，降低了邻接图的计算复杂度；（2）利用线性化的流形学习算法有效地计算高维数据到低维数据的映射，从而降低了优化特征值的计算复杂度。该算法在3个常用人脸数据集（Yale、ORL、Extended Yale B）上得到了验证，进一步证明了算法的有效性。

关键词: 谱方法, 流形学习, 锚点, 邻接矩阵