第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 intelligent 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 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. 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
·1210· 智能系统学报 第14卷 数据按照某种相似性规则划分为若干类。低秩矩 Nie等人通过对损失函数和正则化项进行l2!范数 阵分解是将数据矩阵分解成噪声和稀疏低秩两 约束，提出了一种有效的特征选择方法。 分。在众多方法之中，通过核方法近似低秩分块 然而稀疏约束只能实现局部约束，而低秩约 矩阵由于其模型合理直观、实施简单、效果显著 束却能够实现全局约束。鲁棒主成分分析(ro- 而受到关注。 bust principal component analysis,RPCA)是最典型 本文考虑结构受限下的矩阵分解问题四其 的低秩方法，最初是用来将损坏的观测数据恢复 中结构受限主要是低秩结构受限和分块结构受 为具有低秩结构的数据。后来发现RPCA可以将 限。本文通过消除噪声并最小化块外对角线来增 一个子空间的数据分解成低秩和稀疏噪声两部 强类与类之间数据表示的不相关性，从而实现分 分。但RPCA无法处理多个子空间的并集。为此 块约束)；同时通过增强训练样本的自表达属性 提出了潜在的低秩表示(LatLRR),通过利用子 并缩小样本之间的差距来增强类内数据表示的相 空间分割的低秩表示的方法解决多个子空间问题。 关性，从而实现低秩约束，最后迭代优化求解一 本节主要介绍一些基本符号并简单说明了两 系列子问题来实现矩阵分解的目的。随后设计了 种典型的基于低秩表示的方法：鲁棒主成分分析 一个低秩分块矩阵的核近似算法(Iow-rank block (RPCA)9和低秩表示(LRR)IO。 kernel approximation,.LBKA)。LBKA不仅能够显 1.1 著提高算法速度，而且由于低秩分块约束极大的 基本符号 消除了噪声的影响，使得算法近似精度也有了提高。 本文使用粗体大写字母表示矩阵，例如A。 相较于传统的矩阵分解问题，本文设计了低 用粗体小写字母表示矢量，例如a。对于A,其第 秩分块矩阵的核近似算法。本文的特点和贡献 i行被表示为行向量[A),其第j列被表示为列向 如下： 量[A0将a或Ag表示为A的第（位，）项。将 1)引入了一种低秩分块矩阵的框架，通过核 Diag(A)作为对角矩阵，其对角线上的第i项是 方法将非线性问题转化为高维空间中的线性问题 a。将单位矩阵表示为I。如果A中的所有项都 来解决，这样不仅可以提高算法的精度，还可以 是非负的，则表示为A≥0。文中将使用一些范 通过低秩约束来降低算法复杂度，提高了计算的 数，包括范数Ao,h范数lA,=∑a小Frobenius 收敛速度与计算精度。 2)设计了一种低秩分块矩阵的核近似算法。 范数IAe C,:范数A:=∑[A‖和核 该算法基于增广拉格朗日乘子法和交替方向乘子 范数A.。 法构造迭代公式，依次更新系数矩阵Z和辅助变 1.2低秩分块矩阵相关定义 量J、Q、S,直到收敛到稳定的特征矩阵。 定义1假设矩阵A=[a1,a2,…,a]ERm"是 3)在人脸识别数据集和字符识别数据集上进 一个包含n个数据点的列矩阵。其核矩阵定义 行了实验验证。实验结果表明，相较于传统的识 为：B=b(a,a）=((a,(a》,i,j=1,2,n,其 别算法，LBKA在收敛速度和近似精度上有所提 中中：ad→(a)是内核诱导的特征图。n个映射数 高。同时通过核矩阵近似处理，极大地降低了噪 据点的所有成对内积存储在核矩阵KERXn中。 声对实验的影响。 由于核矩阵的内存为On),所以在实际应用 1相关工作 中是使用数据数量的二次方来计算和存储的。例 如核主成分分析算法需要计算特征值分解 本文主要在低秩、稀疏、对角矩阵的分解领 (SVD),它的复杂度为O(n,并且要多次访问核矩 域探讨有关低秩分块矩阵的近似问题。 阵K。因此要想计算大规模的数据，必须考虑复 随着非负矩阵分解等矩阵分解算法的提 杂度的影响。 出，给数据处理领域带来了新的思路。低秩可以 图1是低秩矩阵分块的一个示例，对于任意 看作稀疏的特殊形式，低秩就是特征值稀疏；块 个矩阵A∈Rmxm,有 对角也是，块对角矩阵自身就具有低秩和稀疏的 特性。 现阶段，稀疏表示被广泛应用于信号处理倒 机器学习和计算机视觉等方面。随着基于稀疏 表示的分类(SRC)6在人脸识别中的成功应用， 图1低秩矩阵分块示例 已经提出了许多基于SRC的优化算法。例如， Fig.1 An example of low-rank matrix partitioning
数据按照某种相似性规则划分为若干类。低秩矩 阵分解是将数据矩阵分解成噪声和稀疏低秩两部 分。在众多方法之中，通过核方法近似低秩分块 矩阵由于其模型合理直观、实施简单、效果显著 而受到关注。 本文考虑结构受限下的矩阵分解问题[2] ，其 中结构受限主要是低秩结构受限和分块结构受 限。本文通过消除噪声并最小化块外对角线来增 强类与类之间数据表示的不相关性，从而实现分 块约束[3] ；同时通过增强训练样本的自表达属性 并缩小样本之间的差距来增强类内数据表示的相 关性，从而实现低秩约束[4] ，最后迭代优化求解一 系列子问题来实现矩阵分解的目的。随后设计了 一个低秩分块矩阵的核近似算法 (low-rank block kernel approximation, LBKA)。LBKA 不仅能够显 著提高算法速度，而且由于低秩分块约束极大的 消除了噪声的影响，使得算法近似精度也有了提高。 相较于传统的矩阵分解问题，本文设计了低 秩分块矩阵的核近似算法。本文的特点和贡献 如下： 1) 引入了一种低秩分块矩阵的框架，通过核 方法将非线性问题转化为高维空间中的线性问题 来解决，这样不仅可以提高算法的精度，还可以 通过低秩约束来降低算法复杂度，提高了计算的 收敛速度与计算精度。 2) 设计了一种低秩分块矩阵的核近似算法。 该算法基于增广拉格朗日乘子法和交替方向乘子 法构造迭代公式，依次更新系数矩阵 Z 和辅助变 量 J、Q、S，直到收敛到稳定的特征矩阵。 3) 在人脸识别数据集和字符识别数据集上进 行了实验验证。实验结果表明，相较于传统的识 别算法，LBKA 在收敛速度和近似精度上有所提 高。同时通过核矩阵近似处理，极大地降低了噪 声对实验的影响。 1 相关工作 本文主要在低秩、稀疏、对角矩阵的分解领 域探讨有关低秩分块矩阵的近似问题。 随着非负矩阵分解[4] 等矩阵分解算法的提 出，给数据处理领域带来了新的思路。低秩可以 看作稀疏的特殊形式，低秩就是特征值稀疏；块 对角也是，块对角矩阵自身就具有低秩和稀疏的 特性。 现阶段，稀疏表示被广泛应用于信号处理[3] 、 机器学习和计算机视觉[5] 等方面。随着基于稀疏 表示的分类 (SRC)[6] 在人脸识别中的成功应用， 已经提出了许多基于 SRC 的优化算法。例如， Nie 等人通过对损失函数和正则化项进行 l21 范数 约束，提出了一种有效的特征选择方法[7]。 然而稀疏约束只能实现局部约束，而低秩约 束却能够实现全局约束。鲁棒主成分分析 (robust principal component analysis, RPCA) 是最典型 的低秩方法，最初是用来将损坏的观测数据恢复 为具有低秩结构的数据。后来发现 RPCA 可以将 一个子空间的数据分解成低秩和稀疏噪声两部 分。但 RPCA 无法处理多个子空间的并集。为此 提出了潜在的低秩表示 (LatLRR)[8] ，通过利用子 空间分割的低秩表示的方法解决多个子空间问题。 本节主要介绍一些基本符号并简单说明了两 种典型的基于低秩表示的方法：鲁棒主成分分析 (RPCA)[9] 和低秩表示 (LRR)[10]。 1.1 基本符号 (i, j) A ⩾ 0 ||A||0 ||A||1 = ∑ i j |ai j| ||A||F = √∑ i j a 2 i j ||A||21 = ∑ j ||[A];, j || ||A||∗ 本文使用粗体大写字母表示矩阵，例如 A。 用粗体小写字母表示矢量，例如 a。对于 A，其第 i 行被表示为行向量 [A]i，其第 j 列被表示为列向 量 [A]:,j。将 aij 或 Aij 表示为 A 的第 项。将 Diag(A) 作为对角矩阵，其对角线上的第 i 项是 ai。将单位矩阵表示为 I。如果 A 中的所有项都 是非负的，则表示为 。文中将使用一些范 数，包括 l0 范数 ，l1 范数 ，Frobenius 范数 ，l21 范数 和核 范数 。 1.2 低秩分块矩阵相关定义 A = [a1, a2,··· , an] ∈ R m×n Bi j = b ( ai , aj ) = ⟨ ϕ(ai), ϕ( aj )⟩ ∀i, j = 1,2,···n ϕ : a| → ϕ(a) K ∈ R n×n 定义 1 假设矩阵 是 一个包含 n 个数据点的列矩阵。其核矩阵定义 为 ： ， ， 其 中 是内核诱导的特征图。n 个映射数 据点的所有成对內积存储在核矩阵 中。 由于核矩阵的内存为 O(n 2 )，所以在实际应用 中是使用数据数量的二次方来计算和存储的。例 如核主成分分析算法需要计算特征值分 解 (SVD)，它的复杂度为 O(n 3 )，并且要多次访问核矩 阵 K。因此要想计算大规模的数据，必须考虑复 杂度的影响。 A ∈ R m×n 图 1 是低秩矩阵分块的一个示例，对于任意 一个矩阵 ，有 A H HT ≈ + = × 图 1 低秩矩阵分块示例 Fig. 1 An example of low-rank matrix partitioning ·1210· 智 能 系 统 学 报 第 14 卷
第6期 王中元，等：低秩分块矩阵的核近似 ·1211· A=HH 集的每个数据实例可以通过其他数据实例的线性 为了用低秩分块矩阵逼近该相似度矩阵并同 组合来表示，这种性质被称为自表达属性。即 时得到聚类结构，可以分别近似这些对角块，每 X=XZ 个对角块表示一个聚类。 在存在自表达属性的情况下，数据集中的每 通过求矩阵秩的最小化来求解低秩矩阵。然 个数据点可以由来自其子空间的几个点的线性组 而这很难，可以用核近似方法将核范数最小化为 合来表示。所以，自表达属性应该是块对角的。 X=arg min f(X)+lXll. 本文令类与类之间块对角线分量尽可能小，同 式中：X∈Rmm,T>0是正则化参数。 时提高相关的类内表示，将其结构化形式表示为 定义2（奇异值阈值(SVT)要想求解核范 min入1lAoZ+2 llDoZIl (5) 数最小化问题NNM),例如： s.t.X=XZ 其中1和2是用于衡量相应的项的正数，⊙表示 X'=arg minlAf Hadamard乘积，并且XeR"。具体地说，第1项 需要使用奇异值阈值处理算子S()给出的闭式解： 是为了最小化类与类之间块对角线分量，并且 X=S(A)=UAS (E)V A=11T-Y。第2项是构造的子空间度量，以提 式中：Sr(x)=sgn(x)maxx-T,0)是软收缩算子； 高相关的类内表示。d是度量x,和x之间的距 UaΣaVT是A的SVD分解。 离。本文将两个样本之间的距离定义为欧几里德 1.2.1鲁棒的主成分分析(RPCA) 距离的平方，即x-x服。由于o范数最小化问题 假设X=[x1,x2,…,xn]∈R"是由n个样本组 是NP难问题，所以第2项可以被放宽表示为 成的数据矩阵，RPCA的目标是从损坏的矩阵 DOZIl。因此，式(5)可以重新表述为 X中确定低秩矩阵X。,同时消除稀疏噪声E,即 mini lAZ+lDoZll (6) X=Xo+E。因此，RPCA的目标函数为 s.t.X=XZ min rank(Xo)+Ello 通过整合公式(4)和(6)，可以得到： (1) s.t.X=Xo+E minlIZIl.++lDZh+llEll (7) 式中1是平衡参数；‖·。表示1o范数。由于低秩 s.t.X=XZ+E 函数的离散性质和最小化1。范数十分困难，目前 其中1、2和3为式(7)的相应项加权。 通常分别使用核范数和，范数正则化代替低秩约 下面本文对式(7)进行核化。 束和。范数正则化。因此，式(1)可以重新表述为 设中：R4→H是从输人空间到Hilbert空间的 min llXoll.+ll 映射，KeRm为半正定核矩阵： s.t.X=Xo+E (2) K=((X)'(X)=(x)'(x）=ker(r,） 其中l.和表示核范数和11范数。式(2) 其中ker:Rd×Rd→R是核函数。式()中的E可 可以使用增广拉格朗日乘子法(ALM)2来计算。 以表示为E=X-XZ,所以有 1.2.2低秩表示(LRR) minlIZIl++llX-XZ(8) RPCA是基于先验假设，即数据大多是从低 然后定义一个变量S=I-Z∈R,可以得到 秩子空间中提取的，可以用单个子空间来描述。 然而真实数据集很难用单个子空间来描述。为 IK-XZ:=IKSa=∑IKs=∑sXXs)P,其中 此，LRR假设每个数据可以由多个线性低秩子空 S=5,52,,s],∈R表示S钠第i列。将其中 间的并集近似表示。由此可以得到LRR的目标 的X替换为(X).可以得到 函数为 minllZll.+oZ+ minrank(Z)+ (3) s.t.X=DZ+E allo (9) 其中D和1分别是字典和平衡参数。川表示不 s.t.S=I-Z 同范数的约束。与RPCA类似，式(3)可以重新表 因为K=(x)/x),所以可以通过将函数gS) 述为 minllll.+Ell 定义为82K,将式9重写为以下问题： (4) =1 s.t.X=DZ+E minllZll.+Z+lDoZIl+i3g(S) (10) 1.3块对角矩阵的核近似 s.t.S=I-Z 定义3（自表达属性）来自多个子空间的并 其中核矩阵K包含在gS)中
A = HH T 为了用低秩分块矩阵逼近该相似度矩阵并同 时得到聚类结构，可以分别近似这些对角块，每 个对角块表示一个聚类。 通过求矩阵秩的最小化来求解低秩矩阵。然 而这很难，可以用核近似方法将核范数最小化为 X ∗ = argmin X f(X)+Γ∥X∥∗ X ∈ R 式中： ， m×n Γ > 0 是正则化参数。 定义 2 (奇异值阈值 (SVT)) 要想求解核范 数最小化问题 (NNM)，例如： X ∗ = argmin X Γ∥X∥∗ + 1 2 ∥X− A∥ 2 F 需要使用奇异值阈值处理算子 S Γ(·) 给出的闭式解： X ∗ = S Γ(A) = UAS Γ(ΣA)V T A S Γ(x) = sgn(x)·max(|x|−Γ,0) UAΣAV T A 式中： 是软收缩算子； 是 A 的 SVD 分解[11]。 1.2.1 鲁棒的主成分分析 (RPCA) X = [x1, x2,··· , xn] ∈ R d×n X = X0 + E 假设 是由 n 个样本组 成的数据矩阵，RPCA 的目标是从损坏的矩阵 X 中确定低秩矩阵 X0，同时消除稀疏噪声 E，即 。因此，RPCA 的目标函数为 min X0 ,E rank(X0)+λ∥E∥0 s.t. X = X0 + E (1) 式中 λ 是平衡参数； || · ||0 表示 l0 范数。由于低秩 函数的离散性质和最小化 l0 范数十分困难，目前 通常分别使用核范数和 l1 范数正则化代替低秩约 束和 l0 范数正则化。因此，式 (1) 可以重新表述为 min X0 ,E ∥X0∥∗ +λ∥E∥1 s.t. X = X0 + E (2) || · ||∗ 其中 和 || · ||1 表示核范数和 l 1 范数。式 (2) 可以使用增广拉格朗日乘子法 (ALM)[12] 来计算。 1.2.2 低秩表示 (LRR) RPCA 是基于先验假设，即数据大多是从低 秩子空间中提取的，可以用单个子空间来描述。 然而真实数据集很难用单个子空间来描述。为 此，LRR 假设每个数据可以由多个线性低秩子空 间的并集近似表示。由此可以得到 LRR 的目标 函数为 min Z,E rank(Z)+λ∥E∥1 s.t. X = DZ + E (3) 其中 D 和 λ 分别是字典和平衡参数。 || · ||1 表示不 同范数的约束。与 RPCA 类似，式 (3) 可以重新表 述为 min Z,E ∥Z∥∗ +λ∥E∥1 s.t. X = DZ + E (4) 1.3 块对角矩阵的核近似 定义 3 (自表达属性) 来自多个子空间的并 集的每个数据实例可以通过其他数据实例的线性 组合来表示，这种性质被称为自表达属性[13]。即 X = XZ 在存在自表达属性的情况下，数据集中的每 个数据点可以由来自其子空间的几个点的线性组 合来表示[14]。所以，自表达属性应该是块对角的。 本文令类与类之间块对角线分量尽可能小，同 时提高相关的类内表示，将其结构化形式表示为 min Z λ1 ∥A⊙ Z∥ 2 F +λ2∥D⊙ Z∥0 s.t. X = XZ (5) λ1 λ2 ⊙ X ∈ R d×n A = 1n1 T n −Y ||xi − xj ||2 2 ||D⊙ Z||1 其中 和 是用于衡量相应的项的正数， 表示 Hadamard 乘积，并且 。具体地说，第 1 项 是为了最小化类与类之间块对角线分量，并且 。第 2 项是构造的子空间度量，以提 高相关的类内表示。dij 是度量 xi 和 xj 之间的距 离。本文将两个样本之间的距离定义为欧几里德 距离的平方，即 。由于 l0 范数最小化问题 是 NP 难问题，所以第 2 项可以被放宽表示为 。因此，式 (5) 可以重新表述为 min Z λ1 ∥A⊙ Z∥ 2 F +λ2∥D⊙ Z∥1 s.t. X = XZ (6) 通过整合公式 (4) 和 (6),可以得到： min Z ∥Z∥∗ +λ1 A˜ ⊙ Z 2 F +λ2∥D⊙ Z∥1 +λ3∥E∥21 s.t. X = XZ + E (7) 其中 λ1、λ2 和 λ3 为式 (7) 的相应项加权。 下面本文对式 (7) 进行核化。 ϕ : R d → H K ∈ R n×n 设 是从输入空间到 Hilbert 空间的 映射， 为半正定核矩阵： Ki j = (ϕ(X) T ϕ(X))i j = ϕ(xi) T ϕ(xj) = ker(xi , xj) R d ×R d → R E = X− XZ 其中 ker： 是核函数。式 (7) 中的 E 可 以表示为 ,所以有 min Z ∥Z∥∗ +λ1 A˜ ⊙ Z 2 F +λ2∥D⊙ Z∥1 +λ3∥X− XZ∥21 (8) S = I− Z ∈ R n×n ||X− XZ||21 = ||XS||21 = ∑n i=1 ||Xsi || = ∑n i=1 (si ′X ′Xsi) 1/2 S = [s1,s2,··· ,sn],si ∈ R n ϕ(X) 然后定义一个变量 ，可以得到 , 其 中 表示 S 的第 i 列。将其中 的 X 替换为 ，可以得到 min Z ∥Z∥∗ +λ1 A˜ ⊙ Z 2 F + λ2∥D⊙ Z∥1 +λ3 ∑n i=1 √ si ′ϕ(X) ′ϕ(X)si s.t. S = I− Z (9) K = ϕ(x)′ϕ(x) g(S) ≜ ∑n i=1 √ si ′Ksi 因为 ,所以可以通过将函数 g(S) 定义为 ，将式 (9) 重写为以下问题： min Z ∥Z∥∗ +λ1 A˜ ⊙ Z 2 F +λ2∥D⊙ Z∥1 +λ3g(S) s.t. S = I− Z (10) 其中核矩阵 K 包含在 g(S) 中。 第 6 期 王中元，等：低秩分块矩阵的核近似 ·1211·
·1212· 智能系统学报 第14卷 定义4（拉格朗日乘子法、增广拉格朗日乘子 LJ,Z,0,S,C1,C2,C3)= 法、交替方向乘子法) 1)假定要求解八X)的最优化问题，满足 IWL.+ioz+aDo01,+gS计 (12) (C1,I-Z-S)+(C2,J-Z)+(C3,2-Z)+ h(X)=0,其中fX):R"→R,h(X):R"→Rm。基于 拉格朗日乘子法1可以得到以下目标函数： 5山-Z+-z-se+0-z) Le(x,A)=f(X)+uh(X) 其中(J,Q)=(J严)。C1、C2和C,是拉格朗日乘 2)在计算等式约束问题时，使用增广拉格朗 子，μ>0是惩罚参数。下面介绍详细迭代步骤： 日乘子法(ALM),ALM增加了二次惩罚项，基于 更新Z固定其他变量并通过下述步骤更新Z ALM可以得到以下目标函数： L=mm2oZ张+C,I-Z-s)+ L.(x,2)=f)+h(+Ih(X 3)要求解X)+g(Z)的最优化问题，满足约束 (CJm-z+(C0-z)+5-z+ 条件AX+BZ=C。这类问题需要用到交替方向乘 -z-s+le-z) 子法(ADMM)II,ADMM是ALM的进一步推广， 这相当于 它将对偶上升法的可分解性与ALM的收敛性相 结合，基于ADMM方法可以得到以下目标函数： L-mni-z-s+ (13) Le(x,z.)=f(X)+g(Z)+(AX+BZ-C)+ lAx+Bz-CIP mzCo-z9 其中R=[Y,0w-m]⊙Z。通过推导8L/8Z=0,可 2低秩分块矩阵的核近似算法 以得到Z的最优解，式(13)的闭式解为 算法1低秩分块矩阵的核近似算法 Z1=【2+1+K-R+U,+U2+U)(14) 输入特征矩阵X;参数，2,3；距离测量 矩阵D: 其中u1-s+号&=+号=Q侣。 输出系数矩阵Z。 更新J当固定其他变量时，式(12)的目标 初始化：=0，Z=0,Q=0,S=0,1,2,>0, 函数可以表示为J的函数，即 C=0,C2=0,C3=-0, J"=argminlI+(C.J)+ whil max(I-Z+1-S+,l1-Z+‖ oZ)>tol +-红-汇 通过使用奇异值阈值算子（见定义3），可以得 do 1)通过式(14)更新系数矩阵Z: 到一个封闭形式的解决方案，即 2)通过式(15)更新辅助变量： r=rwz-9=swn (15) 3)通过式(17)更新辅助变量2： 4)通过式(18)更新辅助变量S: 式中：U2Vr是亿-S)的奇异值分解：S0是 L 5)更新拉格朗日乘子C,C2和C3: 软阈值算子可.定义为 x-A ,x> C1=C1+'(I-Z+1-S+) S(x)={x+A,x0 然后，可以通过ALM得到式(11)的增广拉格朗 argmin DM)=(M) 日函数 (17)
定义 4 (拉格朗日乘子法、增广拉格朗日乘子 法、交替方向乘子法) h(X) = 0 f(X) : R n → R h(X) : R n → R m 1 ) 假定要求 解 f(X) 的最优化问题，满足 ，其中 ， 。基于 拉格朗日乘子法[13] 可以得到以下目标函数： Lc(x, λ) = f(X)+µh(X) 2) 在计算等式约束问题时，使用增广拉格朗 日乘子法 (ALM)，ALM 增加了二次惩罚项，基于 ALM 可以得到以下目标函数： Lc(x, λ) = f(X)+µh(X)+ c 2 ∥h(X)∥ 2 3) 要求解 f(X)+g(Z) 的最优化问题，满足约束 条件 AX+BZ=C。这类问题需要用到交替方向乘 子法 (ADMM)[13] ，ADMM 是 ALM 的进一步推广， 它将对偶上升法的可分解性与 ALM 的收敛性相 结合，基于 ADMM 方法可以得到以下目标函数： Lc(x,z, λ) = f(X)+g(Z)+λ T (AX+ BZ −C)+ c 2 ∥Ax+ Bz−C∥ 2 2 低秩分块矩阵的核近似算法 算法 1 低秩分块矩阵的核近似算法 输入 特征矩阵 X；参数 λ1， ， ；距离测量 λ2 λ3 矩阵 D； 输出 系数矩阵 Z。 初始化：J=0, Z=0, Q=0, S=0, λ1， ， λ2 λ3>0, C1=0, C2=0, C3=0, while max( I− Z t+1 −S t+1 ∞ , J t+1 − Z t+1 ∞ , Q t+1 − Z t+1 ∞ ) > tol do 1) 通过式 (14) 更新系数矩阵 Z； 2) 通过式 (15) 更新辅助变量 J； 3) 通过式 (17) 更新辅助变量 Q； 4) 通过式 (18) 更新辅助变量 S； 5) 更新拉格朗日乘子 C1，C2 和 C3； C t+1 1 = C t 1 +µ t (I− Z t+1 −S t+1 ) C t+1 2 = C t 2 +µ t (J t+1 − Z t+1 ) C t+1 3 = C t 3 +µ t (Q t+1 − Z t+1 ) 6) 更新 µ µ t+1 = min(µmax,ρµt ) end 为了优化式 (10)，首先引入两个辅助变量 J 和 Q 来使问题可分离，将式 (10) 重写为 min J,Z,Q,S ∥J∥∗ + λ1 2 A˜ ⊙ Z 2 F +λ2∥D⊙Q∥1 +λ3g(S) s.t.S = I− Z, J = Z,Q = Z, Z ⩾ 0 (11) 然后，可以通过 ALM 得到式 (11) 的增广拉格朗 日函数 L(J, Z,Q,S,C1,C2,C3)= ∥J∥∗ + λ1 2 A˜ ⊙ Z 2 F +λ2∥D⊙Q∥1 +λ3g(S)+ ⟨C1,I− Z −S⟩+⟨C2, J − Z⟩+⟨C3,Q− Z⟩+ µ 2 (∥J − Z∥ 2 F +∥I− Z −S∥ 2 F +∥Q− Z∥ 2 F ) (12) ⟨J,Q⟩ = tr(J TQ) µ > 0 其中 。C1、C2 和 C3 是拉格朗日乘 子， 是惩罚参数。下面介绍详细迭代步骤： 更新 Z 固定其他变量并通过下述步骤更新 Z L = min Z λ1 2 A˜ ⊙ Z 2 F + ⟨ C t 1 ,I− Z −S t ⟩ + ⟨ C t 2 , J t+1 − Z ⟩ + ⟨ C t 3 ,Q t − Z ⟩ + µ t 2 ( J t+1 − Z 2 F + I− Z −S t 2 F + Q t − Z 2 F ) 这相当于 L = min Z λ1 2 ∥Z − R∥ 2 F + µ t 2 ( I− Z −S t + C t 1 µ t 2 F + J t+1 − Z + C t 2 µ t 2 F + Q t − Z + C t 3 µ t 2 F ) (13) R = [Y,0n(N−n)]⊙ Z t 其中 。通过推导 ∂L/ ∂Z = 0 ，可 以得到 Z 的最优解，式 (13) 的闭式解为 Z t+1 = [(2+ λ1 µ t )I+ K] (−1)( λ1 µ t R+U1 +U2 +U3) (14) U1 = I−S t + C t 1 µ t U2 = J t+1 + C t 2 µ t U3 = Q t + C t 3 µ 其中 t ， ， 。 更新 J 当固定其他变量时，式 (12) 的目标 函数可以表示为 J 的函数，即 J t+1 = argmin J ∥J∥∗ + ⟨ C t 2 , J − Z t ⟩ + µ t 2 J − Z t 2 F = ∥J∥∗ + µ t 2 J − ( Z t − C t 2 µ t ) 2 F 通过使用奇异值阈值算子 (见定义 3)，可以得 到一个封闭形式的解决方案，即 J t+1 = Γ1/µt(Z t − C t 2 µ t ) = US 1/µt(Σ)V T (15) UΣV T (Z t − C t 2 µ t ) S 1/µ 式中： 是 的奇异值分解； t(·) 是 软阈值算子[7] ，定义为 S λ(x) = x−λ , x > λ x+λ , x < λ 0 , −λ < x < λ 更新 Q 当固定其他变量时，式 (12) 的目标 函数可以表示为 Q 的函数，即 L = min Q λ2∥D⊙Q∥1 + µ t 2 Q− ( Z t+1 − C t 3 µ t ) 2 F (16) n×N 可以通过逐元素的方法进行更新。显然， 式 (16) 可以等效为解决 个子问题。对于第 i 行 第 j 列元素 Kij，式 (16) 的最优解是 Q t+1 i j = argmin Qi j λ2 Di j Qi j + µ t 2 (Qi j − Mi j) 2 = S λ2 Di j µ t (Mi j) (17) ·1212· 智 能 系 统 学 报 第 14 卷
第6期 王中元，等：低秩分块矩阵的核近似 ·1213· 更新S 当固定其他变量时，式(12)的目标 N非常大时，LBKA的时间复杂度会很高。特别 函数可以表示为S的函数，即 是计算矩阵J∈Rw的SVD分解需要O(n2NN>m) L=min 438(S)++ 的复杂度。在这里需要注意的是，由于要计算矩 2 阵的逆，迭代更新Z时需要O㎡2+n2d)时间，其 然后令「=I-ZI- 则S的第i行为 中d是样本维数。步骤3的时间复杂度是OW。 rl-ri 因此，LBKA的总时间复杂度为O(2m2N+n2d+nW, Irl,>s 其中k是迭代次数。 S+(i,)= (18) 相比之下，基于稀疏表示的分类方法（如 0 rs名 SRC和LatLRR)的时间复杂度是On2(N-n)d,这 其中r是矩阵T的第i行。 要比LBKA慢很多。LRLRUSI和LRRRU6等回归 在优化变量J、Z、Q和S之后，ADMM算法 方法的计算复杂度为O(nd+md,比LBKA快一 还需要更新拉格朗日乘子C、C2、C以及参数山， 点，但计算精度比LBKA低。基于低秩和稀疏表 以便更快地收敛。 示的方法（如RPCA)需要同时计算特征矩阵的 最后，本文通过谱聚类算法进行聚类，即先通 SVD并求解软阈值问题。LBKA的总体时间复杂 过构造亲和矩阵来找到数据的低维嵌入，然后使 度与低秩稀疏表示方法的总时间大致相同。 用k均值聚类来实现最后的聚类。 4实验结果与分析 3算法的性质分析 4.1实验环境 3.1算法的收敛性分析 本文在两个数据集上分别测试了人脸识别和 为了解决目标函数，即式(10)，本文使用了迭 字符识别两个识别任务，然后与一些最先进的识 代更新ADMM算法，如第2章所示。下面证明 别方法进行比较，包括基于稀疏表示的方法，如 LBKA的收敛性。 LRC刃，基于低秩标准的方法，如RPCA,和传统 定理1LBKA是收敛的。 的分类方法，如支持向量机(SVM,以及块对角 证明经典的ADMM算法主要解决下述问题： 低秩表示方法(block-diagonal low-rank representa- )+hw)） tion,BDLRR) (19) 为了保证LBKA和对比算法在实验中的参数 s.t.Rz+Tw=u 其中R∈Rm,T∈Rm,μ∈RP,f和h是凸函数。 相同，本文使用交叉验证方法重新实现了所有算 可以看出，式(11)是式(19)的一种特殊情 法。因此，本文使用的所有算法都是在相同条件 况。经变换，式(12)可以被转换为式(19)。然后， 下进行测试的，所以实验结果是真实可靠的。 就可以使用ADMM算法以交替方式更新两个原 4.2评估标准 始变量，并迭代地解决式(19)： 本文使用2个常用的度量指标对实验结果进 Z1=argmin L(Z,W,C) 行评估，分别是准确度(Accuracy)和兰德指数 (Rand index): Wtl argminL(Z",W.C) (20) 1)Accuracy(Acc): C+1=C+μ(RZ+1+TW1-U Acc=max-ΣXaX (21) 它与第2章中的算法1有相同的更新步骤。 xn 其中π是n个组的排列，X和X分别是分类准确 因此，式(11)是经典ADMM问题的一个特殊情 的样本和所有测试样本，如果点j属于簇1则它们 况。算法1中所提出的优化算法相当于两块 的第i个条目等于1，否则为0。 ADMM,它的收敛性在理论上得以证明。 2)Rand index(RI): 3.2算法的复杂度分析 TP+TN 定理2根据第2章可以看出LBKA的总时 RI=TP+TN+FP+F而 (22) 间复杂度为O.(2m2N+d+nW),其中n为训练样 其中，TN表示不同类样本的被分到不同个集合， 本数，N为样本总数，d为样本维数，k为迭代次数。 FN表示同一类样本的被分到不同个集合。 证明算法1的主要过程在第二节算法迭代 4.3人脸识别 的前3步给出，因为需要进行奇异值分解(SVD) 在本节中，本文使用扩展YaleB的面部图像数 和矩阵运算。因此，当训练样本数n和样本总数 据集进行实验
更新 S 当固定其他变量时，式 (12) 的目标 函数可以表示为 S 的函数，即 L = min S λ3g(S)++ µ t 2 S− ( I− Z t+1 − C t 1 µ t ) 2 F Γ = I− Z t+1 − C t 1 µ 然后令 t ，则 S t+1 的第 i 行为 S t+1 (i,;) = Γ i 2 − λ3 µ t ∥Γi∥2 Γ i if Γ i 2 > λ3 µ t 0 if Γ i 2 ⩽ λ3 µ t (18) Γ i 其中 是矩阵 Γ 的第 i 行。 µ 在优化变量 J、Z、Q 和 S 之后，ADMM 算法 还需要更新拉格朗日乘子 C1、C2、C3 以及参数 ， 以便更快地收敛。 最后，本文通过谱聚类算法进行聚类，即先通 过构造亲和矩阵来找到数据的低维嵌入，然后使 用 k 均值聚类来实现最后的聚类。 3 算法的性质分析 3.1 算法的收敛性分析 为了解决目标函数，即式 (10)，本文使用了迭 代更新 ADMM 算法，如第 2 章所示。下面证明 LBKA 的收敛性。 定理 1 LBKA 是收敛的。 证明 经典的 ADMM 算法主要解决下述问题： min z∈Rn ,w∈Rm f(z)+h(w) s.t. Rz+Tw = µ (19) R ∈ R p×n ,T ∈ R p×m ,µ ∈ R 其中 p，f 和 h 是凸函数。 可以看出，式 (11) 是式 (19) 的一种特殊情 况。经变换，式 (12) 可以被转换为式 (19)。然后， 就可以使用 ADMM 算法以交替方式更新两个原 始变量，并迭代地解决式 (19)： Z t+1 = argmin Z∈Rn×N Lµ(Z,Wt ,C t ) Wt+1 = argmin W∈Rm×N Lµ(Z t+1 ,W,C t ) C t+1 = C t +µ(RZt+1 +TWt+1 −U) (20) 它与第 2 章中的算法 1 有相同的更新步骤。 因此，式 (11) 是经典 ADMM 问题的一个特殊情 况。算 法 1 中所提出的优化算法相当于两 块 ADMM，它的收敛性在理论上得以证明。 3.2 算法的复杂度分析 Ok(2n 2N +n 2d +nN) 定理 2 根据第 2 章可以看出 LBKA 的总时 间复杂度为 ，其中 n 为训练样 本数，N 为样本总数，d 为样本维数，k 为迭代次数。 证明 算法 1 的主要过程在第二节算法迭代 的前 3 步给出，因为需要进行奇异值分解 (SVD) 和矩阵运算。因此，当训练样本数 n 和样本总数 J ∈ R n×N O(n 2N)(N > n) O(n 2N +n 2d) O(nN) Ok(2n 2N +n 2d +nN) N 非常大时，LBKA 的时间复杂度会很高。特别 是计算矩阵 的 SVD 分解需要 的复杂度。在这里需要注意的是，由于要计算矩 阵的逆，迭代更新 Z 时需要 时间，其 中 d 是样本维数。步骤 3 的时间复杂度是 。 因此，LBKA 的总时间复杂度为 ， 其中 k 是迭代次数。 O(n 2 (N −n)d) O(nd +n 2d) 相比之下，基于稀疏表示的分类方 法 (如 SRC 和 LatLRR) 的时间复杂度是 ，这 要比 LBKA 慢很多。LRLR[15] 和 LRRR[16] 等回归 方法的计算复杂度为 ，比 LBKA 快一 点，但计算精度比 LBKA 低。基于低秩和稀疏表 示的方法 (如 RPCA) 需要同时计算特征矩阵的 SVD 并求解软阈值问题。LBKA 的总体时间复杂 度与低秩稀疏表示方法的总时间大致相同。 4 实验结果与分析 4.1 实验环境 本文在两个数据集上分别测试了人脸识别和 字符识别两个识别任务，然后与一些最先进的识 别方法进行比较，包括基于稀疏表示的方法，如 LRC[17] ，基于低秩标准的方法，如 RPCA，和传统 的分类方法，如支持向量机 (SVM)[18] ，以及块对角 低秩表示方法 (block-diagonal low-rank representation, BDLRR)[5]。 为了保证 LBKA 和对比算法在实验中的参数 相同，本文使用交叉验证方法重新实现了所有算 法。因此，本文使用的所有算法都是在相同条件 下进行测试的，所以实验结果是真实可靠的。 4.2 评估标准 本文使用 2 个常用的度量指标对实验结果进 行评估，分别是准确度 (Accuracy) 和兰德指数 (Rand index)： 1)Accuracy(Acc): Acc = max π 1 n Σi jX t π(i)jXi j (21) 其中 π 是 n 个组的排列，X t 和 X 分别是分类准确 的样本和所有测试样本，如果点 j 属于簇 i 则它们 的第 i 个条目等于 1，否则为 0。 2)Rand index(RI): RI = TP+TN TP+TN+FP+FN (22) 其中，TN 表示不同类样本的被分到不同个集合， FN 表示同一类样本的被分到不同个集合。 4.3 人脸识别 在本节中，本文使用扩展 YaleB[5] 面部图像数 据集进行实验。 第 6 期 王中元，等：低秩分块矩阵的核近似 ·1213·
·1214· 智能系统学报 第14卷 扩展的YaleB数据库：由38个人的2414个 数据库的一个小子集Char74K-15,其中包含15个 人脸图像组成，每个人有59~64个亮度不同的图 训练样本和15个测试样本。 像。在实验过程中，随机选择其中的20、25、30、35 表2扩展YaleB数据库中不同数量训练集中不同方法 个图像作为训练集，其余的作为测试集进行实验。 的兰德指数(R 图2为LBKA获得的扩展YaleB数据库的数 Table 2 Rand index of different methods of different numbers of training samples on the Extended 据表示，从中可以看出获得的矩阵为对角分块结 YaleB database(RI) % 构。表1和表2分别是扩展的YaleB数据库中不 训练集数量 同算法的识别精度和兰德指数。从中可以看出， 算法 在使用不同数量的训练集进行实验时，LBKA都 20 25 30 35 能得到最好的识别结果。而且随着样本数量的增 LRC 91.25 92.63 93.35 93.76 加，LBKA的识别精度也随之逐渐提高。 RPCA 94.61 94.84 95.75 95.96 SVM 93.28 95.51 92.65 96.96 BDLRR 96.34 97.11 96.37 97.03 LBKA 97.82 98.53 97.89 99.11 表3和表4列出了LBKA和其他字符识别方 法的识别准确度和兰德指数，从中可以看出，LB KA识别的准确度和兰德指数都是最高的。 表3场景角色数据库上不同方法的准确度 Table 3 Recognition accuracies of different methods onthe scene character database. % 图2LBKA获得的扩展YaleB数据库的数据表示 算法 准确度 Fig.2 Data representation of the Extended YaleB data- CoHOG 63 baseobtained by LBKA PHOG 65 表1扩展YaleB数据库中不同数量训练集中不同方法 MLFP 64 的准确度(Acc±std RTPD 67 Table 1 Recognition accuracies of different methods of BDLRR 70 different numbers of training samples on the Extended YaleB database (Acc+std) LBKA 13 % 训练集数量 表4场景角色数据库上不同方法的兰德指数 算法 Table 4 Rand index of different methods on the 20 25 30 35 scenecharacter database. % LRC 92.15±0.9593.55±0.6594.55±0.6895.4940.55 算法 兰德指数 RPCA93.58±0.6195.51±0.36 96.70±0.4696.96±0.49 CoHOG 60 SVM 92.81±0.6895.20±0.44 96.11±0.41 96.70±0.69 PHOG 63 BDLRR94.67±0.3195.79±0.2996.46±0.1596.81±0.14 MLFP 61 LBKA97.46±0.6798.22±0.4298.67±0.4699.26±0.29 RTPD 68 BDLRR 72 4.4字符识别 LBKA 74 本文选取Char74K场景人物图像数据集来 进行实验。在以往的模式识别任务中，由于场景 4.5 实验分析 图像十分复杂，很难将想要识别的文本分离出 首先，与两种数据集上的对比算法相比，LB- 来，而LBKA中对类内类外的处理有助于对场景 KA进行模式识别时更加准确。 中字符进行提取。本文将LBKA与其他先进的字 其次，LBKA比现有的识别算法更准确，这说 符识别算法进行对比，包括CoHOG9、RTPD2 明扩大了对角块和非对角块之间的差异的同时增 PHOGP、MLFP2和BDLRR。 强了相关数据表示，能够获得更好的识别效果。 Char74K数据库：该数据库总共包含7万4千 第三，LBKA在识别数量有限的样本时比其 幅图像，所以叫Chars?74K。本文主要关注其中英 它对比算法都好。主要原因是LBKA具有稀疏， 语字符和数字的识别。本文在实验中只使用了原 低秩和分块三大特性。低秩可以有效地挖掘数据
扩展的 YaleB 数据库：由 38 个人的 2 414 个 人脸图像组成，每个人有 59~64 个亮度不同的图 像。在实验过程中，随机选择其中的 20、25、30、35 个图像作为训练集，其余的作为测试集进行实验。 图 2 为 LBKA 获得的扩展 YaleB 数据库的数 据表示，从中可以看出获得的矩阵为对角分块结 构。表 1 和表 2 分别是扩展的 YaleB 数据库中不 同算法的识别精度和兰德指数。从中可以看出， 在使用不同数量的训练集进行实验时，LBKA 都 能得到最好的识别结果。而且随着样本数量的增 加，LBKA 的识别精度也随之逐渐提高。 图 2 LBKA 获得的扩展 YaleB 数据库的数据表示 Fig. 2 Data representation of the Extended YaleB databaseobtained by LBKA 表 1 扩展 YaleB 数据库中不同数量训练集中不同方法 的准确度 (Acc±std) Table 1 Recognition accuracies of different methods of different numbers of training samples on the Extended YaleB database (Acc±std) % 算法 训练集数量 20 25 30 35 LRC 92.15±0.95 93.55±0.65 94.55±0.68 95.49±0.55 RPCA 93.58±0.61 95.51±0.36 96.70±0.46 96.96±0.49 SVM 92.81±0.68 95.20±0.44 96.11±0.41 96.70±0.69 BDLRR 94.67±0.31 95.79±0.29 96.46±0.15 96.81±0.14 LBKA 97.46±0.67 98.22±0.42 98.67±0.46 99.26±0.29 4.4 字符识别 本文选取 Char74K 场景人物图像数据集[5] 来 进行实验。在以往的模式识别任务中，由于场景 图像十分复杂，很难将想要识别的文本分离出 来，而 LBKA 中对类内类外的处理有助于对场景 中字符进行提取。本文将 LBKA 与其他先进的字 符识别算法进行对比，包括 CoHOG[19] 、RTPD[20] ， PHOG[21] 、MLFP[22] 和 BDLRR[5]。 Char74K 数据库：该数据库总共包含 7 万 4 千 幅图像，所以叫 Chars74K。本文主要关注其中英 语字符和数字的识别。本文在实验中只使用了原 数据库的一个小子集 Char74K-15，其中包含 15 个 训练样本和 15 个测试样本。 表 2 扩展 YaleB 数据库中不同数量训练集中不同方法 的兰德指数 (RI) Table 2 Rand index of different methods of different numbers of training samples on the Extended YaleB database(RI) % 算法 训练集数量 20 25 30 35 LRC 91.25 92.63 93.35 93.76 RPCA 94.61 94.84 95.75 95.96 SVM 93.28 95.51 92.65 96.96 BDLRR 96.34 97.11 96.37 97.03 LBKA 97.82 98.53 97.89 99.11 表 3 和表 4 列出了 LBKA 和其他字符识别方 法的识别准确度和兰德指数，从中可以看出，LBKA 识别的准确度和兰德指数都是最高的。 表 3 场景角色数据库上不同方法的准确度 Table 3 Recognition accuracies of different methods onthe scene character database. % 算法 准确度 CoHOG 63 PHOG 65 MLFP 64 RTPD 67 BDLRR 70 LBKA 73 表 4 场景角色数据库上不同方法的兰德指数 Table 4 Rand index of different methods on the scenecharacter database. % 算法 兰德指数 CoHOG 60 PHOG 63 MLFP 61 RTPD 68 BDLRR 72 LBKA 74 4.5 实验分析 首先，与两种数据集上的对比算法相比，LBKA 进行模式识别时更加准确。 其次，LBKA 比现有的识别算法更准确，这说 明扩大了对角块和非对角块之间的差异的同时增 强了相关数据表示，能够获得更好的识别效果。 第三，LBKA 在识别数量有限的样本时比其 它对比算法都好。主要原因是 LBKA 具有稀疏， 低秩和分块三大特性。低秩可以有效地挖掘数据 ·1214· 智 能 系 统 学 报 第 14 卷
第6期 王中元，等：低秩分块矩阵的核近似 ·1215· 相关的基础结构，并且揭示数据矩阵的全局潜在 结构；稀疏能够寻找最近的数据子空间；块对角 10 表示能够发掘数据内在结构并阐明数据点的最近 子空间。 650 随着迭代次数的增加LBKA的相对误差在减 小，并且总值在图3所示的60次迭代后基本没有 0 变化，这验证了LBKA具有收敛性。图4表示 100 LBKA关于参数和的性能变化。可以看出，LB- 0 KA对和的变化值不敏感。更具体的说，当参数 0.0 00u0.113,1030100 处于一个合理范围内时，LBKA准确度较高，这说 (a)Extended YaleB 明增加类内类外约束是十分有必要的。 0.30 0.25 0.20 00000000 0.10 10 0.05 0102030405060708090100 0020115,1050100 迭代次数 (b)Char 74K-15 (a)Extended YaleB 图4入1、1对两种数据集的影响 0.6r Fig.4 The impact of and 4 on the two data sets 0.5 3)本文通过实验证明了LBKA在人脸识别和 字符识别等领域的效果比传统识别算法更好，接 下来可以研究其在回归、聚类、排序等方面的应用。 0.2 参考文献： 0.1 [1]雷恒鑫，刘惊雷.基于行列联合选择矩阵分解的偏好特 0102030405060708090100 征提取).模式识别与人工智能，2017,30(3)：279-288. 迭代次数 (b)Char74K-15 LEI Hengxin,LIU Jinglei.Preference feature extraction based on column union row matrix decomposition[J].Pat- 图3LBKA在不同数据库上的收敛曲线 tern recognition and artificial intelligence,2017,30(3): Fig.3 Convergence curves of LBKA on different databases 279-288. 5结束语 [2]张恒敏，杨健，郑玮.低秩矩阵近似与优化问题研究进展 [.模式识别与人工智能，2018,31(1)少23-36 本文给出了低秩分块矩阵的相关定义，说明 ZHANG Hengmin,YANG Jian,ZHENG Wei.Research 了矩阵分解的应用。分析了核近似的优点，并提 progress of low-rank matrix approximation and optimiza- 出了低秩分块矩阵核近似的方法。最后将该方法 tion problem[J].Pattern recognition and artificial intelli- 在人脸识别和字符识别中进行比较。结果表明： gence,2018,31(1:23-36. 所提出的低秩分块矩阵分解算法在收敛速度和近 [3]CHIANG K Y.DHILLON I S,HSIEH C J.Using side in- 似精度上都具有一定的优势。未来工作包括： formation to reliably learn low-rank matrices from missing 1)从矩阵的核近似出发，对原有的子空间聚 and corrupted observations[].Journal of machine learning research,2018.19(76):1-35 类算法进行改进，提高分块的速度和准确性，从 [4]LU Canyi,FENG Jiashi,LIN Zhouchen.Subspace cluster- 而提升算法找到全局最优解的能力。 ing by block diagonal representation[J].IEEE transactions 2)通过与多种矩阵分解算法的比较，观察提 on pattern analysis and machine intelligence,2019,41(2): 出的低秩分块矩阵的核近似算法的表现，进一步 487-501. 分析算法的可行性。 [5]ZHANG Zheng,XU Yong,SHAO Ling.Discriminative
相关的基础结构，并且揭示数据矩阵的全局潜在 结构；稀疏能够寻找最近的数据子空间；块对角 表示能够发掘数据内在结构并阐明数据点的最近 子空间。 随着迭代次数的增加 LBKA 的相对误差在减 小，并且总值在图 3 所示的 60 次迭代后基本没有 变化，这验证了 LBKA 具有收敛性。图 4 表示 LBKA 关于参数和的性能变化。可以看出，LBKA 对和的变化值不敏感。更具体的说，当参数 处于一个合理范围内时，LBKA 准确度较高，这说 明增加类内类外约束是十分有必要的。 0 10 20 30 40 50 60 70 80 90 100 0.05 0.10 0.15 0.20 0.25 迭代次数 (a) Extended YaleB 相对误差 0 10 20 30 40 50 60 70 80 90 100 0.1 0.2 0.3 0.4 0.5 迭代次数 (b) Char74K-15 相对误差 0.6 0.30 图 3 LBKA 在不同数据库上的收敛曲线 Fig. 3 Convergence curves of LBKA on different databases 5 结束语 本文给出了低秩分块矩阵的相关定义，说明 了矩阵分解的应用。分析了核近似的优点，并提 出了低秩分块矩阵核近似的方法。最后将该方法 在人脸识别和字符识别中进行比较。结果表明， 所提出的低秩分块矩阵分解算法在收敛速度和近 似精度上都具有一定的优势。未来工作包括： 1) 从矩阵的核近似出发，对原有的子空间聚 类算法进行改进，提高分块的速度和准确性，从 而提升算法找到全局最优解的能力。 2) 通过与多种矩阵分解算法的比较，观察提 出的低秩分块矩阵的核近似算法的表现，进一步 分析算法的可行性。 100 80 60 Acc/% 40 20 0 100 5010 5 1 100 50 10 5 0.1 1 0.01 0.1 λ2 λ1 0.01 (a) Extended YaleB 70 60 50 Acc/%40 20 10 30 0 100 5010 5 1 100 50 10 5 0.1 1 0.02 0.1 λ2 λ1 0.02 (b) Char 74K-15 图 4 λ1、λ1 对两种数据集的影响 Fig. 4 The impact of λ1 and λ2 on the two data sets 3) 本文通过实验证明了 LBKA 在人脸识别和 字符识别等领域的效果比传统识别算法更好，接 下来可以研究其在回归、聚类、排序等方面的应用。 参考文献： 雷恒鑫, 刘惊雷. 基于行列联合选择矩阵分解的偏好特 征提取 [J]. 模式识别与人工智能, 2017, 30(3): 279–288. LEI Hengxin, LIU Jinglei. Preference feature extraction based on column union row matrix decomposition[J]. Pattern recognition and artificial intelligence, 2017, 30(3): 279–288. [1] 张恒敏, 杨健, 郑玮. 低秩矩阵近似与优化问题研究进展 [J]. 模式识别与人工智能, 2018, 31(1): 23–36. ZHANG Hengmin, YANG Jian, ZHENG Wei. Research progress of low-rank matrix approximation and optimization problem[J]. Pattern recognition and artificial intelligence, 2018, 31(1): 23–36. [2] CHIANG K Y, DHILLON I S, HSIEH C J. Using side information to reliably learn low-rank matrices from missing and corrupted observations[J]. Journal of machine learning research, 2018, 19(76): 1–35. [3] LU Canyi, FENG Jiashi, LIN Zhouchen. Subspace clustering by block diagonal representation[J]. IEEE transactions on pattern analysis and machine intelligence, 2019, 41(2): 487–501. [4] [5] ZHANG Zheng, XU Yong, SHAO Ling. Discriminative 第 6 期 王中元，等：低秩分块矩阵的核近似 ·1215·
·1216· 智能系统学报 第14卷 block-diagonal representation learning for image recogni- ing[J].IEEE transactions on knowledge and data engin- tion[J].IEEE transactions on neural networks and learning eering,201l,23(9:1406-1418. systems,2018,29(7):3111-3125 [17]NASEEM I.TOGNERI R,BENNAMOUN M.Linear re- [6]WEI C P.CHEN C F.WANG Y C F.Robust face recogni- gression for face recognition[J].IEEE transactions on pat- tion with structurally incoherent low-rank matrix decom- tern analysis and machine intelligence,2010,32(11): position[J].IEEE transactions on image processing,2014, 2106-2112. 23(8):3294-3307. [18]丁立中，廖士中.KMA-a:一个支持向量机核矩阵的近 [7]NI Yuzhao,SUN Ju,YUAN Xiaotong,et al.Robust low- 似计算算法J].计算机研究与发展，2012,49(4)： rank subspace segmentation with semidefinite guarantees 746-753. [C]//Proceedings of 2010 IEEE International Conference DING Lizhong,LIAO Shizhong.KMA-a:a kernel mat- on Data Mining Workshops.Sydney,NSW,Australia, rix approximation algorithm for support vector 2010:1179-1188. machines[J].Journal of computer research and develop- [8]LEE K C.HO J,KRIEGMAN D J.Acquiring linear sub- ment,2012,49(4)746-753. spaces for face recognition under variable lighting[J].IEEE [19]TIAN Shangxuan,LU Shijian,SU Bolan.Scene text re- transactions on pattern analysis and machine intelligence, cognition using co-occurrence of histogram of oriented 2005,27(5):684-698. gradients[C]//Proceedings of the 12th International Con- [9]CANDES E J,LI Xiaodong,MA Yi.Robust principal ference on Document Analysis and Recognition.Wash- component analysis?[J].Journal of the ACM,2011,58(3): ington,DC,USA,2013:912-916. 11. [20]PHAN T Q,SHIVAKUMARA P,TIAN S X.Recogniz- [10]LIU Guangcan,LIN Zhouchen,YAN Shuicheng.Robust ing text with perspective distortion in natural scenes[C]// recovery of subspace structures by low-rank representa- Proceedings of 2013 IEEE International Conference on tion[J].IEEE transactions on pattern analysis and ma- Computer Vision.Sydney,NSW,Australia,2013: 569-576. chine intelligence,2013,35(1):171-184. [11]CHEN Yudong,JALALI A,SANGHAVI S,et al.Clus- [21]TAN Zhirong,TIAN Shangxuan,TAN C L.Using pyr- tering partially observed graphs via convex optimization amid of histogram of oriented gradients on natural scene [J].The journal of machine learning research,2014, text recognition[C]//Proceedings of 2014 IEEE Interna- 15(1):2213-2238. tional Conference on Image Processing.Paris,France, 2014:2629-2633. [12]LIN Zhouchen,CHEN Minming,MA Yi.The augmented [22]LEE C Y,BHARDWAJ A,DI Wei,et al.Region-based lagrange multiplier method for exact recovery of corrup- discriminative feature pooling for scene text recognition ted low-rank matrices[J].arXiv preprint arXiv:1009. [C]//Proceedings of 2014 IEEE Conference on Computer 5055,2010. Vision and Pattern Recognition.Columbus,OH,USA, [13]LU Canyi,FENG Jiashi,YAN Shuicheng.A unified al- 2014:4050-4057 ternating direction method of multipliers by majorization minimization[J].IEEE transactions on pattern analysis 作者简介： and machine intelligence,2018,40(3):527-541. 王中元.男.1996年生，硕士研究 [14]刘松华，张军英，丁彩英.核矩阵列相关低秩近似分解 生，主要研究方向为核方法与矩阵分解。 算法).模式识别与人工智能，2011,24(6776-782. LIU Songhua,ZHAGN Junying,DING Caiying.Low- Rank approximation and decomposition for kernel matrix based on column correlation[J].Pattern recognition and artificial intelligence,2011,24(6):776-782 [15]YIN Ming,GAO Junbin,LIN Zhouchen.Laplacian regu- 刘惊雷，男，1970年生，教授，博 土，主要研究方向为人工智能和理论 larized low-rank representation and its applications[J]. 计算机科学。主持国家自然科学基金 IEEE transactions on pattern analysis and machine intelli- 面上项目、山东省自然科学基金面上 gence,2016,38(3):504-517. 项目各1项。发表学术论文40余篇。 [16]HE Xiaofei,CAI Deng,SHAO Yuanlong,et al.Lapla- cian regularized Gaussian mixture model for data cluster-
block-diagonal representation learning for image recognition[J]. IEEE transactions on neural networks and learning systems, 2018, 29(7): 3111–3125. WEI C P, CHEN C F, WANG Y C F. Robust face recognition with structurally incoherent low-rank matrix decomposition[J]. IEEE transactions on image processing, 2014, 23(8): 3294–3307. [6] NI Yuzhao, SUN Ju, YUAN Xiaotong, et al. Robust lowrank subspace segmentation with semidefinite guarantees [C]//Proceedings of 2010 IEEE International Conference on Data Mining Workshops. Sydney, NSW, Australia, 2010: 1179–1188. [7] LEE K C, HO J, KRIEGMAN D J. Acquiring linear subspaces for face recognition under variable lighting[J]. IEEE transactions on pattern analysis and machine intelligence, 2005, 27(5): 684–698. [8] CANDÈS E J, LI Xiaodong, MA Yi. Robust principal component analysis?[J]. Journal of the ACM, 2011, 58(3): 11. [9] LIU Guangcan, LIN Zhouchen, YAN Shuicheng. Robust recovery of subspace structures by low-rank representation[J]. IEEE transactions on pattern analysis and machine intelligence, 2013, 35(1): 171–184. [10] CHEN Yudong, JALALI A, SANGHAVI S, et al. Clustering partially observed graphs via convex optimization [J]. The journal of machine learning research, 2014, 15(1): 2213–2238. [11] LIN Zhouchen, CHEN Minming, MA Yi. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[J]. arXiv preprint arXiv: 1009. 5055, 2010. [12] LU Canyi, FENG Jiashi, YAN Shuicheng. A unified alternating direction method of multipliers by majorization minimization[J]. IEEE transactions on pattern analysis and machine intelligence, 2018, 40(3): 527–541. [13] 刘松华, 张军英, 丁彩英. 核矩阵列相关低秩近似分解 算法 [J]. 模式识别与人工智能, 2011, 24(6): 776–782. LIU Songhua, ZHAGN Junying, DING Caiying. LowRank approximation and decomposition for kernel matrix based on column correlation[J]. Pattern recognition and artificial intelligence, 2011, 24(6): 776–782. [14] YIN Ming, GAO Junbin, LIN Zhouchen. Laplacian regularized low-rank representation and its applications[J]. IEEE transactions on pattern analysis and machine intelligence, 2016, 38(3): 504–517. [15] HE Xiaofei, CAI Deng, SHAO Yuanlong, et al. Laplacian regularized Gaussian mixture model for data cluster- [16] ing[J]. IEEE transactions on knowledge and data engineering, 2011, 23(9): 1406–1418. NASEEM I, TOGNERI R, BENNAMOUN M. Linear regression for face recognition[J]. IEEE transactions on pattern analysis and machine intelligence, 2010, 32(11): 2106–2112. [17] 丁立中, 廖士中. KMA-α: 一个支持向量机核矩阵的近 似计算算法 [J]. 计算机研究与发展, 2012, 49(4): 746–753. DING Lizhong, LIAO Shizhong. KMA-α: a kernel matrix approximation algorithm for support vector machines[J]. Journal of computer research and development, 2012, 49(4): 746–753. [18] TIAN Shangxuan, LU Shijian, SU Bolan. Scene text recognition using co-occurrence of histogram of oriented gradients[C]//Proceedings of the 12th International Conference on Document Analysis and Recognition. Washington, DC, USA, 2013: 912–916. [19] PHAN T Q, SHIVAKUMARA P, TIAN S X. Recognizing text with perspective distortion in natural scenes[C]// Proceedings of 2013 IEEE International Conference on Computer Vision. Sydney, NSW, Australia, 2013: 569–576. [20] TAN Zhirong, TIAN Shangxuan, TAN C L. Using pyramid of histogram of oriented gradients on natural scene text recognition[C]//Proceedings of 2014 IEEE International Conference on Image Processing. Paris, France, 2014: 2629–2633. [21] LEE C Y, BHARDWAJ A, DI Wei, et al. Region-based discriminative feature pooling for scene text recognition [C]//Proceedings of 2014 IEEE Conference on Computer Vision and Pattern Recognition. Columbus, OH, USA, 2014: 4050–4057. [22] 作者简介： 王中元，男，1996 年生，硕士研究 生，主要研究方向为核方法与矩阵分解。 刘惊雷，男，1970 年生，教授，博 士，主要研究方向为人工智能和理论 计算机科学。主持国家自然科学基金 面上项目、山东省自然科学基金面上 项目各 1 项。发表学术论文 40 余篇。 ·1216· 智 能 系 统 学 报 第 14 卷