基于字典学习的非线性降维方法

郑思龙　　李元祥　　魏宪　　彭希帅

基于字典学习的非线性降维方法

郑思龙1李元祥1魏宪2彭希帅1

目前，众多的数据降维（Dimensionality reduction，DR）方法（如经典的PCA（Principle component analysis），ISOMAP（Isometric mapping））能够使降维后的数据保留原始信号的重要特征，但是从降维后的数据中很好地恢复出原始信号仍旧是一个挑战.近年来，稀疏表示（Sparse representation，SR）在信号重构研究中受到广泛关注，信号可以利用过完备字典中少数原子的线性组合来描述.本文提出一种基于字典学习的非线性降维方法.从高维输入信号到低维特征的降维过程中，期望一些重要的几何特征（内积、距离和夹角）得以保留，同时又能够从低维数据中恢复出原始信号.为达此目的，本文采用CDL（Concentrated dictionary learning）算法训练一个字典对（高维字典D和低维字典P），使高维原始信号的能量能够聚集于低维子空间中.字典D用来获取稀疏表示系数，字典P是D的直接降维采样，CDL算法能够保证P聚集D中的大部分能量.这样，信号的降维与恢复问题就转变为字典对的训练问题，信号的降维即为从D到P的能量保留过程.实验表明: CDL可在RIP（Restricted isomery property）条件的限制之外具有一定的信号重建能力，能在更低的维度条件下恢复图像，优于传统的压缩感知方法.此外，在噪声较大的情况下，CDL图像压缩效果优于JPEG2000.

数据降维，稀疏表示，压缩感知，字典学习

引用格式郑思龙，李元祥，魏宪，彭希帅.基于字典学习的非线性降维方法.自动化学报，2016，42（7）:1065-1076

观测空间中的数据达到上千维甚至上万维时，巨大的数据计算量对计算系统来说是一个挑战.对图像、音频、视频和网络搜索来说，通过降低数据维度来提高处理速度显得尤为重要.

为解决“维数灾难”问题，许多文献假设数据具有低维的固有属性（例如：低秩、稀疏性、低维流形），然后根据这些假设建立各种不同的模型.一个简单有效的假设是：观测数据落在一个低维流形子空间中.基于这样的假设，利用PCA（Principlecomponent analysis）、LDA（Linear discriminant analysis）、ICA（Independent component analysis）、LPP（Locality preserving projection）等不同的线性降维算法，对高维空间做线性投影处理，以得到数据所在的子空间［1］.另一方面，非线性降维算法（例如ISOMAP（Isometric mapping）、LLE （Locally linear embedding））在降维处理中，可保留数据的非线性几何结构［1］.

上述两类算法侧重于挖掘和发现原始数据在低维空间中的内在属性，而对数据的恢复能力仍有待改进.压缩感知（Compressed sensing，CS）算法的出现，使得我们能从更低的采样信号中（低于奈奎斯特采样率）较好地恢复原始信号［2］.

CS在减少观测次数来表示一个有限维向量x∈Rm的同时，更加注重于原始信号x的稀疏性.假设y=Φx，其中Φ∈Rd×m，d≪m是观测到的信号，由于观测矩阵Φ的行数小于列数，通过观测信号y来获取原始信号x是不适定的反问题.但是如果信号x在给定的字典D下足够稀疏，那么在一定的条件下，只要维数d不低于某个限定值，观测信号y可以唯一重构x［3-4］.求解原始信号x在字典D下的稀疏表示α的过程可表述为

我们认为x=Dα+ε，其中ε是高斯白噪声，α 是x在D下的稀疏表示.大多数图像、语音等自然信号，在某些字典下都有很好的稀疏性.

