稀疏表示的人脸识别及其优化算法

第２９卷第１期　２０１２年２月　文章编号：１００５—０５２３（２０１２）０１－００１０—０５　华东交通大学学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｅａｓｔ　Ｃｈｉｎａ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　Ｖｂ１．２９　ＮＯ．１　Ｆｅｂ．．２０１２　稀疏表示的人脸识别及其优化算法　郑轶　，蔡体健　，。　（１．华东交通大学轨道交通学院，江西南昌３０００１３；２．华东交通大学信息工程学院，江西南昌３３００１３；３．中南大学信息科　学与。一程学院，湖南长沙４１００７５）　摘要：稀疏表示的本质就是稀疏正规化约束下的信号分解。提出一种改进的正交匹配追踪算法，使运算量较高的矩阵求逆　运算转变为轻量级的向量运算或向量与矩阵的运算，可以加快逆矩阵和大矩阵乘积的求解。将此算法应用于稀疏表示的人　脸识别，探讨并验证了稀疏阀值的设置和训练字典的选择对人脸识别率和识别速度的影响。　关键词：压缩感知；人脸识别；稀疏表示；快速正交匹配追踪算法；特征提取　中图分类号：ＴＰ３９１．４　文献标识码：Ａ　人脸识别问题是一个经典的模式识别问题。近年来，受到压缩感知理论的启发，基于稀疏表示的人脸　识别技术得到了广泛研究。基于稀疏表示的人脸识别是利用训练图片构造字典，再通过求解一个欠定方　程来求得测试图片的最稀疏线性组合系数，然后根据这些系数来对图像进行识别分类。　稀疏表示的人脸识别问题表示成数学形式为：ｌ，＝　，其中Ｙ∈Ｒ　是ｍ维自然信号，Ａ∈Ｒ　是预定　义的基（又称为字典），Ｘ∈Ｒ　是自然信号在预定义基下的ｉｖ／维稀疏表示。在已知原始信号的基础上，求解　其在预定义基下的稀疏表示，是一个稀疏编码问题，可有以下两种求解方式ｎ。　：　稀疏正规化约束下的稀疏编码：　．１￣＝ａｒｇｍｉｎＩ［Ｙ—Ａ２０１；ｓ．ｔ．１１２０１０≤　３￣＝ａｒｇｍｉｎ１１０１２ｏ　ｓ．ｔ．ｊ１ｙ—ＡＸｌｌ　≤ｓ　（１）　（２）　误差约束下的稀疏编码：　式中：　是原始信号ｌ，在预定义基下的稀疏表示系数；ｓ是误差容限；　是稀疏阈值；ｌ１．１ｌ　表示『ｎ范数，即列　数向量中非０元素的个数。　稀疏编码与信号的压缩感知重构具有相同的数学形式，其主要的求解算法包括最小，０范数法、贪婪迭　代匹配追踪系列算法等。其中，匹配追踪类方法为其近似求解提供了有力工具，在稳定性和运行速度方面　具有一定的优势。目前常用的匹配追踪类算法包括：正交匹配追踪（ｏ￣ｈｏｇｏｎａｌ　ｍａｔｃｈｉｎｇ　ｐｕｒｓｕｉｔ，０ＭＰ）算　法　，基于树型搜索的正交匹配追踪算法　，正则化正交匹配追踪算法　，压缩采样匹配追踪算法　。等。　ｌ正交匹配追踪算法　正交匹配追踪思想　～本质上是来自于　‘稀疏”，就是从过完备字典的Ⅳ个原子中寻找　个关键分量，　这　个关键分量系数的绝对值应该比其它Ｎ－Ｋ个分量大得多。算法在每一次的迭代过程中，从过完备原子　库里选择与信号最匹配的原子来进行稀疏逼近并求出余量，然后不断迭代选出与信号余量最为匹配的原　子。为了减少迭代次数，算法通过递归对己选择原子集合进行正交化以保证迭代的最优性。具体见算法　收稿日期：２０１１　１２－２６　基金项目：周家自然科学基金项口（６１１６５００７）；华东交通大学科研项目（０９１１１００４）　作者简介：郑轶（１９７０一），男，副教授，硕士，研究方向为机械工程与信息控制及处理。　第１期　郑轶，等：稀疏表示的人脸识别及其优化算法　１，其中第５步是贪心选择原子的步骤，ｇ是所选择原子的索引；第６步是将所选择的原子　添加到子空间　Ａ　，Ａｄ是　的子矩阵；第７步是对已选择的原子进行正交化，并计算信号的表示系数　＝（　≠）　ｙ，在　此需要计算（　）　逆矩阵，矩阵的求逆运算是重量级的运算，往往需要对矩阵进行三角分解或ＱＲ分解；　第８步是计算最小残差　。　算法１正交匹配追踪算法　第１步第２步输入：字典　，列信号Ｙ，误差容限ｓ或稀疏阈值Ｋ　输出：稀疏的系数Ｘ　第３步初始化：设置残差Ｒ：＝Ｙ，系数　：＝０，Ａ　：＝［］　第４步ｄｏ　ｗｈｉｌｅ（迭代条件成立）　第５步ｑ：＝ｍａｘ　ｆ　Ｉ｝　第６步Ａ　：＝　第７步　＝（　第８步第９步ｅｎｄｄｏ　）　Ａ；Ｙ　Ｒ：＝Ｙ－Ａ　Ｘ　２改进的正交匹配追踪快速算法　正交匹配追踪算法的计算量主要集中在（　）　矩阵求逆，而Ａ　在每次迭代中只是增加一列，因此　对（　）　的求逆，完全可以用它的上一次迭代的逆矩阵推算得来。假设未更新前的子字典为　，则更　新后的子字典Ａ≯＝ｌ　Ａ。ｌ。令　＝　≠，则可以推得：　Ｆ＝　Ｔ　＝ｌ　：　；　Ｉ：够　ｃ３　（４）　式中：　＝　；ｃ＝ＡＴＡ　。　由于Ｆ是对称正定矩阵，因此可令Ｆ＿。：ｌ　ｙ１ｌｌ　，又由于ＦＦ～：Ｉ（，为单位矩阵），经过运算可得到：　＝１／（ｃ—ｖＴｐ　）；ｙ＝一Ｐ　Ｖｗ；ｘ＝Ｐ＿。Ｉ—ＶＹ　）　由于每次迭代都只是增加一列，因此在上式中Ｃ和Ｗ都是标量，　和】，是向量，而　是上一次迭代的　逆矩阵，是个已知矩阵，因此Ｆ　的求解变成了向量或向量矩阵的轻量级运算。　为了进一步减少正交匹配追踪算法的计算量，可以跳过残差　的计算，直接计算Ａ　Ｒ，并充分利用上　一次迭代的结果进行递推。其演算过程如下：　＝Ａ　Ｙ—Ａ≯　）＝Ａ　（Ｙ－Ａ　（　≠）＿。　ｌ，）＝　】，一　Ｆ　ｙ　（５）　令　＝　≯，　＝　ｊｌ，，则Ｇ＝　ＡＴＡ　］，Ｑ：　（ＡＴｙ）Ｔ￣　，Ｇ和Ｑ的值都可以从上一次迭代的值递　推得到，Ａ　Ｒ＝Ａ　】，一ＧＦ　Ｑ＝Ａ　Ｙ—ＧＸ。需要注意的是每一次迭代过程中字典Ａ也需要更新，即将上次　选中的原子删除。同样　也必需做同样的更新。改进的快速正交匹配追踪快速算法（ｆａｓｔ　ｏｒｔｈｏｇｏｎａｌ　ｍａｔｃｈｉｎｇ　ｐｕｒｓｕｉｔ，ＦＯＭＰ）见算法２：　算法２改进的快速正交匹配追踪快速算法　第１步输入：字典Ａ，列信号ｙ，误差容限ｓ或稀疏阈值Ｋ　１２　华东交通大学学报　第３步初始化：设置残差　：＝Ｙ，系数　＝０，Ａ　：＝［］，Ｇ：＝［］，Ｑ：＝［］，　：＝１，ｐｒｏｄｕｃｔ０＝Ａ　Ｙ　第４步第５步第６步ｄｏ　ｗｈｉｌｅ（迭代条件成立）　ｑ：＝ｍａｘ　ＩＡＷｋＲＩ　Ｉｆ　＞１　ｔｈｅｎ　第７步计算ｃ，，，Ｖ，　，，，Ｙ，　，然后计算Ｆ然后计算～＝－。＝ｌＩ　－Ｉ　ｌ第８步Ｅｌｓｅ　第９步　Ｆ一：（　）　第１０步Ｅｎｄｉｆ　第１１步　≠：＝Ａ≠Ａｑ］　第１２步Ｇ＝　ＡＴＡ　】，Ｑ　第　步Ｔｙ］　Ｘ＝Ｆ　Ｑ　Ａ　Ｒ＝ｐｒｏｄｕｃｔ０一ＧＸ　更新ｐｒｏｄｕｃｔ０￣ｌｌＧ　第　步第　步第　步ｅｎｄ　ｄｏ　３在稀疏表示的人脸识别中的应用　基于稀疏表示的人脸识别利用测试人身份的稀疏性来进行人脸识别ｎ　。数学表示形式为：ｌ，＝　，其　中Ｙ∈Ｒ　是测试人脸图像，Ａ∈Ｒ　”是用已标识的若干个人的　幅人脸图像形成训练字典，每幅图像有ｍ　个像素点。　＝ｌ０，…，０，　，０，…，０１　∈Ｒ　是稀疏系数，除了与测试图像对应的系数为非０，　的其他值大　多为０。由于一般情况下，ｚ《ｍ（虽然潜在的情况是　》ｍ），　是非完备字典，高维的图像数据破坏了方　程的欠定性，无法利用现有的稀疏编码算法求解，并且在现实中，噪声或遮挡不可避免，为此改为用　】，＝　＋ｅ来描述，其中ｅ∈Ｒ　是　维未知噪声，再将此式变换一下：　ｙ＝［Ａｔ］［ｘ１＝ＢＷ　式中：Ｉ是单位矩阵，　＝　∈Ｒ　～；Ｗ＝Ｉ　＿Ｊｌ　∈　题变成求解以下最优化问题，可以用以上的ＦＯＭＰ算法来计算测试样本的表示系数ｘ　Ｗｏ＝ａｒｇｍｉｎ　ｌ　ＩＩｏ　ｓ．ｔ．Ｙ＝ＢＷ　（６）　（７）　，此时　＋　＞ｍ，因此基于稀疏表示的人脸识别问　人脸识别问题实际上是一个测试样本的归类问题。获得了测试样本的稀疏表示　后，由于　中的非０　系数是与字典中属于某一样本类的原子相关，根据这些非０系数就可以简单快速判断测试样本所属类别。　但是由于不同样本类的同一光照角度的图像很相似，容易产生误判，另外噪声的存在使得许多小的非Ｏ项　和多个类别相关，因此我们需要设计一个更精确的分类器。具体做法是：将　中某样本类的系数保留，其　他样本类的系数清０，然后计算测试信号的非线性逼近误差值，最后比较所有样本类的误差值，最小的非线　性逼近误差所对应的类即是测试样本归属的类。　４实验与参数设置　以Ｙａｌｅ　Ｂ人脸库　ｌ（ｔｈｅ　ｙａｌｅ　ｆａｃｅ　ｄａｔａｂａｓｅ　Ｂ）做人脸识别实验，选用１０个人某种姿势下的６４种不同光　照条件下的６４０幅图片，每幅人脸图片大小为８４×９６像素，对图片进行了直方图均衡化及归一化处理，实　验中选取每个人的一部分图片形成训练字典，随机选取其他的图片做测试样本。所选用的机器是Ｄｅｌｌ笔　记本电脑，Ｇｅｎｕｉｎｅ　Ｉｎｔｅｌ　ＣＰＵ　１．６６　ＧＨｚ，１　Ｇ内存。　第１期　郑轶，等：稀疏表示的人脸识别及其优化算法　１）两种算法的对比。为了对比经典的ＯＭＰ算法与改进的ＯＭＰ算法的优劣，我们为每样本类选择１５　个光照图片，选择的原则是尽量考虑各种光照角度的图片，从而构建一个大小为８０６４×８　２１４的训练字　典。随机选择不在字典中的３００幅人脸图片用于测试，设置稀疏阀值从５变化到５Ｏ，在相同条件下应用这　两种算法进行人脸识别实验，分别记录下两种算法平均１００幅人脸识别时间以及对应的识别率。所得到的　曲线图如图ｌ所示。　由图１可知，改进的ＦＯＭＰ算法１００幅人脸识别时间少于经典ＯＭＰ算法，并且随着稀疏阀值的增加，　两种算法的人脸识别时间的差距加大，当稀疏阀值　＝５０时，两种算法的１００幅人脸识别时间相差达到１４　秒多。　２）影响识别率的主要因素。在实验中我们发现增加稀疏阀值，相应地人脸识别率随着提高。图２是　设置字典大小为８　０６４×８　２１４（每样本类１５张图片），并给测试图片增加不同比例椒盐噪声的情况下，人脸　识别率也随稀疏阀值的变化曲线，由图２可知，在稀疏阀值较小时，增加稀疏阀值可明显提高识别率，但稀　疏阀值增加到一定值时（如　＞１５），识别率趋于稳定，分析其原因可知字典中每样本类的原子数目决定了　稀疏阀值的设置。　１００　９８　篓９６　…＿。警　鲞９４　无噪声识别率曲线　——４０％噪声的识别率曲线　３０％噪声的识别率曲线　９２　…一５５％噪声的识别率曲线　９０　．．Ｌ．．．．．．．．．．．．．．．．．—Ｌ．．．．．．．．．．．．．．．．．Ｊ．．．．．．．．．．．．．．．．．．．Ｉ．．．．．．．．．．．．．．．．．．Ｌ．．．．．．．．．．．．．－Ｊ　１０　２０　３０　４０　５０　６０　稀疏阀值　图１　ＦＯＭＰ算法与ＯＭＰ算法运行速度的对比　图２不同噪声下人脸识别率随稀疏阀值的变化情况　Ｆｉｇ．１　Ｔｈｅ　ｓｐｅｅｄ　ｃｏｍｐａｒｉｓｏｎ　ｂｅｔｗｅｅｎ　ｔｈｅ　Ｆｉｇ．２　Ｆａｃｅ　ｒｅｃｏｇｎｉｔｉｏｎ　ｒａｔｅ　ｃｈａｎｇｅｓ　ｗｉｔｈ　ｔｈｅ　ｓｐａｒｓｅ　ＯＭＰ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｔｈｅ　ＦＯＭＰ　ａｌｇｏｒｉｔｈｍ　ｔｈｒｅｓｈｏｌｄ　ｕｎｄｅｒ　ｄｉｆｅｒｅｎｔ　ｎｏｉｓｅ　为了进一步提高人脸识别率，需对训练字典进行调整。为每个样本类提供各种角度的光照图片，特别　是极端光照条件下的人脸图片，能明显提高人脸识别率，见图３（ａ）。图４是设置稀疏阀值为２０，分别为测　试人脸添加１０％，３０％，５５％的椒盐噪声的情况下，人脸识别率随训练字典变化的曲线。由图４可知，在字　典大小达到一定值时（每样本类２０幅图片），人脸识别率基本稳定下来，添加了５５％椒盐噪声的测试样本的　识别率仍可达到９９．５％以上，这远远超过了人类肉眼的识别能力。图３（ｂ）是为测试图像分别添加１０％，　３０％，５５％的椒盐噪声后的图片。从图３可知，噪声达３０％及以上的图片，人类肉眼已很难识别了。　由图３和图４可知，在噪声较小的情况下（３Ｏ％以下噪声），每样本类的光照图片只需２０张，也就是说在　光照变动不超过３Ｏ。的情况下，人脸图片是可以完全正确识别的，Ｙａｌｅ　Ｂ人脸库光照的左右变动范围　为一１３０。－１３０。，上下变动范围为＿４Ｏ。～９Ｏ。，光照角度并不全，如果补全数据，性能将可以进一步得到提高。　■■一　（ａ）　不Ｍ角度的光照人脸图片　■一豳　（ｂ）　添加　同噪声的人脸图片　训练字典中每类的原子数／个　图３训练图片和测试图片　图４不同哚声下人脸识别率随训练　字典大小的变化情况　Ｆｉｇ．３　ｔｒａｉｎｉｎｇ　ｐｉｃｔｕｒｅ　ａｎｄ　ｔｅｓｔｉｎｇ　ｐｉｃｔｕｒｅ　Ｆｉｇ．４　Ｆａｃｅ　ｒｅｃｏｇｎｉｔｉｏｎ　ｒａｔｅ　ｃｈａｎｇｅｓ　ｗｉｔｈ　ｔｈｅ　ｓｉｚｅ　ｏｆ　ｄｉｃｔｉｏｎａｒｙ　ｕｎｄｅｒ　ｄｉｆｆｅｒｅｎｔ　ｎｏｉｓｅ　华东交通大学学报　２０１２正　５结论　研究提出了一种改进的ＦＯＭＰ算法，此算法是将重量级的矩阵求逆或大矩阵乘积运算转变为轻量级　的向量运算或向量矩阵运算，从而提高了算法的运算速度。此算法可广泛应用于稀疏分解或压缩重构，特　别适合于人脸识别以及类似的高维数据的分类。将此算法用于人脸识别实验，分析了影响人脸识别率的　因素，通过实验验证了在光照角度的变动不超过３０。的条件下，可以实现人脸的完全正确识别。如果进一　步考虑人脸的表隋、姿态等的变化，需要对训练字典的选择做进一步研究。　参考文献：　［１］戴琼海，付长军，季向阳．压缩感知研究［ＪＪ＿计算机学报，２０１１，３４（３）：４２５—４３４．　［２］李树涛，魏丹．压缩传感综述［　自动化学报，２００９，３５（１１）：１３６９—１３７７．　［３］杨荣根，任明武，杨静宇．基于稀疏表示的人脸识别方法［Ｊｊ．计算机科学，２０１０，３７（９）：２６６—２６９．　［４］ＴＲＯＰＰ　ＪＡ，ＧＩＬＢＥＲＴＡＣ．Ｓｉｇｎａｌ　ｒｅｃｏｖｅｒｙｆｒｏｍ　ｒａｎｄｏｍｍｅａｓｕｒｅｍｅｎｔｓ　ｖｉａ　ｏｒｔｈｏｇｏｎａｌｍａｔｃｈｉｎｇ　ｐｕｒｓｕｉｔ　ｌ　Ｊｊ．ＩＥＥＥＴｒａｎｓａｃ—　ｔｉｏｎｓ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ．２００７．５３（１２）：４６５５—４６６５．　［５］ＷＥＩ　Ｅ，ＳＨＡ　Ｉ．Ｏｇｈｏｇｏｎａｌ　ｍａｔｃｈｉｎｇ　ｐｕｒｓｕｉｔ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｃｏｍｐｒｅｓｓｉｖｅ　ｓｅｎｓｉｎｇ［ＥＢ／ＯＬ］．（２００８—０８—０１）ｌ２０１１－０９—０１　Ｊｈｔｔｐ：／／　ｗｗｗ．ｅｅｅ．ｈｋｕ．ｈｋ／～ｗｓｈａ／Ｆｒｅｅｃｏｄｅ／ｆｒｅｅｃｏｄｅ．ｈｔｍ．　［６］ＫＡＲＡＢＵＬＵＴ　Ｇ　Ｚ，ＭＯＵＲＡ　Ｌ，ＰＡＮＡＲＩＯ　Ｄ，ｅｔ　ａ１．Ｆｌｅｘｉｂｌｅ　ｔｒｅｅ　ｓｅａｒｃｈ　ｂａｓｅｄ　ｏｒｔｈｏｇｏｎａｌ　ｍａｔｃｈｉｎｇ　ｐｕｒｓｕｉｔ　ａｌｇｏｒｉｔｈｍｌＣｊ／／　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ａｃｏｕｓｔｉｃｓ，Ｓｐｅｅｃｈ，ａｎｄ　Ｓｉｇｎａｌ　Ｐｒｏｃｅｓｓｉｎｇ，２００５：６７３—６７６．　［７］ＤＥＡＮＮＡ　Ｎ，ＲＯＭＡＮ　Ｖ　Ｓｉｇｎａｌ　ｒｅｃｏｖｅｒｙ　ｆｒｏｍ　ｉｎｃｏｍｐｌｅｔｅ　ａｎｄ　ｉｎａｃｃｕｒａｔｅ　ｍｅａｓｕｒｅｍｅｎｔｓ　ｖｉａ　ｒｅｇｕｌａｒｉｚｅｄ　ｏｒｔｈｏｇｏｎａｌ　ｍａｔｃｈ—　ｉｎｇｐｕｒｓｕｉｔ［Ｊ］．ＩＥＥＥｊｏｕｒｎａｌ　ｏｆｓｅｌｅｃｔｅｄｔｏｐｉｃｓｉｎ　ｓｉｇｎａｌｐｒｏｃｅｓｓｉｎｇ，２０１０，４（２）：３１０—３１６．　［８］刘亚新，赵瑞珍，胡绍海，等．用于压缩感知信号重建的正则化自适应匹配追踪算法［Ｊ］．电子与信息学报，２０１０，８２（１１）：　２７ｌ３．２７１７．　［９］ＤＯ　Ｔ　Ｔ，Ｌ　ＧＡＮ，ＮＧＵＹＥＮ　Ｎ，ＴＲＡＮ　Ｔ　Ｄ．Ｓｐａｒｓｉｔｙ　ａｄａｐｔｉｖｅ　ｍａｔｃｈｉｎｇ　ｐｕｒｓｕｉｔ　ａｌｇｏｒｉｔｈｍ　ｏｒｆ　ｐｒａｃｔｉｃａｌ　ｃｏｍｐｒｅｓｓｅｄ　ｓｅｎｓｉｎｇ　［Ｃ］／／ＡｓｉｌｏｍａｒＣｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｓｉｇｎａｌｓ，Ｓｙｓｔｅｍｓ　ａｎｄＣｏｍｐｕｔｅｒｓ，２００８：５８１—５８７．　［１　０］ＷＲＩＧＨＴ　Ｊ，ＧＡＮＥＳＨ　Ａ，ＹＡＮＧ　Ａ，ｅｔ　ａ１．Ｒｏｂｕｓｔ　ｆａｃｅ　ｒｅｃｏｇｎｉｔｉｏｎ　ｖｉａ　ｓｐａｒｓｅ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ　ｌ　Ｊ１．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｔ—　ｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００９，３　１（２）：２　１　０—２２７．　［１　１］ＧＥＯＲＧＨＩＡＤＥＳ　Ａ　Ｓ，ＢＥＬＨＵＭＥＵＲ　Ｐ　Ｎ，ＫＲＩＥＧＭＡＮ　Ｄ　Ｊ．Ｆｒｏｍ　ｆｅｗ　ｔｏ　ｍａｎｙ：ｉｌｌｕｍｉｎａｔｉｏｎ　ｃｏｎｅ　ｍｏｄｅｌｓ　ｆｏｒ　ｆａｃｅ　ｒｅｃｏｇ—　ｎｉｔｉｏｎ　ｕｎｄｅｒ　ｖａｒｉａｂｌｅ　ｌｉｇｈｔｉｎｇ　ａｎｄ　ｐｏｓｅ［Ｊ＿．ＩＥＥＥ　Ｔｒａｎｓ　Ｐａｔｔｅｒｎ　Ａｎａｌ　Ｍａｃｈ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００　１，２３（６）：６４３—６６０．　Ｆａｃｅ　Ｒｅｃｏｇｎｉｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ｓｐａｒｓｅ　ＲｅｐｒｅｓｅｎｔａｔｉＯｎ　ａｎｄ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍｓ　Ｚｈｅｎｇ　Ｙｉ　，Ｃａｉ　Ｔｉｊｉａｎ　’　（１．Ｓｃｈｏｏｌ　ｏｆ　Ｒａｉｌｗａｙ　Ｔｒａｃｋｓ　ａｎｄ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ，Ｅａｓｔ　Ｃｈｉｎａ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｃｈａｎｇ　３３００　１　３，Ｃｈｉｎａ；２．Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒ—　ｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｅａｓｔ　Ｃｈｉｎａ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｙ，Ｎａｎｃｈａｎｇ　３３００　ｔ１　３，Ｃｈｉｎａ；３．Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｓｃｉｅｎｃｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，　Ｃｅｎｔｒａｌ　Ｓｏｕｔｈ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ４１００７５，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｅｓｓｅｎｃｅ　ｏｆ　ｓｐａｒｓｅ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ　ｉｓ　ｔｈｅ　ｓｉｇｎａｌ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ　ｕｎｄｅｒ　ｔｈｅ　ｃｏｎｓｔｒａｉｎｔ　ｏｆ　ｓｐａｒｓｅ　ｒｅｇｕ—　ｌａｒｉｚｅｄ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａｎ　ｉｍｐｒｏｖｅｄ　ｏｒｔｈｏｇｏｎａｌ　ｍａｔｃｈｉｎｇ　ｐｕｒｓｕｉｔ　ａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈ　ｗｏｕｌｄ　ｃｏｎｖｅａ　ｔｈｅ　ｈｉｇｈ　ｃｏｍｐｌｅｘｉｔｙ　ｏｐｅｒａｔｉｏｎｓ　ｏｆ　ｍａｔｒｉｘ　ｉｎｔｏ　ｔｈｅ　ｌｉｇｈｔｗｅｉｇｈｔ　ｏｐｅｒａｔｉｏｎ　ｏｆ　ｖｅｃｔｏｒ　ｏｒ　ｖｅｃｔｏｒ－ｍａｔｒｉｘ　ｃｏｍｐｕｔｉｎｇ．Ｔｈｉｓ　ｉｍ‘　ｐｒｏｖｅｄ　ｍｅｔｈｏｄ　ｃｏｕｌｄ　ａｃｃｅｌｅｒａｔｅ　ｔｈｅ　ｓｏｌｕｔｉｏｎ　ｏｆ　ｉｎｖｅｒｓｅ　ｍａｔｒｉｘ　ａｎｄ　ｌａｒｇｅ　ｍａｔｒｉｘ　ｍｕｌｔｉｐｌｉｃａｔｉｏｎ．Ｔｈｉｓ　ｐａｐｅｒ　ａｐ—　ｐｌｉｅｓ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｆａｃｅ　ｒｅｃｏｇｎｉｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｓｐａｒｓｅ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ，ｅｘｐｌｏｒｉｎｇ　ａｎｄ　ｖａｌｉｄａｔｉｎｇ　ｔｈｅ　ｅｆｆｅｃｔ　ｏｆ　ｔｈｅ　ｓｐａｒｓｅ　ｖａｌｖｅ　ｓｅｔｔｉｎｇ　ａｎｄ　ｔｒａｉｎｉｎｇ　ｏｆ　ｔｈｅ　ｄｉｃｔｉｏｎａｒｙ　ｏｎ　ｆａｃｅ　ｒｅｃｏｇｎｉｔｉｏｎ　ａｃｃｕｒａｃｙ　ａｎｄ　ｒｅｃｏｇｎｉｔｉｏｎ　ｓｐｅｅｄ．　Ｋｅｙ　ｗｏｒｄｓ：ｃｏｍｐｒｅｓｓｅｄ　ｓｅｎｓｉｎｇ；ｆａｃｅ　ｒｅｃｏｇｎｉｔｉｏｎ；ｓｐａｒｓｅ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ；ｏ￣ｈｏｇｏｎａｌ　ｍａｔｃｈｉｎｇ　ｐｕｒｓｕｉｔ　ａｌｇｏ　ｒｉｔｈｍ；ｆｅ：ａｔｕｒｅ　ｅｘｔｒａｃｔｉｏｎ