«上一篇
文章快速检索     高级检索
下一篇»
  智能系统学报  2019, Vol. 14 Issue (6): 1209-1216  DOI: 10.11992/tis.201904058
0

引用本文  

王中元, 刘惊雷. 低秩分块矩阵的核近似[J]. 智能系统学报, 2019, 14(6): 1209-1216. DOI: 10.11992/tis.201904058.
WANG Zhongyuan, LIU Jinglei. Kernel approximation of a low-rank block matrix[J]. CAAI Transactions on Intelligent Systems, 2019, 14(6): 1209-1216. DOI: 10.11992/tis.201904058.

基金项目

国家自然科学基金项目(61572419,61773331,61703360);山东省高等学校科技计划(J17KA091).

通信作者

刘惊雷. E-mail:jinglei_liu@sina.com

作者简介

王中元,男,1996年生,硕士研究生,主要研究方向为核方法与矩阵分解;
刘惊雷,男,1970年生,教授,博士,主要研究方向为人工智能和理论计算机科学。主持国家自然科学基金面上项目、山东省自然科学基金面上项目各1项。发表学术论文40余篇

文章历史

收稿日期:2019-04-24
网络出版日期:2019-08-30
低秩分块矩阵的核近似
王中元 , 刘惊雷     
烟台大学 计算机与控制工程学院,山东 烟台 264005
摘要:为了探讨结构受限下的矩阵分解问题,通过最小化块外对角线来增强类与类之间数据表示的不相关性,从而实现分块约束,即数据来源于不同的聚类结构,是一种局部结构的约束;同时通过增强样本的自表达属性并缩小样本之间的差距来增强类内数据表示的相关性,从而实现低秩约束,即数据行出现冗余,是一种全局结构的约束。随后设计了一个低秩分块矩阵的核近似算法,通过交替方向乘子法迭代求解。最后将该方法分别在人脸识别和字符识别上进行测试。实验结果表明,所提出的低秩分块矩阵分解算法在收敛速度和近似精度上都具有一定的优势。
关键词低秩近似    块对角矩阵    稀疏矩阵    核近似    矩阵分解    交替向量乘子法    子空间聚类    图像识别    
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 representation 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 algorithm for low-rank block matrix was then designed and solved iteratively by alternating the direction method of multipliers (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.
Key words: low-rank approximation    block diagonal matrix    sparse matrix    kernel approximation    matrix factorization    alternating direction method of multipliers (ADMM)    subspace clustering    image identification    

近年来,随着互联网的快速发展,人们获取数据以及存储数据的能力都迅速提高。不论在科学技术还是在日常生活的各个领域都累积了大量数据。怎样才能快速有效地对这些数据进行分析处理并发掘其中蕴含的有效信息引起人们的关注。大部分机器学习都能够通过矩阵的形式表示,但是在现实生活中经常会使用到数以百万记的样本,通过对矩阵进行处理的机器学习技术的复杂度会随着应用规模的增加呈二次方增长,这会使很多问题无法解决。

目前通常通过低秩矩阵分解、核方法和聚类等方法来解决矩阵分解的问题[1]。聚类是将输入数据按照某种相似性规则划分为若干类。低秩矩阵分解是将数据矩阵分解成噪声和稀疏低秩两部分。在众多方法之中,通过核方法近似低秩分块矩阵由于其模型合理直观、实施简单、效果显著而受到关注。

本文考虑结构受限下的矩阵分解问题[2],其中结构受限主要是低秩结构受限和分块结构受限。本文通过消除噪声并最小化块外对角线来增强类与类之间数据表示的不相关性,从而实现分块约束[3];同时通过增强训练样本的自表达属性并缩小样本之间的差距来增强类内数据表示的相关性,从而实现低秩约束[4],最后迭代优化求解一系列子问题来实现矩阵分解的目的。随后设计了一个低秩分块矩阵的核近似算法(low-rank block kernel approximation, LBKA)。LBKA不仅能够显著提高算法速度,而且由于低秩分块约束极大的消除了噪声的影响,使得算法近似精度也有了提高。

相较于传统的矩阵分解问题,本文设计了低秩分块矩阵的核近似算法。本文的特点和贡献如下:

1)引入了一种低秩分块矩阵的框架,通过核方法将非线性问题转化为高维空间中的线性问题来解决,这样不仅可以提高算法的精度,还可以通过低秩约束来降低算法复杂度,提高了计算的收敛速度与计算精