式（1）所表达的稀疏编码框架具有很强的鲁棒重建能力，并且在数据压缩、超分辨率重建、去噪、分类等领域成功应用.一方面，任务驱动的数据降维方法认为特定的任务（如图像识别、数据可视化等）需要特定的降维方法将数据从高维降至低维，因此提取的特征也不一样.文献［5-7］认为在稀疏域中，信号的几何关系是一种有效的结构信息.文献［5］通过字典学习，得到原始信号的稀疏表示系数α，利用α的几何结构信息，建立一个通用有效的框架来解决不同任务的字典学习问题.类似地，文献［6］依据α的几何结构信息，直接利用PCA作用于稀疏系数α上，实现数据降维.文献［7］有针对性地保留稀疏域中信号间的内积关系，通过学习得到原始信号到降维信号的线性投影来完成数据降维.另一方面，数据驱动的数据降维方法采用将CS框架与高斯随机投影结合的框架.文献［8］利用高斯随机矩阵将原始特征映射到观测空间，证明在低维空间中并没有发生重大的信息丢失，并给出结论：低维空间的特征保留了原始信号的主要信息.类似地，文献［9-12］假设信号是在一个嵌入高维空间的低维流形中，因此在降维的过程中，一些重要的几何信息（例如：角度、距离）得以保留.文献［13］认为通过学习得到的观测矩阵比随机投影更加有效.上述基于CS框架的方法都必须服从RIP（Restricted isometry property）条件，这对于数据降维中的可视化（2D或者3D）来说是不适合的.而且，虽然文献［9-12，14］给出了将CS框架搭建在流形上的理论分析，但是实际可行的算法很少.

上述工作都是基于一个先验给定的字典D，不需要学习字典.更进一步的研究认为：在采样和重建的过程中不需要知道字典D的先验知识，而是从训练样本中学习字典（本文称为“在数据降维中的字典学习方法”）.盲压缩感知是这个框架下一个典型的例子，在严格的条件下，字典D可以通过低维的观测值训练学习而来［15-16］.文献［17-20］认为高维信号X与低维信号Y之间，在字典Dx和Dy下共同享有稀疏表示系数.字典对Dx和Dy是分别对应高维数据x和降维数据y的高维字典和低维字典，是从数据降维过程中学习而来的.

本文结合降维算法中保留数据结构特征和CS算法中数据恢复能力的优点，提出聚能量字典学习（Concentrated dictionary learning，CDL）算法. CDL算法既能够在CS中RIP下界的维数限制之外具有一定的信号重建能力，又结合了流形的特点，在降维后的空间中保留原始信号中的特征（例如：内积、距离、夹角）［21］.并且，利用训练得到的字典，仿照CS算法设计算法框架.为验证算法的有效性，将CDL与CS+K-SVD（K-means-singular value decomposition）［22-23］等算法进行数据恢复对比实验，结果表明本文算法相比传统算法有明显的提升.同时，进行了图像数据的3维观测性实验，本文算法表现良好.在噪声污染严重的图像压缩实验中，本文算法相对于JPEG2000，也具有一定程度的优势.

其余章节安排如下：第1节回顾CS算法及KSVD字典训练算法.第2节阐述本文字典学习算法推导及思路，对于内积、距离、夹角特征推导出字典对D和P的具体形式.第3节进行图像重构、3D可视化和图像压缩的对比实验.最后，总结全文，讨论本文算法的应用拓展性.

1　CS及字典学习回顾

本文算法基于CS算法框架，下面对CS算法框架进行简要的回顾.CS算法框架如图1所示，X为原始信号，Y是观测值，Φ是观测矩阵，α是稀疏表示系数，D是字典.典型的CS算法选取Φ为高斯随机矩阵，Φ：Rm→Rd，d≪m，y=Φx；字典D由标准正交基组成，如小波基、离散余弦变换（Discrete cosine transform，DCT）字典）.

CS通过正交匹配追踪算法 （Orthogonalmatching pursuit，OMP）［4，24-25］解决如式（2）的最优化问题得到稀疏系数α，最后由字典D恢复原始信号x：x=Dα.

其中，ε∈R+.在此过程中，低维观测值y∈Rd的维数d受到一定条件的限制：d>O（Cslog（k/s）），其中，C为常数，C∈（0，1），s是稀疏系数的稀疏性，k是字典的原子的个数，这种限制被称为RIP条件［3-4］.一旦采样信号y的维数低于d，那么就无法从y中恢复原始信号x，或者恢复的效果很差.例如，如果需要同时将数据可视化（二维或三维）和信号恢复作为目标，那么传统的CS算法远远满足不了实际需求.

图1CS算法示意图Fig.1　CS algorithm schematic

在CS算法框架中所用到的字典往往是给定的正交基字典.不同于给定字典的思路，K-SVD算法提供了很好的字典学习方法［22-23］.从训练集中训练学习得到的字典比给定的正交基字典表现更加出色，通过字典D能够得到最佳的稀疏系数.它的优势主要表现在：

