最大方差展开的快速松弛算法

摘要：

最大方差展开(maximum variance unfolding,MVU)是在流形局部等距概念基础上提出的一种新的非线性维数约减算法,能有效学习出隐含在高维数据集中的低维流形结构.但MVU的优化需要解决一个半定规划(semidefinite programming,SDP)问题,巨大的计算和存储复杂度限制了它在大规模数据集上的可行性.提出了MVU的一种快速算法--松弛最大方差展开(relaxed maximum varianceunfolding,RMVU),算法基于Laplacian特征映射(Laplacian eigenmap)近似保留数据集局部结构的思想,对MVU中严格的局部距离保留约束进行松弛;算法求解转变为一个广义特征分解问题,大大降低了运算强度和存储需求.为了适应更大规模数据集的处理需求,同时提出了RMVU的一种改进算法--基于基准点的松弛最大方差展开(landmark-based relaxed MVU,LRMVU).在模拟数据集和COLT-20数据库上的实验验证了算法的有效性.

关键词：维数约减、最大方差展开、Laplacian特征映射、流形学习、方差分析

所属期刊栏目：46

分类号：TP18(自动化基础理论)

资助基金：重庆市自然科学基金项目CSTC2006BB2152,CSTC2008BB2160

在线出版日期：2009-07-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：988-994