基于二次规划的求两线性流形之间距离的一种算法

基于二次规划的求两线性流形之间距离的一种算法 2013 年第 2 期漳州师范学院学报自 然科 学版No. 2. 2013 年 ( 总第 80 期)Journal of Zhangzhou Normal University (Nat. Sci. ) General No. 80文章编号:1008-7826201302-0011-07 基于二次规划的求两线性流形之间距离的一种算法1 2何金花 , 张圣贵 1. 福建师范大学 协和 学院, 福建 福州 350108; 2. 福建师范大学 数学与计算机 科学学院, 福建 福州 350108 摘 要: 本文基于两线性流形之间距离与公垂线性流形的定义,将求解两线性流形之间距离的问题转化为凸二次规划问题, 结合全局最优性条件, 给出了求解两线性流形之间距离的算法. 通过实例,说明了该算法的可行性关键词 :线性流形 ; 距离 ; 二次规划 中图分类号: O221文献标识码:A An Algorithm Based on the Quadratic Programming for Distance between Two Linear Manifolds 1 2HE Jin-hua , ZHANG Sheng-gui 1.Concord College, Fujian Normal University, Fuzhou, Fujian 350108, China; 2.School of Mathematics and Computer Science, Fujian Normal University, Fuzhou, Fujian 350108, China Abstract: Based on the distance between two linear manifolds and the definition of common perpendicular manifold, this article characterizes the distance between two linear manifolds by a convex quadratic program and gives its algorithm by optimal conditions. And we illustrate the feasibility of the proposed algorithm through exampleKey words: linear manifold ; distance ; quadratic program 在这个 充满 着信息 的时 代, 研究 者在 研究过 程中 不可避 免的 会遇到 大量 的高维 数据, 比如全 球气 候变暖模型、人类基因分布、语音信号、数字图像、文本聚类和功能性磁共振图像等. 这些高维数据通常分布4在一个 低维 非线性 流形 上, 因此, 能 有效发 现这 种低维 流形 结构的 流形 学习法 目前 (语言 表达 有问题 ) 5 6Isometric Mapping, 等距 映射 算法、LLE Locally Linear Embedding, 局部线 性嵌入 算法、LE Laplacian 8Eigenmaps 算法、ISOTOP 算法 等 都成 为近年来 的 研究热点. 这 些算法都 是 基于不同 的 距离而提 出. 虽然这些算 法在 降维上 都可 以取得 很好 的效果, 但 是 针对某 些识 别问题 而言 (比如 人脸 识别), 无 法 得到足够9多的具有类别标签的数据, 因为对数 据进行标注是一件非常耗时的工作. 魏莱、 王守觉 提出了一种基于流形距离的半监督判别分析法, 通过定义流形距离来选择流形上的数据全局近邻点、异类近邻点和同类近邻点, 通 过这 种 方式选 择的 近邻点 更能 符合数 据具 有低维 流形 分布的 假设, 根据流 形距 离可以 得到 相应的相似度度量, 并利用这种相 似性度量, 同MFA 类似地 构造一个Fisher 判别函数, 保持了全局 数据集的内 在 流 形结构l设三维向量空间的直线 的方程为: 1ax + a x + a x + c 011 1 12 2 13 3 11.1ax + a x + a x + c 021 1 22 2 23 3 2l直线 的方程为: 2收稿日 期: 2013-04-22 作者简 介: 何金花1985-, 女, 福建省福州市人, 硕士, 助教. 12漳州师范学院学报(自然科学版) 2013 年 bx + b x + b x + d 011 1 12 2 13 3 1 1.2bx + b x + b x + d 021 1 22 2 23 3 2l l若 , 是异 面直线 ,则 文献1给出 了求 异面 直线1.1 和1.2 之 间距 离的 最值方 法. 实际 上, 这两条1 2异面直线公垂线的垂足与下列二次规划模型: 2 22xy+ xy +? x ymin 11 2 2 3 3ax + a x + a x + c 011 1 12 2 13 3 1ax + a x + a x + c 021 1 22 2 23 3 2st1.3 by + b y + b y + d 011 1 12 2 13 3 1by + b y + b y + d 021 1 22 2 23 3 2* * * * * * * * *的最优解 xx , , x , y y , y 相关,公垂线的垂足分 别是 xx , x 和 yy , y因此 这两条1 231 2 3 12 3 12 3异面直线之间的距离为: 2 22* * * * *xy+ xy + xy 11 2 2 3 3显然,二次规划1.3 是一个凸规划,因此必有最优解,且有许多求解算法n受此启发,本文将建立实数域 R 上的向量空间 R 中两个不相交的线性流形的公垂线性流形的垂足相关的二次凸规划模型,并给出求解算法1 两线性流形之间距离的二次规划模型 为了方便读者, 我们在此给出相关的概念与结论L k + k k+ k1, kk , K设Y 是向 量空间V 的非 空子集, 如果Y 中任意两个 向量 , 所确定 的直线 1 12 2 12 1 212都含于Y 内, 就称Y 是V 中的线性流形. 数域 K 上 n 维向量空间V 中的线性流形Y 一定具有以下形式: YW + + W,其中 是Y 中任意取定的向量, W 是V 的一个线性子空间, 它被Y 唯一确定, 000W 称为Y 的方向子空间, Y 称为W 型的线性流形. dimW 被定义为Y 的维数如果 数域 K 上的 n 元 非 齐次线 性方 程组 AX b 其中 A 是 mn 阵, b 是 m 维列向 量有解, 则它的所 有解 组成的 集合 是一个W 型的线性流形 +W其中, 是 该非 齐次线 性方 程组的 一个 特解, W 是 其导0 0出组 AX 0 的解空间n定义 2.1 :设实数域 R 上的 n 维向量空间 R 中的两个线性流形 P +WP , +W 且 PP ?,1 1 12 2 2 1212则 之间的距离定义为: ,其中PP , d PP , min ? , 12 12 1 2 12 12 12 P11 P2 2n n定义 2.2 :设 P +WP , +W 其中 , R ,WW , 都是 R 的子空间, 且1 1 12 2 2 12 12PP ?,dimW 0 , dimW 0若存在 PP , 使得 LL + + L ,且12 1 2 1 1 2 2 10 2 0LW ,LW , 则称 L 是线性流形 PP 和 的公垂线性流形0 10 2 1 2定理 2.1 2: 设 A 是实 mn 矩 阵, A 是实 mn 矩阵, bb , 分别是 mm , 维 实列向量. 令1 1 2 2 12 12dM , M min x? y12xM M x Ax b?, M y A y b ? ,且 MM ?, 定义 1 是 MM , 的 1 11 2 2 2 12 12yM 2第 2 期何金花 , 张圣 贵 :基于 二次规划的求 两线性流 形之 间距离的一种 算法 13 距离, XM ,Y M则 XY? d, M M ? XY? M? X , XY? M?Y12 12 1 2注:若 MM ?, 则有 dM , M 012 12两线性流形之间距离的二次规划模型: bb ,设 A 是 mn 矩阵, A 是实 mn 矩阵, 分别是 mm , 维实列向量1 1 2 2 12 12设 Rank A r, Rank A s M x A x b?, M y A y b ? , 1 2 1 11 2 2 2nr n s则: M + k k RM ,+ ? ? R?10 ii i 2 0 j j j ij 11其中: , ,?, i1,2,?, nr? 和 , ,?, j1,2,?, n? s i i12 i in j j1 j2 jn分别是 Ax 00 和A y 的一个基础解系, 和 分别是 Ax b 和A y b 的一个特解12 0 0 1 12 2若: 则求线性流形 的距离问题,就是求 MM ? , MM 到12 12TTX x , x , x M ,Y y , y , , y M 12 nn 1 1 2 2使得 XY最小,它等价于二次规划问题: 2min XYAX b11st 2.1 AY b22进一步可以转化为关于未知量 kk , , k , , , ,的无约束问题: 12 nr 1 2 n s2nr n smin 2.2 + k ? 00 iij jij 11?2nr n s令: Gk ,k ,k , , ? + k ? + ?12 nr 1 2 n s0 i i0 j jij 11?则由最优性条件,2.2 转化为解下列线性方程组:?G0?k1G0?k2 2.3 ?G0?knr?G01?G 0? ns 14漳州师范学院学报(自然科学版) 2013 年 因2.1 是一个凸规划问题, 则它一定有解, 因而方程组2.3 有解. 若 (kk , , k , , , ,) 是2.312 nr 1 2 n s的一个解,并令 nrn?s + k , + ? ,则: dM , M 0 ii 0 j j 12ij 112 算法与算例 设 M x Ax b , M y A y b1 11 2 2 2算法: m n m n m m1 2 12输入 A R , A R ,b R ,b R 1 2 12步 1: 分别计算 RankA , RankA ,b , RankA , RankA ,b 1 11 2 2 2若 RankA Rank A ,b 或RankA Rank A ,b ,则此问题无解, 1 11 2 2 2终止. 否则,转步 3? AbA11 1步 2 :计算 Rank , RankAb A222Ab A?11 1若 Rank RankAb A222则 之间的距离为 0, 终止. 否则,转步 4MM 到12RankA RankA ,b n, RankA RankA ,b n , 则分别求线性方程组 Ax b 和A y b步 2 :1 若1 11 2 2 2 1 12 2* * *的唯一解 ,输出 以及 之间的距离 dM , M x -y ,终止x 和y x ,y MM 到 12 122 若 , 则 RankA RankA ,b n, RankA RankA ,b s n1 11 2 2 2*2.1 求 Ax b 的唯一解 x ; 112.2 求 A y b 的一个特解 和 A y 0 的一个基础解系 , , ; 2 2 0 2 1 2 n-s2ns*2.3 求G, ?, x? + 的展开式; ?12 ns0 j jj1?2.4 求解未知量为 , , ?,的线性方程组: 12 ns?G 01G02?G0ns?ns*那么 ,终止dM ,+ M x? ?12 0 j jj1?3 若 RankA RankA ,b rn, RankA RankA ,b n , 则 1 11 2 2 2*3.1 求 A y b 的唯一解 y ; 2 23.2 求 Ax b 的一个特解 和 Ax 0 的一个基础解系 , , ; 11 0 1 1 2 n-r第 2 期何金花 , 张圣 贵 :基于 二次规划的求 两线性流 形之 间距离的一种 算法 15 2nr*3.3 求Gk , k ?,k + k? y 的展开式; 12 nr? 0 i i? i13.4 求解未知量为 kk , ?, k 的线性方程组: 12 nr?G 0?k1G0?k? 2?G 0?knrnr*那么 dM ,+ M k? y ,终止 120 ii? i14 若 RankA RankA ,b rn, RankA RankA ,b s n , 则 1 11 2 2 24.1 求 Ax b 的一个特解 和 Ax 0 的一个基础解系 , , ; 11 0 1 1 2 n-r4.2 求 A y b 的一个特解 和 A y 0 的一个基 , , ; 2 2 0 2 1 2 n-s2nr n s4.3 求Gk ,k ,k , , ? + k ? + ? 的展开式; ?12 nr 1 2 n s 0 i i 0 j j ij 11?4.4 求解未知量为 kk , , kk , , , k , , ,?,的线性方程组: 12 12 nr 1 2 n s?G0?k1G0?k2G 0?knr?G0? 1?G 0? nsnrn?s令: , + k , + ? 0 ii 0 j jij 11则: dM , M 终止 12例 3.1 :令16漳州师范学院学报(自然科学版) 2013 年 x1?00 0 1 11?x200 1 1 0 1A ,b ,. xx311 1 3 2 1x411 2 5 3 1x500 0 1 1 1 Bb ,? 1?00 1 1 0 111 1 3 2 1C ,b ? 2?11 2 5 3 1令线性流形 M x Bx b + ?+ ?, R 1 0 12 3N x Cx b + x+ y + z x, y, z R2 01 2 3其中: 01 0 000 1 0 0 , 0 , 0 , 101 2 310 0 ?10 0 01?11 1 10 ?10 0? 0 , 0 , 2 , 101 2 300 1 000 0 1?求 X x , x , x x M 和Y y , y , y , y N 使得 XY最小,即 1 234 1 2 3 42min XYBX b1stCY b222 2 22x2xy + 6y2xz + 6yz + 32 zxu + 2yu + 2zu + u + 2xv转化为: min22+v + 6yw + 3w + 24 xy 2z 22 uw + 2st x, y, zu , ,v, w R 由最优性条件转化为求解下列线性方程组: 21 x? y? zu+ v ?+ x 63 y + zu + + 3w 2?+ x 33 y + zu + 1x + y zu +1?xv + 033 yw +1