1）灵活性：能够与任何的匹配追踪算法相结合，确保所选的匹配追踪算法能够适合于所要求的时间限制；

2）有效性：K-SVD算法复杂度低，具有高效性和快速收敛性，更新字典原子和稀疏表示系数是同时进行的.

2CDL算法

以CS框架为基础，利用K-SVD字典算法的优点，本文提出基于字典学习的信号降维和重建算法.该算法可在RIP条件的限制之外具有一定的信号重建能力，即能够从较低维的观测值中恢复出原始信号.

原始信号x可看作是高维稀疏系数α通过字典D，在低维子空间中的一种表现形式.不同于观测矩阵Φ的做法，本文直接将稀疏系数α通过映射函数P（α，y）投影到另一低维子空间y中，如式（3）所示.那么信号x与y之间的映射关系F（x，y）就可以通过稀疏系数α搭建桥梁，建立模型.理论证明该做法具有保留几何结构特性的作用［21］.

为了得到映射函数P（α，y），可简单地认为α到y的投影是通过一个矩阵P来实现的.而矩阵P是通过字典D获取的.那么式（3）可以转为如下表达形式：

假设已知P与D的关系，那么x到y的映射函数F（x，y）也就确定下来.在本文中，仅考虑x和y之间的关系有：内积、距离、夹角.那么x到y的降维算法就转换为字典D到P的函数关系，如式（5）所示.维空

设间X 中R=m［x 的1，xn2，个···输，x入n］信∈号.R给m×定n字表典示D高，α=［α1，α2，···，αn］∈.Rk×n是X在字典（Dx，y下），的n个稀疏表示系数给定映射函数 F Y=［y1，y2，···，yn］∈Rd是低维空间中的特征.那么通过稀疏系数α搭建的桥梁，（X，Y）可以表示为如下形式：

其中，噪声ε1∈Rm，ε2∈Rd.

2.1内积关系

当期望X内部xi与xj之间的内积关系能在Y中保留下来时，定义将式（6）带入其中，得到关于P的最优化问题：

为了解决上述最优化问题，定义核函数：

那么f2（xi，xj；yi，yj）的表示如下：

假设（xi，xj）和（yi，yj）内部相互独立，那么：

其中，σ1，σ2为ε1，ε2的方差，由式（11），式（7）最终转化为求解下式：

2.2距离关系

同样地，若期望在Y中保留X 内部xi与 xj之间的距离关系，定义写成如下形式：

同样地，将式（6）带入式（13）得到一个关于P的最优化问题：

上式中第二部分h2（xi；yi）推导如下：

可以看出，得到的结果与内积关系式（12）相同.

2.3夹角关系

定义X和Y内部的夹角关系为

事实上，在处理数据集时，常常将数据集归一化，即：||xi||2=1.可以看出夹角关系与内积关系是相似的.

2.4理论推导

从内积、距离、夹角关系中可看出，需要解决如下问题：

将上式重写为

通过求解式（17）得到的特征Y的维数可以比CS算法更低，因此该算法框架可在CS算法的RIP限制之外具有恢复信号的能力［25］.

由式（18），可认为字典P是字典D的PCA降维，不妨假设：

当字典维数较低时，DCT及K-SVD字典在降维后，无法保留较多的主成分.因此，本文通过训练字典，使得能量聚集于较低的维度内（见图4），保留较多的主成分，以满足式（19）的需求.

文献［25］中提到D与P是具有如下条件的矩阵：

且

式（21）说明，奇异值分解中的Θ总能量是保持不变的，如果Θ中靠后的（m-d）个奇异值越小，那么前d个奇异值越大.因此，为了使字典D前d维聚集更多的能量，应满足下述条件：

1）原始信号X在字典D下表示系数足够稀疏；

2）给定正整数q，当d＜q时，D的奇异值分

解：D=UΘVT中，关于奇异值Θ有：

其中，Θd是奇异值Θ取前d行d列，td是设定的主成分阈值.

3）为了保证D的满秩性，要求奇异值Θ后m-d个奇异值很小却非零.

当D满足上述条件时，字典P可以保留字典D中较多的主成分.设D的奇异值分解为

式（19）中，取A=Ud，则有：

式（25）中，如果能够保证Θd足够大，即：

2.5字典训练

通过上述分析，明确训练字典D的两个目标：

