第２４卷第２期２０１１年４月模式识别与人工智能ＰＲ＆ＡＩＶ０１．２４ＡｐｒＮｏ．２２０１１张量补全算法及其在人脸识别中的应用史加荣焦李成尚凡华（西安电子科技大学智能信息处理研究所智能感知与图像理解教育部重点实验室西安７１００７１）摘要数据丢失问题通常可以归结为矩阵补全问题，而矩阵补全是继压缩感知理论之后的又一种重要的信号获取方法．在实际应用中，数据样例往往具有多线性性，即数据集可以表示成高阶张量．本文研究了张量补全问题及其在人脸识别中的应用．基于张量的低维Ｔｕｃｋｅｒ分解，提出张量补全的迭代算法，并且证明在算法的迭代过程中，估计张量与其Ｔｕｃｋｅｒ逼近张量的距离是单调递减的．实验结果表明张量补全算法在补全张量和人脸识别上的可行性与有效性．关键词张量补全，人脸识别，数据丢失问题，矩阵补全，Ｔｕｃｋｅｒ分解中图法分类号１１Ｐ３９１．４ＴｅｎｓｏｒＣｏｍｐｌｅｔｉｏｎＡｌｇｏｒｉｔｈｍａｎｄＩｔｓＡｐｐｌｉｃａｔｉｏｎｓｉｎＦａｃｅＲｅｃｏｇｎｉｔｉＯｎＳＨＩＪｉａ—Ｒｏｎｇ，ＪＩＡＯＵ—Ｃｈｅｎｇ，ＳＨＡＮＧＦａｎ—Ｈｕａ（量研如６０ｍ￡ｏ可矿ｍ把ＺＺ瑶｝ｅｍ胁￡如ｍｅ旷觑删咖眦蜘胁毗加ｍｃ∞ｓ垤，蜀ｄｉ口ｎ‰娩船蚵，施缸凡７１００７１）ＡＢＳＴＲＡＣＴＰｅｒｃｅｐ￡幻ｎ口蒯懈‰ｄｅ您ｔ肌击ｎｇ矿施ｎ括打ｙ矿尉妣口￡ｉｏｎ矿醌ｉ№，Ｍｉｓｓｉｎｇｄａｔａｐｍｂｌｅｍｓｃｏｍｐｌｅｔｉｏｎｉｓａｎａｒｅｃｏｍｍｏｌｌｌｙ砌ｂｕｔｅｄｔｏｔｈｅｍ“ｘｃｏｍｐｌｅｔｉｏｎｐｒｏｂｌｅｍ，ａｎｄｍａｔｒｉｘｄａｔａｉｍｐｏｒｔａｎｔｍｅｔｈｏｄｏｆｓｉｇｎａｌａｃｑｕｉｓｉｔｉｏｎｓｆｏＵｏｗｉｎｇｃｏｍｐｒｅｓｓｉｎｇｓｅｔｓｅｎｓｉｎｇ．Ｔｈｅｅｘ锄ｐｌｅｓＢａｓｅｄｏｎｈａｖｅｔｌｌｅｐｒｏｐｅｒｔｙｏｆｍｕｌｔｉ—ｌｉｎｅ耐ｔｙｉｎ叩ｐｌｉｃａｔｉｏｎｓ，ｔＩｌａｔｉｓ，ｔｈｅｄａｔａｃａｎｂｅｒｅｐｒｅｓｅｎｔｅｄｂｙｈｉｇｈｅｒｏ珂ｅｒｔｅｎｓｏｒｓ．Ｔｈｅｔｅｎｓｏｒｃｏｍｐｌｅｔｉｏｎｐｒｏｂｌｅｍａｎｄｉｔｓａｐｐｌｉｃａｔｉｏｎｓｉｎｆａｃｅｒｅｃｏｇｎｉｔｉｏｎａ弛ｓｔｕｄｉｅｄ．ｄｅｃｏｍｐｏｓｉｔｉｏｎｏｆｔｅｎｓｏｒＳ，ａＩｌｌｏｗｅ卜ｄｉｍｅｎｓｉｏｎａｌＴｕｃｋｅｒｉｔｅｒａｔｉｖｅａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｔｏｃｏｍｐｌｅｔｅｔｅｎｓｏｒｓ．ＡｎｄｔｈｅｄｉｓｔａｎｃｅｂｅｔｗｅｅｎｔｈｅｅｓｔｉｍａｔｉｎｇｔｅｎｓｏｒａｎｄｉｔｓＴｕｃｋｅｒａｐｐｍｘｉｍａｔｉｏｎｔｅｎｓｏｒｍｏｎｏｔｏｎｉｃａｌｌｙｄｅｃｒｅａｓｅｓｄｕｒｉｎｇｔｈｅｉｔｅｍｔｉＶｅｐｒｏｃｅｄｕｒｅ．ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｄｅｍｏｎｓｔｒａｔｅｔｈｅｅｆｆｅｃｔｉＶｅｎｅｓｓａｎｄｆｅａｓｉｂｉｌｉｔｙｏｆｔｌｌｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｉｎｃｏｍｐｌｅｔｉｎｇｔｅｎｓｏｒａｎｄｆ如ｅｒｅｃｏｇｎｉｔｉｏｎ．ＫｅｙＷｏｒｄｓ’ｒｅｎｓｏｒＣｏｍｐｌｅｔｉｏｎ，ＦａｃｅＲｅｃｏｇｎｉｔｉｏｎ，ＭｉｓｓｉｎｇＤａｔａＰｒｏｂｌｅｍ，ＭａｔｒｉｘＣｏｍｐｌｅｔｉｏｎ，ＴｕｃｋｅｒＤｅｃｏｍｐｏｓｉｔｉｏｎ木国家９７３重点基础研究发展计划（Ｎ０．２００６ＣＢ７０５７０７），国家８６３高技术研究发展计划（№．２００７ＡＡｌ２恐２３，２００７ＡＡｌ２２１３６），国家自然科学基金（Ｎｏ．６０６０３０１９，６０６０２０６４，６０７０２０６２）资助收稿日期：２００９一０９—１０；修回日期：２０１０—０８—１６作者简介史加荣，男，１９７９年生，博士研究生，主要研究方向为机器学习与模式识别．Ｅ－ｍａｉｌ：ｊｉａｒｏｎ铲３＠ｙａｌｌｏｏ．ｃｎ．焦李成，男，１９５９年生，教授，博士生导师，主要研究方向为自然计算，数据挖掘，图像处理，智能信息处理．尚凡华，男，１９７９年生，博士研究生，主要研究方向为机器学习．万方数据模式识别与人工智能２４卷ｌ引言数据丢失问题广泛地存在于科学与工程的诸多领域中，例如：计算机视觉［１。２］、图像修复［３１和机器学习－４Ｊ．为了分析与处理数据，通常需要事先估计丢失的元素．估计丢失元素的方法主要有两类：第一类是基于统计的归因法，主要包括均值法，忌近邻法和预测模型法等Ｈ。１；第二类是低秩矩阵分解法，它先将整个数据集表示为一个矩阵，然后基于秩亏损这一性质去恢复丢失的元素，主要包括ｗｉｂｅｒｇ算法，阻尼牛顿（ＤａｍｐｅｄＮｅ试ｏｎ，ＤＮ）算法，Ｌｅｖｅｎｂｅｒｇ—Ｍａ叩ａｒｄｔ算法和幂迭代法等¨ｑ’６Ｊ．根据第二类方法来恢复丢失元素又被称为矩阵补全问题（ＭａｔｒｉｘＣｏｍｐｌｅｔｉｏｎＰｒｏｂｌｅｍ）¨ｊ．在很多情况下，矩阵具有结构性，即它们是低秩或近似低秩的．对于一个秩为ｒ的ｍ×ｎ矩阵Ａ，由奇异值分解可知它的自由度为（ｍ＋ｎ—ｒ）ｒ¨Ｊ．当ｒ《ｍｉｎ（ｍ，ｎ）时，矩阵Ａ的自由度远远小于它的元素总数目ｍｍ这意味着由矩阵的少数采样来恢复矩阵是可能的．一个至关重要的问题是，如果矩阵的采样充分，是否一定能恢复矩阵？回答是否定的．考虑一个ｍ×ｎ的矩阵曰，它只有一个非零元素，显然它的秩为１．但是当矩阵曰的非零元素丢失时，不可能再恢复它．这自然会产生一个问题：当矩阵及采样数目满足什么条件时，可以较好地恢复它．最近，Ｃａｎｄ色ｓ等一，８１证明了当矩阵的特征值及采样数目满足一定的条件时，大多数低秩矩阵可以通过求解简单的凸优化问题（即半定规划问题）而以较大的概率近乎完美地恢复．现有的半定规划算法仅能解决小规模的问题，而最新提出的奇异阈值算法可以解决较大规模的矩阵补全问题一】．矩阵补全已成为继压缩感知（ＣｏｍｐｒｅｓｓｅｄＳｅｎｓｉｎｇ）之后的又一种重要的信号获取方法¨引．对于数据集中的样例，传统的表示方法是向量形式．在实际应用中，样例往往具有多线性性．例如，灰度人脸图像可以表示为２阶张量（矩阵）¨１ｌ，视频序列可以表示为３阶张量，功能磁共振成像（ＦｕｎｃｔｉｏｎａｌＭａｇｎｅｔｉｃＲｅｓｏｎａｎｃｅＩｍａｇｉｎｇ，朋ＲＩ）序列可以表示为４阶张量¨引．处理这类数据常用的方法是将张量样例向量化，但这会破坏数据的空时结构，导致维数灾难和小样例问题的产生【ｌ３｜．近年来，张量代数已成功地应用在模式识别、计算机视觉和信号处理等领域中．数据集中的所有张量样例可由一个更高阶的张量来表示．当数据集中的样例含有丢失元素时，数据张量是不完全的．根据张量万方数据的部分采样来恢复它，称此问题为张量补全问题．对于不完全张量，如果没有任何信息，补全它是不可能的．实际问题中的张量在各个模式上通常是低秩或近似低秩的．如果知道完全张量在各模式上的秩，那么可以得到它的Ｔｕｃｋｅｒ分解（或逼近）．假定一个，×，×…×，的Ｊ７、ｒ阶张量Ａ可以表示为低维Ｔｕｃｋｅｒ分解，其核心张量的维数为ｒ×ｒ×…×ｒ．由Ｔｕｃｋｅｒ分解可知张量的自由度为ｒ“＋ｒⅣ，一ｒⅣ（ｒ＋１）／２．当ｒ《，Ｊｉ２＜Ⅳ＜，时，张量Ａ的自由度远远小于它的元素总数目，．只要张量的采样数目大于它的自由度，就有可能完全恢复它．本文基于Ｔｕｃｋｅｒ分解，提出张量补全算法，并将其应用到人脸识别上．２张量代数张量又称为多阶阵列，是向量和矩阵的高阶推广．Ｊ７、ｒ阶张量Ａ∈Ｒ＾则ｚ”一划ｗ可由Ⅳ个指标来表示，其（ｉ。，ｉ：，…，０）元素表示为Ａ。也…．¨本文遵循Ｋｏｌｄａ和Ｂａｄｅｒ的符号描述，简单介绍张量代数的基本知识［１４１．定义ｌ张量Ａ，皿∈刚ｍ””州“的Ｈａｄａｍａｒｄ积为Ａ．木Ｂ，其（ｉｌ，ｉ２，…，“）元素为Ａ一：，…妇噩油，…西．定义２张量ＡＥＲ”，２””。啊的Ｆｒｏｂｅｎｉｕｓ范数为ＩＩＡ０＝（∑越忠．…晰）寺．１１ｔ１２，…，●Ⅳ张量Ａ，口∈Ｒ，ｌ州２””划“的距离为０Ａ一届¨定义３张量Ａ∈Ｒｊ”如””刈”的ｎ模式展开（又称为ｎ模式矩阵化）为矩阵ⅣＡ㈤∈Ｒ’ｎ砚‘，其中Ⅳ＾一１（Ａ㈤）¨＝Ａ附一曲，歹＝１＋∑（以一１）ｎＬ．定义４张量Ａ∈Ｒ＾地”“刈“的ｎ秩为其ｎ模式向量张成空间的维数，记为．，。＝ｒａｎｋ。（Ａ）．定义５张量Ａ∈Ｒ”，２””。ｈ与矩阵Ｕ∈Ｒ厶。ｋ的ｎ模式积为一个，ｌ×…×厶一ｌ×Ｌ×厶＋ｌ×…×，Ⅳ的张量，用Ａ×。ｕ表示，其（ｉ。，ｉ：，…，ｉ剃，Ｊ，ｉ州，…，ｉⅣ）元素定义为，＾（Ａ×。ｕ）ｉ１．¨．．。。。“。小…，抽＝∑Ａｌ＇ｉ：，…妇％。．‘ｎ２ｌ定义６张量Ａ∈Ｒ，ｌｘ。２”一刈“的Ｔｕｃｋｅｒ分解为Ａ＝Ｃ×１Ｕ‘¨…×ⅣＵ‘Ⅳ’＋８，其中Ｃ∈Ｒ７ｌ。如”‘。“２期史加荣等：张量补全算法及其在人脸识别中的应用为核心张量，８∈Ｒ，１州２”一州Ⅳ为噪声张量，模式矩阵ｕ¨’∈Ｒ。“刈“为列标准正交矩阵，Ｌ≤Ｌ，，Ｉ＝１，２，…．Ⅳ．定义７张量Ａ∈Ｒ”。ｚ””划“的ＰＡＲＡＦＡＣ分解为Ａ＝Ｕ‘１’。…。Ｕ‘Ⅳ’＋ｓ，其中￡，‘Ⅳ’∈Ｒ’一。‘，８∈Ｒ，１ｘ，２”～刈“为噪声张量，‘。’表示外积．作为Ｔｕｃｋｅｒ分解的特例，ＰＡＲＡＦＡｃ分解没有考虑不同模式之间的交互作用．Ｔｕｃｋｅｒ分解又称为张量的秩（．，，，＾，…，＾）逼近，可以通过对张量的奇异值分解进行剪切可得到，但这种方法一般来说不是最优的‘１２’１５—６｜．３张量补全问题现在考虑含有丢失元素的张量Ａ∈Ｒ，ｌ×，２”“埘ｗ．令Ⅱ和日为两个指示张量：如果Ａｌ＇ｉ：．…，ｉⅣ丢失，贝０皿：．，屯。…．抽＝Ｏ，皿。，ｉ：，…，抽＝ｌ；否则Ｊ匮。．屯．…，如＝ｌ，Ｅ．，屯。…．抽＝Ｏ．希望根据张量的低秩信息来补全张量．当张量Ａ具有ＰＡＲＡＦＡＣ低秩分解时，可以利用交替式最小二乘法来补全张量（ＰｏｓｉｔｉｖｅＴｅｎｓｏｒｃｏｍｐｌｅｔｉｏｎ，ＰＴｃ）Ⅲｏ．当它的ｎ秩为Ｌ（＾＜Ｌ）时，文献［１８］提出低秩张量补全算法（Ｌｏｗ．ＲａｎｋＴｅｎｓｏｒＣｏｍｐｌｅｔｉｏｎ，ＬＲＴＣ）．本文基于张量的Ｔｕｃｋｅｒ分解来补全张量（ＴｕｃｋｅｒＴｅｎｓｏｒＣｏｍｐｌｅｔｉｏｎ，ＴＴＣｌ．当张量不含丢失元素时，考虑它的最优Ｔｕｃｋｅｒ分解．为此，需求解下列优化问题：ｍｉｎ八Ｃ，￡，‘¨，…，Ｕ‘Ⅳ’）＝０Ａ—Ｃ×Ｉ￡，‘１’…×Ⅳ￡，‘Ⅳ’Ｉｌ２，ｓ．ｔ．Ｃ∈Ｒ＾ｘＪ２”‘。ＪⅣ，（１）Ｕ‘”’∈Ｒ。ｎ。Ｌ，（Ｕ‘”’）’Ｕ‘４’＝ＥＪ。，ｎ＝１，２，…，Ⅳ；其中，层Ｊ＾表示Ｌ阶单位矩阵．当模式矩阵ｕ¨’，￡，‘孙，…，Ｕ‘Ⅳ’给定时，目标函数以Ｃ，￡，‘¨，…，Ｕ州’）关于张量Ｃ为凸二次型，故最优张量Ｃ＝Ａ×１（Ｕ‘１’）’…×Ⅳ（Ｕ‘Ⅳ’）７．此时，张量Ａ的最优逼近为（Ａ×ｌ（Ｕ‘１’）’…×Ⅳ（Ｕ‘Ｍ）’）×ｌＵ‘¨…×『ｖＵ‘ｍ．因此，优化问题（１）等价于如下优化问题：ｍａｘｇ（￡，‘¨，…，Ｕ‘Ⅳ’）＝ｆＩＡ×ｌ（ｕ‘１’）’…×Ⅳ（Ｕ‘椰）’Ｉ｜２＇ｓ．ｔ．ｕ（“）∈Ｒｋ“，（【，‘“’）’盯“’＝目。，ｎ＝１，２，…，Ⅳ上述问题的目标函数和约束均不是凸的，直接求解比较困难．由于它是块优化问题，通常采用交替式方法求解模式矩阵ｕｈ），，Ｉ＝１，２，…，Ⅳ．当Ⅳ一１个万方数据模式矩阵ｕ‘¨，…，Ｕ‘”¨，Ｕ‘”¨，…，Ｕ‘Ⅳ’给定而ｕ抽’未知时，目标函数ｇ（ｕ‘¨，…，￡，‘Ⅳ’）＝Ｉｌ（ｕ‘“’）ＴＡ（。）％０２，其中瞩＝￡，‘Ⅳ’＠…ｏｕ‘“１’ｏｕ‘”１’ｏ…＠Ｕ¨’，‘＠’表示Ｋｒｏｎｅｃｋｅｒ积．最优矩阵Ｕ¨’可由Ａ㈩％的前，。个最大的奇异值对应的左奇异向量组成．交替更新模式矩阵，直至满足终止条件，便可得到张量的Ｔｕｃｋｅｒ分解．４张量补全算法对于含丢失元素的张量，不能对其进行高阶奇异值分解，更不能得到它的Ｔｕｃｋｅｒ分解．为了补全张量，先初始化张量Ａ的丢失元素，进而得到张量丑对张量Ｂ进行Ｔｕｃｋｅｒ分解，得到它的Ｔｕｃｋｅｒ逼近张量Ｄ，根据张量刀更新张量口，即届：＝匠木Ⅱ＋Ｄ．ｊｌ：皿由于张量的Ｔｕｃｋｅｒ分解是块优化问题，所以可以采用下列方式来简化问题：固定Ｔｕｃｋｅｒ分解中的Ｊ７、ｒ一１个模式矩阵，求解另外一个最优的模式矩阵．按照上述过程，重复更新张量皿显然，张量Ａ的未丢失的元素与张量口的相应元素相同．采用局部相对标准误差来评价张量Ｄ的逼近性能：麟肚悝嵩嵩尸＝嘴帮，（２）指标职ｓＥ越小越好．若采样充分，则当职ｓＥ＝０时，张量Ａ得到了精确的恢复．在迭代过程中，当衄ｓＥ下降比较缓慢时，可终止迭代．下面给出张量补全的算法流程．算法１张量补全算法（ＴＴＣ）ｓｔｅｐ１初始化张量Ａ的丢失元素，得到完全张量Ｂ；初始化￡，¨）∈Ｒｋ叫ｎ为列标准正交矩阵，ｎ＝２，…，Ⅳ；初始化局部相对标准误差￡ＪＲＳ哟和容许误差＆置，ｌ＝１．ｓｔｅｐ２Ｇ＝Ｂ×１（Ｕ‘１’）’…ר（Ｕ‘剃’）’×。＋１（Ｕ‘剃’）’…×＿ｌｖ（Ｕ‘Ⅳ’）Ｔ．ｓｔｅｐ３张量Ｇ按ｎ模式展开成矩阵Ｇ㈤，对协方差矩阵Ｇ（。）Ｇ：ｊ）进行特征分解，前Ｌ个最大的特征值对应的特征向量组成模式矩阵Ｕｎ）．ｓｔｅｐ４口＝（Ｇ×。（￡，‘８’）７）×１Ⅳ‘１’×…×，ｖ￡，（ｍ．Ｂ：＝匠球日＋Ｄ．冰Ⅱ女口果，ｌ＜＾ｆ，ｎ：＝ｎ＋ｌ，转ｓｔｅｐ２．如果ｎ＝Ⅳ，则按照式（２）计算职ＳＥ．２５８模式识别与人工智能２４卷当从ｓ哟一豫ｓＥ＜占时，终止算法，输出张量届；否则，置衄Ｊｓ脚＝衄ＳＥ，ｎ＝１．在上述算法中，张量口与其Ｔｕｃｋｅｒ逼近张量Ｄ之间的距离随着模式矩阵的更新而单调递减，即有如下定理．定理１若在算法１的某次张量更新过程中，张量Ｂ的Ｔｕｃｋｅｒ逼近为张量Ｄ，在其下次张量更新过程中，张量丑’的Ｔｕｃｋｅｒ逼近为张量Ｄ’，则有ＩＩＢ—ＤＩＩ≥』Ｂ７一Ｄ’¨证明对于张量Ｂ，固定模式矩阵酽¨，…，轳Ｈ’，栌¨’，…，轳ｍ，根据算法１的ｓｔｅｐ２和ｓｔｅｐ３可求得最优模式矩阵护ｎ．显然，矩阵轳‘’与张量Ｃ＝Ｂ×。（栌１’）７…×Ⅳ（酽Ⅳ’）’是下列问题的最优解：ｍｉｎＩＩ口一Ｃ×ｌ栌１’…×Ｈ轳¨’×ｉ铲ｉ’×…酽Ⅲ’…×Ⅳ扩椰０２，Ｕ‘ｉ’ＥＲ协＾，（Ｕ‘ｉ’）７Ｕ‘ｉ’＝Ｅ¨所以，张量Ｂ更新为口７＝匠，ｌ＝Ⅱ＋Ｄ．木日，其中张量Ｄ＝Ｃ×ｌ轳１’…×Ⅳ栌Ⅳ’为张量Ｂ的Ｔｕｃｋｅｒ逼近．此时有０口’一Ｄ０＝ＩＩ（皿水日＋Ｄ．：Ｉ＝Ⅱ）一（Ｄ．水口＋Ｄ．丰日）０＝０（曰一Ｄ）．木Ⅱ０≤ＩＩＢ—Ｄ¨在下次更新过程中，固定模式矩阵轳¨，…，护ｎ，驴“２１，…，扩ｍ，更新模式矩阵Ｕ（川），为此需求解ｍｉｎ｜ｌ曰’一Ｃ×ｌ扩１’…×ｉ护‘’×川Ｕ‘Ⅲ’×ｍ驴ｍ’…×＾ｒ驴Ⅳ’｜｜２，￡，‘ｉ＋１’∈Ｒ‘＋１。几１，（Ｕ‘Ⅲ’）１Ｕ‘Ⅲ’＝层Ｊｌ＋１．ＩＩＢ７一Ｄ’０≤ｌＩ（曰’一Ｃ×１栌¨…×ｉ轳‘’×Ⅲ轳川’×ｍ护ｍ’…×Ⅳ扩肿０＝０口’一Ｄ｜Ｉ≤ＩＩ皿一Ｄｎ证毕．由定理ｌ可知，衄ＳＥ随着模式矩阵的更新而单调下降下面讨论Ⅳ个模式矩阵均更新一次的计算复杂度．为此，先考虑矩阵ｕｎ’未知而其余的Ⅳ一１万方数据棋式矩阵巴知情彤Ｆ的计算复杂度．为表述简使，记，（ｏ）＝１，，（１ｉ｝）＝兀，ｉ，Ｊ（Ｊ｜｝）＝ｎ以，．｜｝＝ｌ，２，…，Ｎ．张量Ｇ的计算复杂度为。Ⅲ州薹器＋乞塞。器儿模式矩阵ｕ抽’的计算复杂度为ｏ（，２（，ｎ＋．，（Ⅳ）／Ｌ）），张量Ｄ的计算复杂度为叩（Ⅳ）（厶＋煮者％）］＇张量Ｂ的计算复杂度为Ｄ（，（Ⅳ））．所以，所有模式矩阵均更新一次的计算复杂度为删，ｃ耋务＋Ⅳ薹褊，＋轴．叩ｃ州Ⅳ＋薹ｃ芝器＋妻。塞。耥小５实验分析在实验中，所提供的数据张量Ｘ∈Ｒ，ｌ””灯ｗ不含丢失元素．若张量Ｘ的ｎ模式秩为．，。或近似为Ｌ，，ｌ＝１，２，…，Ⅳ，则它的自由度ｄ＝ｎ＾＋∑¨厶一掣］．记张量五的采样数目为口，则只有ｇ用大于等于１时，才有可能根据采样恢复张量．假定对张量尺进行随机采样，这样就得到不完全张量Ａ对于Ａ，采用最简单的方法初始化丢失元素，即令口＝Ａ球日，由于张量Ｘ事先已知，所以采用相对标准误差来度量算法的逼近性能：脚＝埒斧，ＲＳＥ越小越好，当ＲｓＥ＝０时，张量Ａ得到精确的恢复．下面在合成数据和实际数据（人脸数据）上来验证张量补全算法的有效性和可行性．５．１合成数据按照两种方式来随机合成数据，第一种方式是工＝Ｐ‘１’。…。Ｐ‘ｍ，其中Ｐ‘“’∈Ｒ‘”，ｎ＝ｌ，２，…，Ⅳ；第二种方式是石＝Ｓ×１Ｐ‘１’×２Ｐ‘２）…×ＪｖＰ‘Ｍ，其中ＪＳ∈Ｒ。１。Ｊ２。…。７Ⅳ，Ｐ‘“）∈Ｒ７ｎ。厶，ｎ＝１，２，…，Ⅳ．假设Ｐｎ’和Ｓ的元素均由相互的标准正态分布随机生成．对张量Ｘ进行随机采样，得到不完全张量Ａ下面给出４个例子．ｓ．ｔ．Ｃ∈ＲＪＩ。Ｊ２”’。ｈ．ｓ．ｔ．Ｃ∈Ｒ＾。如”’。ＪⅣ．设张量Ｂ’的最优Ｔｕｃｋｅｒ逼近为Ｄ’，则有２期史加荣等：张量补全算法及其在人脸识别中的应用例１例２例３例４张量Ｘ按照第一种方式随机生成，Ⅳ＝张量置按照第一种方式随机生成，Ⅳ＝结果如表１和表２所示．从表１和表２的性能比较可以看出，ＰＴｃ算法非３，厶＝，２＝，３＝５０，ｒ＝１０．４，，ｌ＝，２＝，３＝厶＝３０，ｒ＝１０．常不稳定；虽然ＬＲＴＣ算法相对稳定，但尺ＳＥ值非常大；ＴＴｃ算法的尺．ｓＥ值接近于０，同时又比较稳张量Ｘ按照第二种方式随机生成，Ⅳ＝张量晨按照第二种方式随机生成，Ⅳ＝定．因此，在上述３种算法中只有ＴＴＣ几乎比较完美地补全了张量．ＰＴＣ算法只适用于特殊的低秩张量；ＬＲＴｃ是一种松弛算法，它受采样数目、张量的秩以及参数选取的影响很大．在以后的试验中不再将这两种算法与ＴＴｃ进行比较．表３给出例３和例４试验结果，可以看出张量也得到几乎比较完美的恢复．３，，。＝厶＝Ｌ＝５０，＾＝以＝以＝１０．４，厶＝，２＝，３＝，４＝３０，＾＝厶＝厶＝厶＝１０．对于相同的采样数目ｇ，重复执行５次试验，用ＲｓＥ的平均值及标准差来评价算法的性能．对于前两个例子，将ＴＴＣ算法与ＰＴＣ和ＬＲＴＣ进行比较，试验表１Ｔａｂｌｅｌ例ｌ在３种算法下的性能比较ｆｏｒＥｘａｍｐｌｅｌＰｅｒｆｂｒｍａｎｃｅｃｏｍｐａｒｉｓｏｎａｍｏｎｇ３ａ１９０ｒｉｔｈｍｓ表２Ｔａｂｌｅ２例２在３种算法下的性能比较Ｐｅｒｆｏｒｍａｎｃｅｃｏｍｐａｒｉｓｏｎａｍｏｎｇ３ａｌｇｏｒｉｔｈｍｓｆｏｒＥｘａｍｐｌｅ２表３Ｔａｂｌｅ３例３和例４在ＴＴＣ算法下的试验结果ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｆｂｒＥｘａｍｐｌｅ３ａｎｄＥｘａｍｐｌｅ４ｗｉｔｈ７Ｉ’１１Ｃ５．２人脸识别在ＯＲＬ和Ｙａｌｅ人脸数据库上进行实验．ＯＲＬ似低秩的．在ＯＲＬ中，取＾＝厶＝１０，＾＝６０；在Ｙａｌｅ中，取．，。＝以＝１０，厶＝３０．对每个数据张量进行随机采样，再利用算法ｌ（，Ｉ’ｒｒＣ）进行补全．待张量补全后，训练集和测试集规定如下：在０ＲＬ中，每个人的前５幅图像属于训练集，其余的５幅图像归为测试集；在Ｙａｌｅ中，每个人的前６幅图像为训练集，其余的５幅图像为测试集．最后用最近邻法对人脸数据进行分类．对于相同的采样数目ｑ，将试验重复５次，最终用相对标准误差（Ｒ．ｓＥ）和识别人脸数据库包括４０个人的人脸图像，其中每个人有１０幅不同的图像．这些图像在不同时间获取，具有不同的表情和面部细节，而且稍许倾斜（不超过２００）．Ｙａｌｅ人脸数据库包括１５个人的人脸图像，其中每个人有ｌｌ幅不同的图像．它们是具有不同表情、遮掩和光照条件的正面图像．为计算方便，这两个数据集的每幅图像均经下采样成为６４×６４的图像．每个人脸数据库的图像都可以形成３阶张量．ＯＲＬ的张量数据的维数为６４×６４×４００，Ｙａｌｅ的张量数据的维数为６４×６４×１６５．人脸数据集通常具率（础）来评价算法的性能，如表４和表５所示．为了便于比较，现给出对原人脸数据张量直接使用最近邻法进行分类的结果：０ＲＬ的识别率为Ｏ．８７５Ｙａｌｅ的识别率为０．７７３３．０，有较大的冗余，可认为数据张量在每个模式上为近从表４和表５可以看出，随着采样数目的增加，万方数据模式识别与人工智能２４卷尺ｓＥ会随之碱小，础会随之增加；尺ｓＥ和础的标准差相对比较小，这说明算法具有好的稳定性；当的识别率仅有约１％的误差与表３相比．表４和表５的船Ｅ比较大，这是因为表３的数据不含噪声．而表４和表５的数据含的噪声比较大ｑ／ｄ＝７时，订ｃ算法所得到的识别率与全部采样下襄４Ｔａｂｌｅ４ＴＴｃ算法在０ＲＬ上的实验结果Ｅｘ口ｅｒ…ｎＩＢｌ…１ｔ３ｎｆ１ＴＣ５ｏｎ０ＲＬ６７６ｌｘ１０’４０ｔ１６２±４０６×１０４４／ｄ４０ｌ３８２±３７０ｘ１０。Ｏ月距０１２７ｌ±６０７×１０。Ｏ８４７０±００１１５０１２０３±２刷８３４０±０叭２４０８５５０±００１０６Ｏ８６４０±Ｏ００９６表５Ｔａｂｌｅ５Ｅ…ｌ…ＩａＩ…ｌｔｓ５ＴＴｃ算法在Ｙａｌｃ上的实验结果ｂｒＴＴＣ。ｎＹａｌｅ６０２１６４±０００４９０７４９３±ｎ０２７３７０２０２０±０００１９０７６５３±００２２３叮／ｄ４０３０１６±００２２００６６９３±Ｏ０４９４船Ｆ础０２３３８±０００６２０７１７３±０们７４当采样概率为ｏｌ时，图１和图２分别给出两个数据集的部分原始图像与相应的采样图像和补全图像，其中（ｂ）是采样图像（来采样点用白像素表示）通过比较原始图像与补全图像．可以得出如下的结论张量补全算法较好地恢复了人脸的轮廓；由于采样率相对比较小，眼镜等部分噪声得到有效的抑制（ａ）原始图像圈銎錾噩莲堑（ｂ）采样图像ｂ）ｓａ“ｐｌｅｄＩｍＢ舻ｓ（ｃ）补全翱像ｃ）ｃｏｏｐｌｅｔｅｄ唧ａｇ。ｓ囤２采样概率为０ｌ时Ｙａｌｅ的原始人脸图像与补全图像对比Ｆ１９２ａ）Ｏｒｌ９１ｎｍｌ“ａｇｅｓ（ａ）原始图像圈］翌要噩殛（ｂ）采样图像ｂ）ｓａｍ—ｅｄｌ“ａｇｅ８ａ）０“ｇ…ａｌ～ｐ８Ｃｏ”ｐ８＾…ｂｅｔ……‘９１ｎａＩｌｍ８９…Ｍ…ｐｌ”ｇａｎｄ…ｐＩｅｔｅｄｏｎｈｃｅｐ。ｏｂａｂｌＩｌｔｙ“０ｌＹａｌｅ（ｃ）补全目像ｃ）ｃｏ“ｐｌｅｔｅｄ圈１ｌｍａｇｅｓ６结束语本文研究了张量补全问题对于不完全数据张量，基于Ｔｕｃｋｅｒ分解提出张量补全的算法，并从理论上证明在算法的迭代过程中估计张量与其Ｔｕｃｋｅｒ逼近张量的距离是单调递减的张量补全算法为张采样概率为ｏｌ时ＯＲＬ的厚始人脸图像与补全图像对比Ｆ镕ｌＣｏ“ｐ８ｒｉｓｏｎｂｅｔ…ｏｒｌｇｍａｌａｎｄ…ｐｌｅｔｅｄｈｃｅ…妒…ｔｈ…ｐＩｌ”ｇｐ”ｂａｂｌｌｎｙｄ０Ｊ。ｎ０ＲＬ万方数据２期史加荣等：张量补全算法及其在人脸识别中的应用２６ｌ量信号采样提供了一种新方法．实验结果表明了张量补全算法在补全张量和人脸识别上的可行性与有效性．张量补全问题的理论与应用仍值得进一步研究．参考文献［１］０ｋａｔ蛐ｉＴ，ＤｅｇＩｌｃｈｉＫ．０ｎｔｌＩｅｗｉｂｅｒｇＡＩｇｏｒｉｔＩＩｍｆｏｒＭａ血Ｆ扯ｔｏｒｉ－枷ａｎｉｎｔＩＩｅＰｌ汜ｓｅｎｃｅ０ｆＭｉｓｓｉｎｇＣｏｍｐｏｎｅｎｔｓ．Ｉｎｔ锄ａｔｉｏｎａｌＪｏｕｍａｌ０ｆＣｏｍｐｕｔｅｒＶｉｓｉｏｎ，２００７，７２（３）：３２９—３３７［２］ｃｈｅｎＰｅｉ．０ｐＩｉＩｌｌｉｚ“０ｎＡｌｇｏｒｉｔｌＩｍｓ蚰ｓｕｂｓｐ扯鹄：Ｒｅ“ｓｉｔｉｎｇＭｉｓ８ｉｎｇＤａｔａＰｒｏｂｌ咖ｉｎｈｗ—Ｒ蛐ｋＭｇｔｒｉｘ．ｈｌｔｅｍａｌｉ∞ａｌＪｏ哪ａＩｏｆＣｏｍｐｕｔ－ｅｒＶｉｓｉｏｎ，２００８，８０（１）：１２５一１４２［３］ＫｏＩａｌｌＴ，Ｒ鹕ｍｕｓｓｅｎｃ．ｓｐ娟０ｔｅｍｐｏｒａｌＩｎｐａｉＨｔｉｎｇｆｏｒＲｅｃｏｖｅｒｉｎｇｋｔｕｒｅＭ叩ｓｏｆＯｃｄｕｄｅｄＢｕｉｌｄｉｎｇＦａｃａｄ髑．皿ＥＥＴｒ如ｓｏｎＩｍａｇｅＰｒｏｃ∞８ｉｎｇ，２００７，１６（９）：２２６２—２２７ｌ［４］Ｇａｒｃｉａ．ＬａｅｎｃｉｎａＰＪ，ｓａｎｃｈｏ－Ｇｏｍｅ互ＪＬ，ＦｉｇｕｅｉＩ鹳－ＶｉｄａＩＡＲ，ｅｔｄＺ．ＫＮ舶瑚ｔＮｅｉｇｌｌｈ岫ｗｉｔｌｌＭｕｔｕａｌＩｎｆ０册ａｔｉｏｎｆ打ｓｉｍｕｌｔａｎｅｏｕ８Ｃｌ哪ｉｆｉｃａｔｉｏｎ锄ｄＭｉ鹞ｉｎｇＤａｔａＩｍｐｕ叫ｏｎ．Ｎ叫ｒｏｃ嘲”ｔｉＩｌｇ，２００９，７２（７／８／９）：１４８３—１４９３［５］Ｆａｒｈ删【ｇｆａｍＡ，ＫＩＩｒｇａｎｂＬ，ＤｙＪ．Ｉｍｐ舵ｔ０ｆＩｍｐｕｔ８６０ｎ０ｆＭｉ驰ｉｎｇＶａｌｕｅｓｏｎＣｌａｓｓｉｆｉｃａｔｉｏｎＥ眦ｆｏｒＤｉｓｃ硪Ｄａｔａ．Ｐａｔｔ锄Ｒｅｃｏ驴ｉ－ｄ∞，２００８，４１（１２）：３６９２—３７０５［６］Ｖｉｄ８ｌＲ，Ｔｒ硼Ｒ，ＨａｒｔｋｙＲ．Ｍｕｌ６ｈｍｅＭ撕ｏｎＳｅｇｍｅｎｔ撕蚰ｗｉｄｌＭｉｓｓｉｎｇＤａｔａＵｓｉｎｇＰ嘶ｅｒＦａｃｔｏｒｉ髓￡ｉｏｎ孤ｄＧＰＣＡ．Ｉｎｔ唧ａｔｉ∞ａｌＪｏｕｍａｌ０ｆＣｏｍｐｕｔｅｒＶｉｓｉ∞，２００８。７９（１）：８５一１０５［７］ｃ删ｆＩｄ爸ｓＥＪ，ＲｅｃｈｔＢ．ＥｘａｃｔＭ圳血ｃｏｍｐｌｅｔｉｏｎｖｉａＣｏｎｖｅｘ０ｐ６ｍｉ・躔ｔｉｏｎ．ＦｏｕｎｄａｔｉｏｎｓｏｆＣｏｍｐｕｔａｔｉｏｎａｌＭａｔｈｅｍａｔｉｃｓ，２００９，９（６）：７１７—７７２［８］ｃ蚰ｄｂＥＪ，Ｔｅ惦ｎｃｅＴ．ＴｈｅＰｄｗ盯０ｆｃｏｎｖ麟Ｒｅｌ懿“０ｎ：Ｎｅａｒ－０ｐ－ｔｉｍａｌＭａ试ｘＣｏｍｐｌｅｔｉｏｎ．ＩＥＥＥ７ｒｍ璐们Ｉｎｆ０咖“佣ｎｅｏｒｙ，２０１０，５６（５）：２０５３—２０８０万方数据［９］ｃａｉＪｉａｍＩＩｇ，ｃ蚰如ｓＥＪ，Ｓｈ蚰ｚｏｕｗｅｉ．ＡｓｉｎｇＩｌｌ盯ＶａＩｕｅ强他ｓｌＩ－０ｌｄｉｎｇＡ１９０蒯珊五叫Ｍａｔｒｉ】【Ｃｏｍｐｌｅｔｉ蚰．ＳＩＡＭＪ叫ｍａｌ∞Ｏ—ｍｉ盟・ｔｉｏｎ，２０１０，２０（４）：１９５６—１９８２［１０］ｃ∞ｄｈＥＪ，Ｐｌ蛐Ｙ．Ｍｇｔｒｉｘｃｏｍｐｌｅｔｉｏｎｗ油Ｎｏｉ辩．ＰＴＤｃｏｆｔｌｌｅＩＥＥＥ，２０１０，９８（６）：９２５—９３６［１１］Ｙ觚Ｈｕｉ，Ｊｉｎｚｈｏｎｇ，Ｙ龃ｇＪｉｎ鄹ｍ．Ｎｏｎ—ＮｅｓａｔｉｖｅＴｗｏ—ＤｉｍｅｎｓｉｏｎａｌＰｒｉｎｃｉｐａｌＣｎｍｐｏｎｅｎｔＡｎａｌｙｓｉｓ柚ｄＩｔｓＡｐｐＨｃ撕仰ｔ０ＦａｃｅＲｅｃｏ口ｉ—ｔｉ帆．ＰａｔｔｅｍＲｅｃｏ印ｉｔｉ帆锄ｄＡ眦ｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ。２００９，２２（６）：８０９—８１４（ｉｎＣｌｌｉｎｅ∞）（严慧，金忠，杨静宇．非负二维主成分分析及在人脸识别中的应用．模式识别与人工智能，２００９，２２（６）：８０９—８１４）［１２］ｗａｎｇＨ硼铲ｈｅＩｌｇ，ＡｈｕｊａＮ．Ａ１钿ｓ∞Ａｐｐｒｏｘｉｍａｔｉ仰Ａｐｐ啪ｃｈｔｏＤｉ啪心。础酊Ｒｅｄｕｃｔｉ０１１．Ｉｎｔｅｍａｔｉ仰ａｌＪｏｕｍａｌ０ｆＣ咖ｐｕｔｅｒＶｉｓｉｏｎ，２００８，７６（３）：２１７—２２９［１３］Ｙ如ｓｈｕｉｃｈｅｎｇ，ｘｕＤｏｎｇ，Ｙ肌ｇＱｉ蛐ｇ，ｅｔ出．Ｍｕｌｔｉｌｉｎ髓ｒＤｉ８一函ｍｉｎ明ｔＡｎａｌｙｓｉ８ｆｏｒＦ∞ｅＲ∞唰ｔｉｏｎ．ＩＥＥＥ１＇砌ｓ∞Ｉｍａｇｅ胁ｃ∞ｓｉｎｇ，２００７，１６（１）：２１２—２２０［１４］ＫｏｌｄａＴＧ，ＢａｄｅｒＢｗ．１ｈｓｏｒＤ∞咖ｐ∞ｉｔｉｏ咕如ｄＡｐｐＩｉｃ撕∞８．ＳＩＡＭＲｅｖｉｅｗ，２００９，５ｌ（３）：４５５—５００［１５］Ｉ丑ｔｌｌａｕｗｅｒＬＤ，Ｍｏ∞ＢＤ，Ｖ蛐ｄｅｗａｕｅＪ．ＡＭｌｌｌｍｉｎｅ盯ｓｉｎｇｕｌ耻ＶａｌｕｅＤｅｃｏｌｎｐ鸺ｉｔｉｏｎ．ＳＩＡＭＪｏｕｍａｌ帆Ｍａ晡ｘＡｎａｌｙｓｉｓ肋ｄＡｐｐｂ—ｃａｔｉｏｍ，２０００，２ｌ（４）：１２５３一１２７８【１６］Ｌ砒ｈａｕｗｅｒＬＤ，ＭｏｏｒＢＤ。Ｖ柚ｄｅｗａ】ｌｅＪ．０ｎ山ｅＢｅｓｔＲａｎｋ・ｌ蚰ｄＲａｎｋ一（焉，恐，…，ｈ）Ａｐ鲫Ｄ】【ｉｍａｔｉ帆０ｆＨｉｇｌ＂ｒ－ＯＤｄｅｒＴ∞＆∞．Ｓ工ＡＭＪ叫ｍａｌｏｎＭ曲奴Ａｎａｌｙ８ｉｓ蚴ｄＡｐｐｌｉｃａｔｉｏｌｌｓ，２０００，２ｌ（４）：１３２４一１３４２［１７］ＴｏｍａｓｉＧ，ＢｍＲ．ＰＡＲＡＦＡｃ粕ｄＭｉｓｓｉｎｇＶａＩ吣．ｃｈ锄ｏｍ试ｃ８ａｎｄＩｎｔｅＵｉ酽ｍｔＬａｂｔＨ咖ＩｙＳｙ８ｔｅｍｓ，２１００６。７５（２）：１６３一１８０［１８］ｕｕＪｉ，ＭｔＩｓｉａｌｓｋｉＰ，Ⅵ‰ｋａｌＰ，甜口ｆ．Ｔｅｎｓｏｒｃｏｍｐｌｅｔｉ叫ｆｏｒＥ出－ｍａｔｉｎｇＭｉｓｓｉＩＩｇＶａｌｕ镐ｉＩｌＶｉｓｕａｌＤａｔａ／／Ｐｒｏｃｏｆｔｌｌｅ２０ｔｌＩＩＥＥＥｈＩ－悃ｍｔｉ∞ａｌＣｏｎｆｅ陀ｎｃｅ仰Ｃ伽聊ＪｔｅｒＶｉｓｉｏｎ．Ｋｙｏｔｏ，Ｊａｐ锄，２００９：２１１４—２】２ｌ张量补全算法及其在人脸识别中的应用
作者：作者单位：刊名：英文刊名：年，卷(期)：
史加荣， 焦李成， 尚凡华， SHI Jia-Rong， JIAO Li-Cheng， SHANG Fan-Hua
西安电子科技大学智能信息处理研究所智能感知与图像理解教育部重点实验室,西安,710071模式识别与人工智能
PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE2011,24(2)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_mssbyrgzn201102014.aspx
