摘要
最大方差展开(maximum variance unfolding,MVU)是在流形局部等距概念基础上提出的一种新的非线性维数约减算法,能有效学习出隐含在高维数据集中的低维流形结构.但MVU的优化需要解决一个半定规划(semidefinite programming,SDP)问题,巨大的计算和存储复杂度限制了它在大规模数据集上的可行性.提出了MVU的一种快速算法——松弛最大方差展开(relaxed maximum variance unfolding,RMVU),算法基于Laplacian特征映射(Laplacian eigenmap)近似保留数据集局部结构的思想,对MVU中严格的局部距离保留约束进行松弛;算法求解转变为一个广义特征分解问题,大大降低了运算强度和存储需求.为了适应更大规模数据集的处理需求,同时提出了RMVU的一种改进算法——基于基准点的松弛最大方差展开(landmark-based relaxed MVU,LRMVU).在模拟数据集和COLT-20数据库上的实验验证了算法的有效性.
Nonlinear dimensionality reduction is a challenging problem encountered in a variety of high dimensional data analysis, including machine learning, pattern recognition, scientific visualization, and neural computation. Based on the notion of local isometry, maximum variance unfolding （MVU） is proposed recently for nonlinear dimensionality reduction. By pulling the input patterns as far apart as possible subject to the strict local distance-preserving constraints, MVU can learn the faithful low dimensional structure of the manifold embedded in the high dimensional space. However, the final optimization of MVU needs to solve a semidefinite programming （SDP） problem; the huge computational and memory complexity makes MVU infeasible for large-scale implementations. To solve the problem, a fast algorithm of MVU, called relaxed MVU （RMVU）, is proposed. In RMVU, originated from the approximate local structure preservation idea of Laplacian eigenmaps, the strict local distance-preserving constraints of MVU are relaxed. The optimization finally becomes a generalized eigen-decomposition problem and the computational intensity is significantly reduced. For addressing the more large-scale data sets, an improved RMVU, called landmark-based relaxed MVU （LRMVU）, is also proposed. The theoretical analysis and experiments on the artificial data set and actual images show that the proposed algorithms RMVU and LRMVU can largely reduce the computational and memory complexity of MVU.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2009年第6期988-994,共7页
Journal of Computer Research and Development
基金
重庆市自然科学基金项目(CSTC2006BB2152
CSTC2008BB2160)~~