1）字典D要使得测试图像在该字典下的表示系数足够稀疏.

为了达到上述目标，利用式（25）的性质，令：

其中

令

更新奇异值分解：D=UΘVT中Θ：

令

将上述更新过程写作：

输入.训练图集X，迭代次数T.

输出.训练好的字典D、P.

初始化.从训练图集中随机选取16×16的图像块，并将每个小块排列成列向量形式xi（256×1），令X=［x1，x2，···，xn］.初始化DCT字典D.

第一阶段.稀疏编码

1）稀疏编码

对每一个xi，利用匹配追踪算法得到稀疏表示系数αi［24-25］：

α←minα12||X-Dα||22+λ||α||1其中，

第α二=阶［α 段1.，α字2，典···，α更n］新∈Rk×n. DDD

2）对DTD作奇异值分解：DTD=uΛvT；

5）仿照K-SVD 字典学习算法［22-23］，将Ek限定在wk集合中，得到

6）对EkR做奇异值分解做如下更新=∆（1，1）n1；

第三阶段.字典 PPP 计算

8）根据式（23）字典D的奇异值分解得到Ud，则字典

2.6训练结果

图3所示的CDL字典是利用自然图像（如图2所示）训练得到的，见第3.1节描述.根据式（23）字典D的奇异值分解得到Ud（d=16），令即可得到对应的低维字典.字典P如图3（b）所示.

CDL字典能够将主成分集中于较低的维数中，具有能量聚集的作用，如图4所示.当选取90%主成分（td=0.9）时，CDL字典的能量集中于前16维，而K-SVD字典则需要148维，DCT字典需要207维.当字典的维数降得较低时，DCT，K-SVD字典在降维后，无法保留较多的主成分.

图2 自然图像示例Fig.2　Natural image examples

图3 由CDL算法训练得到的字典对Fig.3　Coupled dictionaries trained by CDL

图4　不同字典奇异值的分布（当选取90%主成分（td=0.9）时，图中的点代表所需的字典维数.DCT字典: 207，K-SVD字典:148，CDL字典:16）Fig.4　Distribution of singular values from different dictionaries（When selecting 90%component of dictionaries（td=0.9），the dots represent the required dimensions for different dictionaries.DCT:207，K-SVD: 148，CDL:16）

3　实验结果分析

为了验证本文算法的有效性，分别从图像重构与数据可视化、RIP条件验证和图像压缩三个方面进行实验和分析.实验中的图像包括：自然图像、USPS手写数字和PIE人脸图像.

3.1图像重构和3D可视化

本文的对比算法有：CS+K-SVD、PCA、LPP［1］.低维空间的维数分别为：d=8，16，32，64.CS+KSVD算法中，降维采样矩阵分别用高斯随机阵（GAU）和主成分分析（PCA）.重构图像的质量评价用峰值信噪比（Peak signal to noise ratio，PNSR）表示.

1）自然图像重构

自然图像集包括13张图片［19］，尺寸为256×256或者512×512，如图2所示.训练时，随机选取图集中的图像块13 000个（16×16）.分别用K-SVD算法和本文CDL算法训练字典.测试用的图像分别为：Lena（512×512）、Boat（512×512），测试结果如图5、图6所示.由表1和表2可看出，CDL重构效果明显优于其他算法，比CS+K-SVD（GAU）高出3 dB以上.

表1　Lena图像重构对比Table 1　Comparison of reconstructed Lena images

表2　Boat图像重构对比Table 2　Comparison of reconstructed Boat images

2）手写数字重构和3D可视化

手写数字图片来自USPS库1，包含9298个图片（16×16）.选取其中每类数字的一半做训练，分别降至8，16，32和64维，利用训练得到的CDL字典对剩余的一半数字做重构测试.如图7及表3所示，给出d=16时各种方法的重构结果，并统计出不同方法恢复结果的平均PSNR值.表4统计不同维数下各方法重构的PSNR平均值，可看出CDL的重构效果优于其他算法.

1http：//www.cad.zju.edu.cn/home/dengcai/Data/data.html

图5Lena图像重构对比（原始图像、CS+K-SVD（GAU）、CS+K-SVD（PCA）、PCA、LPP、CDL，d=16）Fig.5 Reconstructed images of Lena（Original image，CS+K-SVD（GAU），CS+K-SVD（PCA），PCA，LPP，CDL，d=16）

