第14卷第6期 智能系统学报 Vol.14 No.6 2019年11月 CAAI Transactions on Intelligent Systems Nov.2019 D0:10.11992/tis.201904058 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190829.1513.006html 低秩分块矩阵的核近似 王中元，刘惊雷 (烟台大学计算机与控制工程学院，山东烟台264005) 摘要：为了探讨结构受限下的矩阵分解问题，通过最小化块外对角线来增强类与类之间数据表示的不相关 性，从而实现分块约束，即数据来源于不同的聚类结构，是一种局部结构的约束：同时通过增强样本的自表达 属性并缩小样本之间的差距来增强类内数据表示的相关性，从而实现低秩约束，即数据行出现冗余，是一种全 局结构的约束。随后设计了一个低秩分块矩阵的核近似算法，通过交替方向乘子法迭代求解。最后将该方法 分别在人脸识别和字符识别上进行测试。实验结果表明，所提出的低秩分块矩阵分解算法在收敛速度和近似 精度上都具有一定的优势。 关键词：低秩近似：块对角矩阵：稀疏矩阵：核近似：矩阵分解：交替向量乘子法：子空间聚类：图像识别 中图分类号：TP181文献标志码：A文章编号：1673-4785(2019)06-1209-08 中文引用格式：王中元，刘惊雷.低秩分块矩阵的核近似.智能系统学报，2019,14(6)：1209-1216. 英文引用格式：WANG Zhongyuan,,LIU Jinglei..Kernel approximation of a low-.rank block matrix.CAAI transactions on intelli-- gent systems,.2019,146):1209-1216. Kernel approximation of a low-rank block matrix WANG Zhongyuan,LIU Jinglei (School of Computer and Control Engineering,Yantai University,Yantai 264005,China) Abstract:In order to explore the matrix decomposition problem under structural constraints,irrelevance of data repres- entation between classes was enhanced in this paper by minimizing the diagonal outside the block,thus realizing the block constraint,i.e.,the data is derived from different cluster structures.It is a local structure constraint.At the same time,by enhancing the self-expressing property of the sample and narrowing the gap between samples,the correlation of the data representation in the class was enhanced,thereby realizing the low-rank constraint,i.e.,the redundancy of the data row was a constraint of the global structure,thereby realizing the low-rank constraint.A kernel approximation al- gorithm for low-rank block matrix was then designed and solved iteratively by alternating the direction method of multi- pliers(ADMM).Finally,the method was tested on face recognition and character recognition.Experimental results showed that the proposed low-rank block matrix decomposition algorithm has certain advantages in solving speed and approximate accuracy. Keywords:low-rank approximation;block diagonal matrix;sparse matrix;kernel approximation;matrix factorization; alternating direction method of multipliers (ADMM);subspace clustering;image identification 近年来，随着互联网的快速发展，人们获取数理并发掘其中蕴含的有效信息引起人们的关注。 据以及存储数据的能力都迅速提高。不论在科学 大部分机器学习都能够通过矩阵的形式表示，但 技术还是在日常生活的各个领域都累积了大量数 是在现实生活中经常会使用到数以百万记的样 据。怎样才能快速有效地对这些数据进行分析处 本，通过对矩阵进行处理的机器学习技术的复杂 度会随着应用规模的增加呈二次方增长，这会使 收稿日期：2019-04-24.网络出版日期：2019-08-30 很多问题无法解决。 基金项目：国家自然科学基金项目(61572419,61773331,61703360)： 山东省高等学校科技计划(J17KA091). 目前通常通过低秩矩阵分解、核方法和聚类 通信作者：刘惊雷.E-mail:jinglei_liu(@sina.com 等方法来解决矩阵分解的问题"。聚类是将输入DOI: 10.11992/tis.201904058 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190829.1513.006.html 低秩分块矩阵的核近似 王中元，刘惊雷 （烟台大学 计算机与控制工程学院，山东 烟台 264005） 摘 要：为了探讨结构受限下的矩阵分解问题，通过最小化块外对角线来增强类与类之间数据表示的不相关 性，从而实现分块约束，即数据来源于不同的聚类结构，是一种局部结构的约束；同时通过增强样本的自表达 属性并缩小样本之间的差距来增强类内数据表示的相关性，从而实现低秩约束，即数据行出现冗余，是一种全 局结构的约束。随后设计了一个低秩分块矩阵的核近似算法，通过交替方向乘子法迭代求解。最后将该方法 分别在人脸识别和字符识别上进行测试。实验结果表明，所提出的低秩分块矩阵分解算法在收敛速度和近似 精度上都具有一定的优势。 关键词：低秩近似；块对角矩阵；稀疏矩阵；核近似；矩阵分解；交替向量乘子法；子空间聚类；图像识别 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2019)06−1209−08 中文引用格式：王中元, 刘惊雷. 低秩分块矩阵的核近似 [J]. 智能系统学报, 2019, 14(6): 1209–1216. 英文引用格式：WANG Zhongyuan, LIU Jinglei. Kernel approximation of a low-rank block matrix[J]. CAAI transactions on intelli￾gent systems, 2019, 14(6): 1209–1216. Kernel approximation of a low-rank block matrix WANG Zhongyuan，LIU Jinglei (School of Computer and Control Engineering, Yantai University, Yantai 264005, China) Abstract: In order to explore the matrix decomposition problem under structural constraints, irrelevance of data repres￾entation between classes was enhanced in this paper by minimizing the diagonal outside the block, thus realizing the block constraint, i.e., the data is derived from different cluster structures. It is a local structure constraint. At the same time, by enhancing the self-expressing property of the sample and narrowing the gap between samples, the correlation of the data representation in the class was enhanced, thereby realizing the low-rank constraint, i.e., the redundancy of the data row was a constraint of the global structure, thereby realizing the low-rank constraint. A kernel approximation al￾gorithm for low-rank block matrix was then designed and solved iteratively by alternating the direction method of multi￾pliers (ADMM). Finally, the method was tested on face recognition and character recognition. Experimental results showed that the proposed low-rank block matrix decomposition algorithm has certain advantages in solving speed and approximate accuracy. Keywords: low-rank approximation; block diagonal matrix; sparse matrix; kernel approximation; matrix factorization; alternating direction method of multipliers (ADMM); subspace clustering; image identification 近年来，随着互联网的快速发展，人们获取数 据以及存储数据的能力都迅速提高。不论在科学 技术还是在日常生活的各个领域都累积了大量数 据。怎样才能快速有效地对这些数据进行分析处 理并发掘其中蕴含的有效信息引起人们的关注。 大部分机器学习都能够通过矩阵的形式表示，但 是在现实生活中经常会使用到数以百万记的样 本，通过对矩阵进行处理的机器学习技术的复杂 度会随着应用规模的增加呈二次方增长，这会使 很多问题无法解决。 目前通常通过低秩矩阵分解、核方法和聚类 等方法来解决矩阵分解的问题[1]。聚类是将输入 收稿日期：2019−04−24. 网络出版日期：2019−08−30. 基金项目：国家自然科学基金项目 (61572419，61773331，61703360)； 山东省高等学校科技计划 (J17KA091). 通信作者：刘惊雷. E-mail：jinglei_liu@sina.com. 第 14 卷第 6 期 智 能 系 统 学 报 Vol.14 No.6 2019 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2019