Liu, Y., Li, X., Liu, C., et al., Structure-Constrained Low-Rank and Partial Sparse Representation with Sample Selection for image classification. Pattern Recognition, 2016. 59: p. 5 - 13. 本文是这篇 Pattern Recognition 期刊论文的笔记，主要是对文中的理论方法进行展开详解。本人学术水平有限，文中如有错误之处，敬请指正。
摘要： 此文提出了一个结构约束低秩、部分稀疏表示算法，用于图像分类。首先，结构约束低秩字典学习（Structure-Constrained Low-Rank Dictionary Learning, SCLRDL）算法被提出，将结构约束和低秩约束加入到系数矩阵中。其次，假设测试样本的系数是稀疏的，并与训练样本的表示是相关联的，提出了一个低秩和部分稀疏表示（Low-Rank and Partial Sparse Representation, LRPSR）算法，将训练样本和测试样本结合起来形成一个新的数据矩阵，再找出一个低秩、稀疏的数据表示，通过一个学习到的字典。最后，设计一个样本筛选（Sample Selection）步骤，来加速 LRPSR 。
识别图像和视频中的物体所属的类别是对于人来说很简单的任务，但是被证明对于计算机是很困难的。目前很多的研究中，稀疏表示（sparse representation）和低秩矩阵分解（low-rank matrix factorization）被大量关注，也提出了许多的图像分类的算法。
稀疏表示是用一个基或超完备字典的元素的线性组合来近似一个已知的信号 1 。其在人脸识别的应用上效果很不错。超完备字典在稀疏表示应用的性能表现上有很重要的作用 2 。一些字典学习的算法提出，来学习一个简洁、判别性的字典 3 。
低秩矩阵分解 4，将已知的矩阵分解为一个低秩的部分和一个稀疏的部分。Yang et al. 提出了 FDDL 5，基于 Fisher 准则，将整个字典分成按类别的子字典，并将它们分别优化。Liu et al. 提出了 BDDL 6，也是将字典分成各个子字典，并加入了一个字典相关项。Ma et al. 提出了 DLRD_SR 7，将低秩约束加入于字典，基于训练样本的相关性。Zhang et al. 8 提出了结构低秩表示算法。其优化字典和系数时，同时加入了稀疏和低秩的约束，但是在测试阶段，需要多个样本来计算稀疏矩阵的秩，这方法不实用。（这篇会议论文，本人看过，与这里描述的不一致，其测试方法采用最近邻分类，可以一个一个样本预测，也可以多个样本预测）
此文提出一种新的图像分类的算法，用于学习图像的字典和系数，并加上稀疏和低秩的约束。
在训练阶段，此文提出了 SCLRDL，将字典分成每个类别的子字典，减小字典之间的相关性，约束系数中非零项的元素的位置，并约束系数矩阵的秩。
在测试阶段，此文设计了 LRPSR，将测试样本和训练样本组合起来，使得算法更加实用。
为了加速 LRPSR，设计了样本筛选步骤，减少数据矩阵中一些多余的训练样本，降低计算成本。
稀疏表示，低秩矩阵分解相关，略
从这里开始，原文的符号有许多错误，上下文不一致。本文均已修改为正确形式。
大部分的字典学习算法在学习时，一起考虑所有类别的样本。而此文的 SCLRDL 算法学习按类别的子字典，并加入字典相关项，加强字典的判别性。
训练阶段，给予训练数据 {X}Ni=1 ，其中 N 是训练样本的个数，可以被分为多个子集 {Xj}Cj=1，其中 C 是类别的数量，Xj 是第 j 个类别的训练样本的子集。研究表明，如果结合稀疏和低秩的约束，可以提升分类的性能。首先给出如下的 SCLRDL 的目标函数： argminD,Z,E α||Z||∗ β||E||ℓ δ||Z||1,s.t. X=DZ E,(1) 其中 α,β,δ 是权衡参数， ||E||ℓ 表示不同的噪声，比如平方 Frobenius 范数 ||⋅||2F 表示高斯噪声， ℓ1 范数表示随机噪声。 ||Z||∗ 和 ||Z||1 迫使稀疏矩阵 Z 低秩、稀疏的性质。
研究发现有一些属于不同类别的样本也是相似的，比如人脸识别中。所以系数矩阵的全局约束可能不合适。此文通过将训练样本、系数矩阵、和误差矩阵，都按类别分开，各自进行约束。将目标函数重写为
argminD,Zi,Ei ∑i=1Cα||Zi||∗+∑i=1Cβ||Ei||ℓ+∑i=1Cδ||Zi||1s.t. Xi=DZi+Ei.(2) 这里强调每一个类别的系数矩阵 Zi 是低秩、稀疏的，而不是直接约束整体的系数矩阵 Z 。关联每一个字典元素到一个标签，即一个监督性字典，会提升算法的性能。比如
Xi=DZi=D1Z1i+D2Z2i+⋯+DCZCi=[D1 D2 ⋯ DC]⎡⎣⎢⎢⎢⎢⎢Z1iZ2i⋮ZCi⎤⎦⎥⎥⎥⎥⎥,(3) 其中 Zji 是 Zi 的第 j 行部分，对应子字典 Dj。很自然的假设是，来自第 i 类的样本 Xi 主要由 Di 重建，即 Xi=DZi=D1Z1i+D2Z2i+⋯+DCZCi≈DiZii.(4) 而且，这表明了 Zi 的稀疏性，所以这里忽略项 ∑Ci=1δ||Zi||1 ，加入一个额外的约束。目标函数重写为 argminD,Zi,Ei ∑i=1Cα||Zi||∗+∑i=1Cβ||Ei||ℓs.t. Xi=DZi+Ei, Ωπi(Zi)=0,(5) 其中 Ωπi(Zi)=0 使得 Zi 的所有行为零，除了对应第 i 类的行。为了加强字典的判别性，目标函数中又加入了一个字典相关项 ∑i≠jγ||DTiDj||2F 。 9 中首先介绍了这一项，并尝试保持不同类别的元素之间的正交性。最终的目标函数给出如下
argminD,Zi,Ei ∑i=1Cα||Zi||∗+∑i=1Cβ||Ei||ℓ+∑i≠jγ||DTiDj||2Fs.t. Xi=DZi+Ei, Ωπi(Zi)=0.(6)
优化步骤可以分为两步，并迭代进行。首先对 Zi,Ei 进行更新，固定 D 。加入一个辅助变量 J ，
argminJi,Zi,Ei ∑i=1Cα||Ji||∗+∑i=1Cβ||Ei||ℓs.t. Xi=DZi+Ei, Ji=Zi, Ωπi(Zi)=0.(7) 每一个类别的増广 Lagrangian 函数是 argminJi,Zi,Ei α||Ji||∗+ β||Ei||ℓ+⟨Λ1,Xi−DZi−Ei⟩+⟨Λ2,Zi−Ji⟩+μ2(||Xi−DZi−Ei||2F+||Zi−Ji||2F).(8) 变量可以交替进行更新:对于变量 Ji ，目标函数写为
argminJi α||Ji||∗+⟨Λ2,Zi−Ji⟩+μ2||Zi−Ji||2F=argminJi α||Ji||∗+μ2||Ji−(Zi+Λ2/μ)||2F.(9) 可以使用 singular value thresholding 有效求解 USVT=svd(Zi+Λ2/μ), Ji=USα/μ(S)VT, Sα/μ(x)=sign(x)⋅max{|x|−α/μ,0}.(10)对于变量 Zi ，目标函数写为
argminZi ⟨Λ1,Xi−DZi−Ei⟩+⟨Λ2,Zi−Ji⟩+μ2(||Xi−DZi−Ei||2F+||Zi−Ji||2F).(11) 通过令其导数为零，可以得到 Zi 的表达式 −DTΛ1+Λ2+μ[−DT(Xi−DZi−Ei)+(Zi−Ji)]=0,Zi=(DTD+I)−1(DTXi−DTEi+Ji+(DTΛ1−Λ2)/μ). 接着将约束 Ωπi(Zi)=0 作用于每一个 Zi （原文中并没有明确指出如何实现）。对于变量 Ei ，如果 ||E||ℓ 是 ||E||1 ，目标函数写为
argminEi β||Ei||1+⟨Λ1,Xi−DZi−Ei⟩+μ2||Xi−DZi−Ei||2F,argminEi β||Ei||1+μ2||Ei−(Xi−DZi+Λ1/μ)||2F.(12)(13) 通过 soft-thresholding 或 shrinkage 操作求解 Ei=Sβ/μ(Xi−DZi+Λ1/μ).(14) 如果 ||E||ℓ 是 ||E||2F ，可以直接忽略这个约束，应为误差已经在 ||Xi−DZi||2F 中被考虑到了。更新其他一些参数
Λ1=Λ1+μ(Xi−DZi−Ei), Λ2=Λ2+μ(Zi−Ji), μ=min(ρμ,μmax).(15)在变量 Zi，Ei 更新之后，固定它们，继续更新字典 D ，每一个类别的目标函数（重新考虑）如下 argminDk L(Dk)=argminDk 12||Xk−DkZkk||2F γ2∑i≠k||DTiDk||2F,(16) 其中 Zkk 是字典 Zk 所有行中对应类别 k 的一部分。使用梯度下降法更新 L(Dk)，
DkDk=Dk−τ∇L,=Dk−τ⎛⎝γ∑i≠k(DiDTi)Dk−(Xk−DkZkk)(Zkk)T⎞⎠.(17)(18) 这里 τ 是梯度下降的步长，通过直线搜索求得（搜索令下一步迭代的值最小的步长），步骤为带入 L(Dk−τ∇L) ，求其关于 τ 的梯度为零 ∂L/∂τ=0 ，解得最优的 τ ， τ=−tr(AT∇LZkk)−γ∑i≠ktr(B∇L)||∇LZkk||2F+γ∑i≠k||DTi∇L||2F, A=Xk−DkZkk, B=DTkDiDTi.(19) 原文的公式有错误，Appendix 将给出具体的推导过程。每一次梯度更新之后都要重新计算步长，计算代价很大，真的实用？这里考虑如何计算测试样本的系数。传统的方法，比如 OMP 10，iterative hard threshold 11，fast iterative shrinkage-thresholding algorithm 12，LARS 13 和 SBL 14 都不能很好的利用 SCLRDL 学习到的字典。此文学习到的训练样本的系数是低秩、稀疏的，但是其他一些传统的稀疏编码算法，只考虑了稀疏性约束。15 是一个好的方法，但是不适用于大量的测试样本进行分类（此文的描述与该引用中的方法的描述不符）。
此文设计一个更实用的稀疏编码的算法用于图像分类任务，低秩部分稀疏表示（Low-Rank and Partial Sparse Representation, LRPSR）。（根据公式推导来看，方法太复杂，不一定也实用）
给定一个测试样本 x ，其类别是与训练样本 X 中的某一些样本相同，所以 x 是与 X 相关的。利用这样的相关性，将训练样本和测试样本结合起来，形成一个新的矩阵 X~=[Xx] ，其对应的系数 Z~=[Zz] ，这里的 Z 训练样本的系数，在前一个阶段已经计算得到。 Z~ 可以被分解为一个固定的部分，和一个未知的部分
Z~=F+W,(20) 其中 F 表示固定部分 F=[Z0] ， W 是未知的部分 W=[Oz] 。将低秩约束加入 Z~ ，稀疏约束加入 W ，给出 LRPSR 的目标函数如下： argminZ~,W,E α||Z~||∗+β||E||ℓ+η||W||1s.t. X~=DZ~+E, Z~=F+W, πΩ(W)=O,(21) 其中 πΩ(W)=O 表示将矩阵 W 中除最后一列之外的所有元素置为零。加入一个辅助变量 J，写出増广 Lagrangian 函数 argminJ,Z~,W,E α||J||∗+β||E||ℓ+η||W||1+⟨Λ1,X~−DZ~−E⟩+⟨Λ2,Z~−J⟩+⟨Λ3,Z~−F−W⟩+μ2(||X~−DZ~−E||2F+||Z~−J||2F+||Z~−F−W||2F).(22) 使用交替乘子法 ALM 求解
对于 Z~ ，目标函数如下
argminZ~ ⟨Λ1,X~−DZ~−E⟩+⟨Λ2,Z~−J⟩+⟨Λ3,Z~−F−W⟩+μ2(||X~−DZ~−E||2F+||Z~−J||2F+||Z~−F−W||2F).(23) 令其导数为零，得到 Z~=(DTD+2I)−1(DT(X~−E)+F+W+J+(DTΛ1−Λ2−Λ3)/μ).(24)对于 J ，目标函数
argminJ α||J||∗+⟨Λ2,Z~−J⟩+μ2||Z~−J||2F=argminJ α||J||∗+μ2||J−(Z~+Λ2/μ)||2F.(25) 直接使用 SVT 求解， USVT=svd(Z~+Λ2/μ), Ji=USα/μ(S)VT.(26)对于 W ，目标函数为
argminW η||W||1+⟨Λ3,Z~−F−W⟩+μ2||Z~−F−W||2F,argminW η||W||1+μ2||W−(Z~−F+Λ3/μ)||2F.(27) 用 soft-thresholding 求解 W=Sη/μ(Z~−F+Λ3/μ).(28) 接着将约束 πΩ(W)=O 应用于 W （这里与 ℓ1 约束冲突，是否还有意义？）。对于变量 E ，如果 ||E||ℓ 是 ||E||1 ，目标函数写为
argminE β||E||1+⟨Λ1,X~−DZ~−E⟩+μ2||X~−DZ~−E||2F,argminE β||E||1+μ2||E−(X~−DZ~+Λ1/μ)||2F.(29)(30) 通过 soft-thresholding 或 shrinkage 操作求解 E=Sβ/μ(X~−DZ~+Λ1/μ).(31) 如果 ||E||ℓ 是 ||E||2F ，可以直接忽略这个约束，应为误差已经在 ||X~−DZ~||2F 中被考虑到了。更新其他一些参数
Λ1=Λ1+μ(X~−DZ~−E), Λ2=Λ2+μ(Z~−J), Λ3=Λ3+μ(Z~−F−W), μ=min(ρμ,μmax).LRPSR 使用全部的训练集，可能会过大，计算很耗时。这里采用一个样本筛选步骤（Sample Selection, SS）16，从每一个类别中选择一小部分训练样本，使测试阶段的效率更高。
给定第 k 类别的 Xk，用 Euclidean 距离计算一个非相似矩阵 S 。考虑一个辅助的变量 V ，关联其非相似矩阵
V=⎡⎣⎢⎢vT1⋮vTN⎤⎦⎥⎥=⎡⎣⎢⎢v11⋮vN1v12⋮vN2⋯⋱⋯v1N⋮vNN⎤⎦⎥⎥,(32) 其中 vTi 表示矩阵 V 的第 i 行。vij 可以解释为 Xk(i) 中的第 i 个样本用于表示 Xk(j) 中的第 j 个样本的概率。用 Xk(i) 表示 Xk(j) 的代价为 sijvij 。表示样本 Xk(j) 的所有样本代价为 ∑Ni=1sijvij ；表示所有样本 X 总代价为 ∑Nj=1∑Ni=1sijvij 。为了选择较少的样本表示 Xk ，意味着 V 应该是行稀疏矩阵。加入一个行稀疏约束项，最小化的代价函数如下 argminvij λ∑i=1NI(||vi||p)+∑j=1N∑i=1Nsijvijs.t. ∑i=1Nvij=1, vij≥0.(33) 这个优化问题可以用 ALM 求解，具体的求解过程在 [16] 中给出。
在获得了测试样本 x 的系数表示 z 之后，通过最小重建误差进行分类
i∗=argmini ||x−DΔi(z)||22,(34) 其中 Δi(z) 表示设置除第 i 类之外的元素为零。解释为：可以用对应的子字典和系数相乘减去样本 x 的最小残差得到标签类别。略
已知 L(Dk)=12||Xk−DkZkk||2F+γ2∑i≠k||DTiDk||2F ，进而得到 L(Dk−τ∇L) 的表达式
L(Dk−τ∇L)=12||Xk−(Dk−τ∇L)Zkk||2F+γ2∑i≠k||DTi(Dk−τ∇L)||2F.(35) 直线搜索的定义，求令下一次迭代的值最小的步长 τ=argminθ L(Dk−θ∇L) ，通过求其梯度并令其等于零，得到 ∂L(Dk−θ∇L)∂τ=tr((∇LZkk)T(∇LZkkτ+Xk−DkZkk))+γ∑i≠ktr((DTi∇L)T(DTi∇Lτ−DTiDk))=0,⎛⎝tr((∇LZkk)T∇LZkk)+γ∑i≠ktr((DTi∇L)TDTi∇L)⎞⎠τ=−tr((∇LZkk)T(Xk−DkZkk))+γ∑i≠ktr((DTi∇L)TDTiDk),⎛⎝||∇LZkk||2F+γ∑i≠k||DTi∇L||2F⎞⎠τ=−tr((Xk−DkZkk)T(∇LZkk))+γ∑i≠ktr(DTkDiDTi∇L),τ=−tr((Xk−DkZkk)T∇LZkk)−γ∑i≠ktr(DTkDiDTi∇L)||∇LZkk||2F+γ∑i≠k||DTi∇L||2F. 其中使用几个迹的性质 tr(A±B)=tr(A)±tr(B), tr(ATA)=||A||2F, tr(A)=tr(AT) ，证毕。