图6Boat图像重构对比（原始图像、CS+K-SVD（GAU）、CS+K-SVD（PCA）、PCA、LPP、CDL，d=32）Fig.6 Reconstructed images of Boat（Original image，CS+K-SVD（GAU），CS+K-SVD（PCA），PCA，LPP，CDL，d=32）

图7　USPS手写数字重构对比（从上到下:原始图像、CS+K-SVD（GAU）、CS+K-SVD（PCA）、PCA、CDL，d=16）Fig.7　Reconstructed images of USPS（From top to bottom:original image，CS+K-SVD（GAU），CS+K-SVD （PCA），PCA，CDL，d=16）

同时，在USPS中取3类数据（数字0、3、4），共3229个.利用CDL、CS+PCA［6］和PCA算法降至3维后，给出3维平面上的数据分布，如图8所示.图8给出的3D可视化结果表明，通过CDL降维后的数据可分性很强，而CS+PCA由于受到RIP条件的限制，导致算法失效，具体分析见第3.2 节.在图像重构方面，CDL仍然能够将降至3维后的数据恢复，如图9所示.

图8　USPS手写数字三类样本（0、3、4）可视化结果（d=3）Fig.8　The visualization results of USPS（0，3，4）（d=3）

表3　USPS手写数字重构对比（d=16）Table 3　Comparison of reconstructed USPS（d=16）

表4　USPS手写数字重构对比（d=8、16、32、64）Table 4　Comparison of reconstructed USPS （d=8，16，32，64）

图9　USPS手写数字三类样本（0、3、4）图像重构对比（从上到下:原始图像、CDL、CS+K-SVD（GAU））Fig.9　Reconstructed images of USPS（0，3，4）（From top to bottom:original image，CDL，CS+K-SVD（GAU））

图10　PIE人脸图像重构对比（从上到下:原始图像、CS+K-SVD（GAU）、CS+K-SVD （PCA）、PCA、CDL，d=16）Fig.10　Reconstructed images of PIE（From top to bottom:original image，CS+K-SVD（GAU），CS+K-SVD （PCA），PCA，CDL，d=16）

3）人脸重构

人脸图像来自PIE库1（16×16）.选取其中的10类样本1700个图片，一半用于训练字典，另一半用于测试，分别计算将数据降至8、16、32和64维时的PSNR值，并统计不同方法的PSNR平均值（如图10和表5所示）.从表5可看出在PIE上CDL也优于其他算法.

另外，文献［6］中提到：CS+PCA在满足RIP条件的情况下可以得到很好的降维效果，可以用于数据可视化和数据分类.针对上述PIE库，用本文中的字典P和直接对α做PCA降维的方法得到降维数据（d=64），本文算法可以有效恢复图像；而文献［6］采用CS+PCA方法，则无法恢复出原始数据（如图11所示）.

从上述实验可以看出，本文CDL算法的图像重构效果明显优于其他算法.

表5　PIE人脸图像重构对比（d=8、16、32、64）Table 5　Comparison of reconstructed PIE （d=8，16，32，64）

3.2RIP条件验证

另外，回顾第3.1节中CS+PCA［6］在USPS数据集上3D可视化的结果（如图8所示），在实验中，k=784，s=10，RIP条件为：d>18.94.当维数降至3维时不满足RIP条件限制，其低维（3D）嵌入也丧失了原始数据的可分性结构.CS算法只有在严格的条件限制下具有一定的信息保持能力，详见文献［9］.

图11PIE人脸图像重构对比（从上到下:原始图像、CS+PCA、CDL）（d=64）Fig.11　Reconstructed images of PIE（From top to bottom:original image，CS+PCA，CDL）（d=64））

图12　Lena图像和Barara图像重构对比（d=4）Fig.12　Reconstructed images of Lena and Barara（d=4）

表6　USPS手写数字三类样本（0、3、4）图像重构对比Table 6　Comparison of reconstructed USPS（0，3，4）

利用USPS数字0、3、4做图像重构实验时，针对RIP条件，对比CDL和CS+K-SVD的性能.首先，分别用CDL和K-SVD训练字典，字典规格均为256×784，即k=784.实验中稀疏系数的稀疏性s=6，则RIP条件：d>12.7.CDL算法中利用字典P降维；CS算法中，降采样矩阵为高斯随机阵.实验中两种算法同时对数据降至12维和3维，实验结果如图9和表6所示.可以发现，当d=12时，在RIP条件临界值附近，CS+K-SVD算法依然有效，但是当维数更低时（d=3≪12），CS+K-SVD算法无法完成图像重构；而CDL在d=3仍然能够恢复数据.因此，CDL能够在RIP条件限制之外仍具有较好的图像重构能力.

3.3图像压缩

从压缩的角度出发，为了最大限度地减少数据量，在本文算法的基础上，不重叠的取出测试图像块.实验中，仍然取图像块大小为16×16，并分别降维至64、32、16、8，即分别对应压缩比CR为 4、8、16和32.测试图像为Lena（512×512），分别在无噪声，添加方差为10、20、40的噪声情况下（如图13～图16所示），进行压缩重建.CDL与JPEG2000进行对比，用PSNR来评判解压图像质量的优劣，如表7～表10所示.

实验表明：1）无噪声时，JPEG2000解压效果优于CDL.2）但在噪声环境下，CR较低时，CDL优于JPEG2000；随着噪声的增加，CDL相比JPEG2000的优势越明显.由于在重构的过程中，当原始信号X通过字典D转化为稀疏系数α表示时，此过程中存在一定去噪的功能，而Y在字典P转化为α表示时，恢复过程同样有一定的去噪功能.因此，本文CDL算法对噪声具有很好的鲁棒性.

表7　Lena图像压缩重建（无噪声）Table 7　Comparison of reconstructed Lena（No noise）

图13　Lena图像压缩重建（从左到右:原始图像、JPEG2000（38.45dB）、CDL（30.56dB））（无噪声，CR=16）Fig.13　Reconstructed images of Lena（From left to right:original image，JPEG2000（38.45dB），CDL（30.56dB））（No noise，CR=16）

图14　Lena图像压缩重建（从左到右:原始图像、加噪图像（28.15dB）、JPEG2000（32.04dB）、CDL（30.24dB）（σ=10，CR=16））Fig.14　Reconstructed images of Lena（From left to right:original image，noisy image（28.15dB），JPEG2000 （32.04dB），CDL（30.24dB）（σ=10，CR=16））

图15　Lena图像压缩重建（从左到右:原始图像、加噪图像（22.09dB）、JPEG2000（25.93dB）、CDL（29.34dB）（σ=20，CR=16）Fig.15　Reconstructed images of Lena（From left to right:original image，noisy image（22.09dB），JPEG2000 （25.93dB），CDL（29.34dB）（σ=20，CR=16））

图16　Lena图像压缩重建（从左到右:原始图像、加噪图像（16.09dB）、JPEG2000（19.76dB）、CDL（26.96dB）（σ=40，CR=16））Fig.16　Reconstructed images of Lena（From left to right:original image，noisy image（16.09dB），JPEG2000 （19.76dB），CDL（26.96dB）（σ=40，CR=16））

表8　Lena图像压缩重建（σ=10）Table 8　Comparison of reconstructed Lena（σ=10）

表9　Lena图像压缩重建（σ=20）Table 9　Comparison of reconstructed Lena（σ=20）

表10　Lena图像压缩重建（σ=40）Table 10　Comparison of reconstructed Lena（σ=40）

4　结束语

本文提出一种聚能量字典学习算法，应用于图像降维与恢复.基于字典学习的理论，本文算法通过字典对（高维字典D和低维字典P），能够在原始信号X到特征Y的降维过程中保留高维信号的本质特征，并且能够在RIP条件限制之外仍具有较好的信号重构能力.在自然图像、人脸图像、手写数字上的实验验证了本文算法的优越性.

从X到Y降维的同时，因为Y中保留了X的几何结构特征，因此可以从Y中恢复出原始信号X.算法本身并不局限于内积、距离、夹角等特征，只要能找到合适映射关系，可推导出不同的模型，以实现不同任务需求：如目标识别、目标跟踪、视频分析等.

References

1 Van der Maaten L J P，Postma E O，Van den Herik H J. Dimensionality reduction：a comparative review.Journal of Machine Learning Research，2009，10：66-71

2 Donoho D L.Compressed sensing.IEEE Transactions on Information Theory，2006，52（4）：1289-1306

3 Cand´es E J，Romberg J，Tao T.Robust uncertainty principles：exact signal reconstruction from highly incomplete frequency information.IEEE Transactions on Information Theory，2006，52（2）：489-509

4 Tropp J A，Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit.IEEE Transactions on Information Theory，2007，53（12）：4655-4666

5 Mairal J，Bach F，Ponce J.Task-driven dictionary learning.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（4）：791-804

6 Gao J B，Shi Q F，Caetano T S.Dimensionality reduction via compressive sensing.Pattern Recognition Letters，2012，33（9）：1163-1170

7 Gkioulekas I A，Zickler T.Dimensionality reduction using the sparse linear model.In：Proceedings of the 2011 Advances in Neural Information Processing Systems.Granada，Spain：Morgan Kaufmann，2011.271-279

8 Calderbank R，Jafarpour S，Schapire R.Compressed Learning：Universal Sparse Dimensionality Reduction and Learning in the Measurement Domain.Technical Report，Princeton University，USA，2009

9 Baraniuk R G，Wakin M B.Random projections of smooth manifolds.Foundations of Computational Mathematics，2009，9（1）：51-77

10 Hegde C，Wakin M B，Baraniuk R G.Random projections for manifold learning.In：Proceedings of the 2008 Advances in Neural Information Processing Systems.Vancouver，Canada：Morgan Kaufmann，2008.641-648

11 Chen M H，Silva J，Paisley J，Wang C P，Dunson D，Carin L.Compressive sensing on manifolds using a nonparametric mixture of factor analyzers：algorithm and performance bounds.IEEE Transactions on Signal Processing，2010，58（12）：6140-6155

12 Baraniuk R，Davenport M，DeVore R，Wakin M.A simple proof of the restricted isometry property for random matrices.Constructive Approximation，2008，28（3）：253-263

13 Weiss Y，Chang H S，Freeman W T.Learning compressed sensing.In：Proceedings of the 24th Annual Allerton Conference on Communications，Control and Computing.Illinois，USA：Citeseer，2007.535-541

14 Baraniuk R G，Cevher V，Duarte M F，Hegde C.Modelbased compressive sensing.IEEE Transactions on Information Theory，2010，56（4）：1982-2001

15 GleichmanS，EldarYC.Blindcompressedsensing. IEEE Transactions on Information Theory，2011，57（10）：6958-6975

16 Silva J，Chen M H，Eldar Y C，Sapiro G，Carin L.Blind compressed sensing over a structured union of subspaces. eprint arXiv：1103.2469，2011.

17 Zeyde R，Elad M，Protter M.On single image scale-up using sparse-representations.In：Proceedings of the 7th International Conference on Curves and Surfaces.Avignon，France：Springer，2012.711-730

18 Yang J C，Wang Z W，Lin Z，Cohen S，Huang T.Coupled dictionary training for image super-resolution.IEEE Transactions on Image Processing，2012，21（8）：3467-3478

19 Yang J C，Wright J，Huang T S，Ma Y.Image superresolution via sparse representation.IEEE Transactions on Image Processing，2010，19（11）：2861-2873

20 Adler A，Hel-Or Y，Elad M.A shrinkage learning approach for single image super-resolution with overcomplete representations.In：Proceedings of the 11th European Conference on Computer Vision.Heraklion，Crete，Greece：Springer，2010.622-635

21 Wei X，Kleinsteuber M，Shen H.Invertible nonlinear dimensionality reduction via joint dictionary learning.In：Proceedings of the 12th International Conference on Latent Variable Analysis and Signal Separation.Liberec，Czech Republic：Springer，2015.279-286

22 Aharon M，Elad M，Bruckstein A.K-SVD：an algorithm for designing overcomplete dictionaries for sparse representation.IEEE Transactions on Signal Processing，2006，54（11）：4311-4322

23 Elad M，Aharon M.Image denoising via sparse and redundant representations over learned dictionaries.IEEE Transactions on Image Processing，2006，15（12）：3736-3745

24 Pati Y C，Rezaiifar R，Krishnaprasad P S.Orthogonal matching pursuit：recursive function approximation with applications to wavelet decomposition.In：Proceedings of the 27th Asilomar Conference on Signals，Systems and Computers.Pacific Grove，USA：IEEE，1993.40-44

25 Tropp J A.Greed is good：algorithmic results for sparse approximation.IEEE Transactions on Information Theory，2004，50（10）：2231-2242

郑思龙上海交通大学航空航天学院硕士研究生.主要研究方向为图像处理，计算机视觉与模式识别.

E-mail:zhengsilong@sjtu.edu.cn

（ZHENG Si-LongMaster student at the School of Aeronautics and Astronautics，Shanghai Jiao Tong University.His research interest covers image processing，computer vision，and pattern recognition.）

李元祥上海交通大学航空航天学院副教授.2001年获得清华大学电子工程系博士学位.主要研究方向为遥感图像解译，图像识别，图像重构与评估，台风云图信息提取与汉字信息处理.本文通信作者.E-mail:yuanxli@sjtu.edu.cn

（LI Yuan-XiangAssociate professor at the School of Aeronautics and Astronautics，Shanghai Jiao Tong University.He received his Ph.D.degree from the Department of Electronic Engineering，Tsinghua University in 2001.His research interest covers remote sensing image interpretation，image recognition，image reconstruction and evaluation，typhoon image information extraction，and Chinese information processing.Corresponding author of this paper.）

魏宪慕尼黑工业大学电气与计算机工程系博士研究生.主要研究方向为几何优化，数据表达与图像处理.

E-mail:xianweich@gmail.com

（WEI XianPh.D.candidate in the Department of Electrical and Computer Engineering，Technische Univesitaet M¨unchen，Germany.His research interest covers geometry optimization，data representation，and image processing.）

彭希帅上海交通大学航空航天学院博士研究生.主要研究方向为图像处理，计算机视觉，机器学习.

E-mail:xishuaipeng@sjtu.edu.cn

（PENG Xi-ShuaiPh.D.candidate at the School of Aeronautics and Astronautics，Shanghai Jiao Tong University.His research interest covers image processing，computer vision，and machine learning.）

Nonlinear Dimensionality Reduction Based on Dictionary Learning

ZHENG Si-Long1LI Yuan-Xiang1WEI Xian2PENG Xi-Shuai1

Most classic dimensionality reduction（DR）algorithms（such as principle component analysis（PCA）and isometric mapping（ISOMAP））focus on finding a low-dimensional embedding of original data，which are often not reversible.It is still challenging to make DR processes reversible in many applications.Sparse representation（SR）has shown its power on signal reconstruction and denoising.To tackle the problem of large scale dataset processing，this work focuses on developing a differentiable model for invertible DR based on SR.From high-dimensional input signal to the low-dimensional feature，we expect to preserve some important geometric features（such as inner product，distance and angle）such that the reliable reconstruction from the low dimensional space back to the original high dimensional space is possible.We employ the algorithm called concentrated dictionary learning（CDL）to train the high dimensional dictionary to concentrate the energy in its low dimensional subspace.Then we design a paired dictionaries:D and P，where D is used to obtain the sparse representation and P is a direct down-sampling of D.CDL can ensure P to capture the most energy of D.Then，the problem about signal reconstruction is transformed into how to train dictionaries D and P，so the process of input signal X to feature Y is transformed into the process of energy retention from D to P.Experimental results show that without the restrictions of linear projection using restricted isometry property（RIP），CDL can reconstruct the image at a lower dimensional space and outperform state-of-the-art DR methods（such as Gaussian random compressive sensing）.In addition，for noise-corrupted images，CDL can obtain better compression performance than JPEG2000.

Dimensionality reduction（DR），sparse representation（SR），compressed sensing（CS），dictionary learning CitationZheng Si-Long，Li Yuan-Xiang，Wei Xian，Peng Xi-Shuai.Nonlinear dimensionality reduction based on dictionary learning.Acta Automatica Sinica，2016，42（7）:1065-1076

10.16383/j.aas.2016.c150557

2015-09-02录用日期2016-01-13
Manuscript received September 2，2015；accepted January 13，2016
国家自然科学基金（U1406404，61331015，41174164）资助
Supported by National Natural Science Foundation of China （U1406404，61331015，41174164）
本文责任编委胡清华
Recommended by Associate Editor HU Qing-Hua
1.上海交通大学航空航天学院上海200240中国2.慕尼黑工业大学电气与计算机工程系慕尼黑D-80333德国
1.School of Aeronautics and Astronautics，Shanghai Jiao Tong University，Shanghai 200240，China2.Department of Electrical and Computer Engineering，Technische Universitaet M¨unchen，Munich D-80333，Germany