（信号与信息处理专业论文）信号稀疏表示理论及应用研究.pdf

信号稀疏表示理论及应用研究 摘要 信号处理在各个领域的应用中一直占有重要地位，特别是随着现代生活的信息膨 胀，对数据进行更简洁的表示成为了一个热点问题。信号的稀疏表示是二十世纪九十年 代初提出的一种新兴的信号表示方法，作为一种信号的基础研究，它在人脸识别、图像 去噪、图像复原、波达方向估计、盲源分离等领域都有很重要的意义。 稀疏表示最初提出是伴随着一种新的贪婪算法出现的，而后学者们又对其不断完 善，在对其数学模型进行研究的过程中产生了各种新的评价准则和分解算法。本文对信 号的稀疏表示基本技术进行了研究和学习，主要在分解算法和字典学习，并将其用在经 典的图像去噪问题中。首先介绍稀疏表示的国r 彤 t - 研究现状，并且对该课题现在面临的 主要问题及难点进行阐述。最后从信号逼近理论出发给出稀疏表示的数学模型，度量标 准和一些重要定理。 本文重点对基于，范数的稀疏分解算法进行研究，其中s l 0 算法是从一种全新的角 度对稀疏问题进行实现，在算法中引进了一个连续函数和控制因子，在理想情况下对他 们进行操作后，得到的算法就可以求解原来的非凸优化问题。 本文实现的主要内容如下： 在对s l 0 算法的研究中，首先对算法中的重要参数进行实验分析，并根据实验得到 的数据来设置s l 0 算法中的参数。然后将稳定的s l 0 算法与其他凸优化方法进行比较， 实验结果证明s l 0 算法在运行速度和信号重构质量上具有优势。 在得到一个稳定的s l 0 算法后，将其用于稀疏表示的另一重要研究领域，即字典学 习。字典学习算法中的k s v d 字典训练算法由于其具有较低的计算成本，因而更具有 实用性，但是原算法中是使用o m p 算法进行稀疏编码，得到的是固定数目的表示系数， 这样不能保证在不同的应用中的字典质量，所以采用s l 0 算法来进行k s v d 算法的稀 疏编码，改善编码质量。因为稀疏表示是对信号的本质刻画，更能够体现信号的特点， 所以可以将稀疏表示应用于图像去噪。具体方法采用贝叶斯最大后验估计( m a p ) 方法求 解原图像的一个估计结果，从而得到去噪图像，并将此算法与性质良好的非局部均值滤 波去噪进行对比。实验结果证明了基于稀疏表示的图像去噪算法在去噪的质量上更加优 披。 关键词：稀疏分解；稀疏表示；字典；s l 0 算法 a b s t r a c t s i g n a lp r o c e s s i n gp l a y s a ni m p o r t a n tr o l ei nv a r i o u sf i e l d sn o w a d a y s e s p e c i a l l y w l t ht h e e x p l o s i o no fi n f o m a t i 0 i l ，c o n c i s er e p r e s e n t a t i o no f t h ed a t ah a sb e c o m eah o t1 s s u e s p a r s e r e d r e s e n t a t i o no fs i g n a l si sp r e s e n t e d i nt w e n t i e t hc e n t u r ya tt h eb e g i n n i n go f t h en i n e t e e n s , w h i c hi san e ws i g n a lr e p r e s e n t a t i o nm e t h o d a sp a r to f b a s i cr e s e a r c ho f8 i g n a l ，i t1 su s e dm f a c er e c o g n i t i o n ，i m a g ed e n o i s i n g ，i m a g er e s t o r a t i o n ，d i r e c t i o no fa r r i v a l e s t i m a t i o n , b l i n d s o u r c es e p a r a t i o na n do t h e rf i e l d s - s p a r s er e p r e s e n t a t i o n i s p u tf o r w a r do r i g i n a l l y a c c o m p a n i e dw i t h an e wg r e e d y a l g o r i t ，t h e nc o n t i n u o u s l yi m p r o v e db yt h es c h o l a r s v a r i o u sn e w e v a l u a t l o nc m r l o na j l d d e c o m p o s i t i o na l g o r i t h ma r eg e n e r a t e dw i t h t h er e s e a r c ho ft h em a t h e m a t i c a lm o d e lo fs p a r s e r e d r e s e n t a t i o n t h i sp a p e rr e s e a r c h e dt h eb a s i ct e c h n o l o g yo fs p a r s e s i g n a lr e p r e s e n t a t l o n ， m a i n l va b o u tt h ed e c o m p o s i t i o na l g o r i t h m a n dd i c t i o n a r yl e a r n i n g ，a n du s e di n c l a s s l c a l i m a g ed e n o i s i n gp r o b l e m s f i r s t ，t h ep a p e ri n t r o d u c e d t h er e s e a r c hs t a t u so ft h e5 p 盯s e r e p r e s e n t a t i o na th o m ea j l da b r o a d ，a n ds t a t e d t h em a i np r o b l e m sa n dd i f f i c u l t i e si n t h e r e s e a r c h t h e n ，i tg a v es p a r s er e p r e s e n t a t i o nm o d e l ，m e t r i c sa n d s o r e ei m p o r t a n tt h e o r e m s f r o mt h es i g n a la p p r o x i m a t i o nt h e o 阱 t h i sp a p e rr e s e a r c h e dt h es p a r s ed e c o m p o s i t i o na l g o r i t h mb a s e d o nl pn o 咖，mw h l c h s l oa l g o r i t l l r l li m p l e m e n t e ds p a r s em e t h o di na n e wv i s i o n i nt h ei d e a lc o n d i t i o n sw i t ht h e c o n t i n u o u s 如n c t i o na n dc o n t r o lf a c t o ri n v o l v e d ，t h ea l g o r i t h m c a ns o l v et h eno n 。c o n v e x o p t i m i z a t i o np r o b l e m s i nt h i sp a p e r , t h em a i n c o n t e n t sa r ea sf o l l o w s ： i nm er e s e a r c ho fs l oa l g o r i t m ，t h ep a p e ra n a l y z e dt h ei m p o r t a n tp a r a m e t e o f t h e a l g o r i 也m ，狃ds e tt h ep a r a m e t e r so ft h ea l g o r i t h ms l oa c c o r d i n g t ot h er e s u l t so ft h e e x p e r i m e n t ，a n dt h e nc o m p a r e dt h es t a b l e s l oa l g o r i t h ma n do t h e rc o n v e x0 p t l m l z a t l o n m e t h o d s t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tt h es l oa l g o r i t h mh a sa d v a n t a g e sm t h e o p e r a t i n gs p e e da n ds i g n a lr e c o n s t r u c t i o nq u a l i t y a r e rg e t t i n gas t a b l es l oa l g o r i t h m ，t h ep a p e ra p p l i e d i tt ot h es p a r s er e p e s e n t a t l o nm a 1 1 0 t h e ri m p o r t 砌r e s e a r c hf i e l d ，n a m e l yt h ed i c t i o n a r y l e a r n i n g y h ek - s v dd i c t i o n a r y 1 e 锄i n ga l g o r i m mo fd i c t i o n a r yl e a r n i n gi s m o r ep r a c t i c a lb e c a u s eo fi t 5l o wc o m p u t a t l o n c 呲b u tt h eo r i g i n a la l g o r i t l l r l lu s i n gt h eo m pa l g o r i t h mf o rs p a r s ec o d i n g ，g x v e 8 at l x e d n u m b e ro fc o e f f i c i e n t s ，a n dd i c t i o n a r yq u a l i t yi si n a p p r o p r i a t ei n ad i f f e 。e n ta p p l l c a t l o n ，8 0 u s i n gs l oa l g o r i t h m ，k s v da l g o r i t h ms p a r s ec o d i n gi m p r o v e sc o d eq u a l i t y b e c a u s eo f 8 p a r s e 。e p r e s e n t a t i o no fs i g n a li st h ee s s e n t i a lr e p r e s e n t a t i o no fs i g n a l ，b e t t e ra b l et or e n e c t t h e8 1 9 n 龇c h a r a c t e r i s t i c st h a no t h e rr e p r e s e n t a t i o nm e t h o d s ，s o i ti sa d v i s a b l et ou s es d a r s e r e p r e 8 e n t a t l o n l ni m a g ed e n o i s i n g t h es p e c i f i cm e t h o di sb a s e do nt h et r a i n i n gr e s u i t s o f d l c 1 0 n a r y , u s l n gam a x i m u map o s t e r i o r ( m a p ) e s t i m a t i o nm e t h o dt oo b t a i na ne s t i m a t i o n r e s u l to ft h eo r i g i n a li m a g e ，a n dt h ed e n o s i n gi m a g e ，a n dc o n t r a s t e dt h e c a l c u l a t i n gm e t h o d a n dn o n l o c a lm e a nf i l t e r i n g d e n o i s i n gm e t h o d t h ee x p e r i m e n t a lr e s u l t ss h o wt h a ti m a g e d e n 0 1 8 1 n ga l g o r i t h mb a s e do nt h es p a r s er e p r e s e n t a t i o nh a ss u p e r i o r q u a l i t yi nd e n o i s i n g f i e l d s 。 k e yw o r d s ：s p a r s ed e c o m p o s i t i o n ；s p a r s er e p r e s e n t a t i o n ；d i c t i o n a r y s ；s l oa i g o r i t i l l l l ： i m a g ed e n o i s i n g 第1 章绪论 第l 章绪论 1 1 课题研究背景和意义 人类获取的信息，主要来自听觉和视觉，分别为2 0 和6 0 ，只有不超过2 0 的信 息来自于味觉、触觉、嗅觉等。由于图像具有直观、具体、生动、高效等特点，使其成 为人们获取和识别信息的源泉和重要手段。现今社会是一个信息社会，多媒体技术是现 代社会不可或缺的并已渗透到人们的日常生活。人们进行信息交流、处理、传输和存储 主要采用声音、文字、图像或视频等多种媒体。能够直观地表达视觉信息的数字图像是 目前常用的图像形式，但图像中的海量数据不适合于实际的存储、传输和理解。因此， 寻求高效的图像表示方法显得尤为重要。 在给定条件下的信号模型及信号处理方法可以确保精准地对信号进行测度、加工、 分析、量化和压缩。信号处理算法的结构与性能受其模型的影响很大，合适的模型能对 信号与异常、信息与噪声等直接区分，带限模型为基本的信号处理模型。基于这种模型 下的奈奎斯特采样定理能够使用下限采样频率而准确地重建原始信号，这个定理已经成 为现代数字信号处理的基础i lj 。 百年来，信号处理经历了从正交基变换到小波变换，多尺度变换，2 0 世纪最后1 0 年又过渡到过完备表示，图1 1 展示了这个过程【2 ，3 j 。现在在信号的各种应用领域都已经 掀起了使用稀疏模型的热潮。这种模型在分析信号时是用基元或冗余字典中较少的元素 的线性组合来进行的，它的一个最经典的应用就是静态图像压缩标准j p e g 及静态图像 压缩标准的拓展标准，即j p e g 2 0 0 0 4 , 5 】。d c t 变换和离散小波变换分别是j p e g 标准和 j p e g 2 0 0 0 的基础。d c t 变换有利于图像的压缩的原因是较大的d c t 系数聚集于图像 的左上角，这一部分能够近似的表达图像内容。而小波系数中大幅值( 大幅值是远远大 于小幅值的，所以可以将小幅值近似看为零) 的系数要少于d c t 的，因此它的系数也更 为稀疏，进而小波变换可以用相对较少的数据对更广泛的类型的图像做近似，这就是 j p e g 2 0 0 0 的压缩性能比j p e g 更好的原因。在图像处理领域中最基本的问题是图像表 示，它直接影响着图像压缩、编码、增强、分割、检索、去噪的效果。在小波变换提出 后，为了解决高维空间数据稀疏表示问题，提出又一类新的图像表示方法，即多尺度几 何分析方法【3 1 。有关图像的多尺度几何分析理论与方法尚属于发展阶段，是一个较为前 沿的研究领域。目前，在国内，多尺度几何分析理论及其应用是图像稀疏表示方面的研 究热点，其中，最为突出的是超完备图像稀疏表示。经长期的研究，研究者们发现灵长 目动物的视觉皮层是在稀疏规律下对外界信号进行表达的。一些研究结果阐明，细胞感 哈尔滨： 程大学硕士学位论文 ；宣；i ；i i ；i i i ；| ；i ；i ；i i ；i 受野上某一特定位置中的方位信息可以通过v 1 区的简单细胞检测的，并且视觉皮层中 v 1 区第四层的细胞量要比视网膜及外侧膝状体中的神经节细胞数多很多，所以v l 区的 细胞对外侧膝状体细胞所传递的信号的特征表达具有过完备特性，其信号编码表示空间 的大小远远超过信号空间【6 。12 1 。以上的研究结果表明，过完备稀疏表示可以更好的近似 神经信息群体分布式表达结果。 图1 ：l 信号表不的发展 信号与图像的过完备表示理论是法国科学家m a l l a t 在1 9 9 3 年提出的，基于过完备 g a b o r 字典完成信号的稀疏分解，创造性的提出基于贪心策略的匹配追踪( m a t c h i n g p u r s u i t ，m p ) 算法，为这种理论奠定基础【l3 1 。之后，n e f f 和z a k h o r a 在甚低比特视频编 码中运用了m p 算法及过完备g a b o r 字典【l4 | 。现今，过完备稀疏表示的理论基础仍不完 善，而且具有超高的计算复杂度，是科学研究及实际应用的瓶颈，由于它在人类视觉神 经中的独特价值，所以对它的研究是一个必然的过程。 1 2 国内外研究现状 信号的稀疏表示从提出至现在已近2 0 年，并且已经吸引了国内一批研究者注意， 而国内目前的研究主要集中在稀疏分解算法的复杂度的降低及各种应用领域，孙玉宝等 将其用在图像处理的反问题中，李恒建等将陶提出的字典的树形结构表示应用在图像去 噪领域，梁巍等提出了一种基于残差比阂值的迭代终止条件匹配追踪稀疏分解方法，有 效地控制了传统迭代终止条件无法选择迭代终止阈值的问题，邓成志等同样为解决稀疏 分解的速度问题以及收敛，提出了非相干子字典多原子快速匹配追踪算法，刘华丹等提 出了一种冗余字典下的信号稀疏分解新方法，提高算法复杂度，并解决了过匹配问题 1 5 , 1 6 , 1 7 , 1 8 , 1 9 】。张海等则对( o ，1 ) 范围内的正则算子进行理论分析得到对于稀疏问题，“，正 则子可以替代( o ，1 ) 范围的，。正则子【2 0 l 。另外还有很多研究者将其应用到人脸识别及 m u l t i 1 a b e l 分类中，也取得了一些进展【2 1 1 。 而这种方法最具有影响力的一个应用就是2 0 0 6 年e c a n d e s 、t a o 、r o m b e r g 和d d o n o h o 这些统计数学领域里的优秀科学家共同提出的压缩感知理论f c o m p r e s s i v e 第1 章绪论 s e n s i n g ，c s ) 瞄引。这个理论突破了奈奎斯特采样限，将原来的信号采样理论延伸为信息 采样理论，为信号处理领域的研究者开辟了新的研究方向，r i c e 大学的研究者们已经开 始研制单像素相机，这个设备的好处就是感光元件数量大大降低，但是又不损失分辨率。 相信随着c s 的蓬勃发展，也将掀起对信号稀疏表示研究的热潮。 信号的稀疏表示可用图1 2 形象的展示，可以看到整个理论最关键的就是稀疏分解 算法和过完备原字库的研究，下面从这两方面阐述稀疏表示的国内外研究现状。 图1 2 稀疏表不的过程 1 2 1 稀疏分解算法的发展 2 0 世纪9 0 年代初有人提出了信号稀疏分解的概念，它从一出现就受到了研究者们 的关注，并出现了很多的分解算法。因为其算法复杂度大，所以初期的工作都集中到如 何降低其复杂度，找到其快速的算法。目前，已经出现了非常多的分解算法，下面对其 进行详细介绍。 ( 1 ) 松弛优化算法。 其基本思想是用凸的稀疏性度量函数来近似的求解非凸的，。范数，或者研究新的易 于求解的稀疏性度量函数做标准，这样做的目的是为了用现有的高效优化算法来处理这 个n p 难问题，从而使其复杂度降低，其中的算法主要包括了基追踪( b a s i sp u r s u i t ) 算法、 框架算法( m e a t h o d o ff r a m e ，m f ) 、交替投影算法、s l o ( s m o o t hl o n o r m ) 算法、g p s r 算 法( g r a d i e n tp r o je c t i o ns p a r s er e c o n s t r u c i t o n ，g p r s ) 、迭代收缩算法，f o c u s s ( f o c a l u n d e r d e t e r m i n e ds y s t e ms o l v e r f 0 c u s s l 算法等【2 3 , 2 4 , 2 5 , 2 6 , 2 7 】。其中m o f 算法为了降低算 法的复杂度，使用可导的7 ，范数替代原来的，。范数做稀疏性度量，不过这样分解系数的 稀疏性得不到保证。而基追踪算法是用，。范数来替换“范数，这样就变成了线性规划的 问题，能够使用线性规划( l i n e a rp r o g r a m ，l p ) q 的单纯形( s i m p l e x ) 法或内点( i n t e r i o r p o i n t ) 法求解，其字典中的原子个数为l ，其时间复杂度为o w5 ) ，并且该方法能使稀疏 哈尔滨工程大学硕士学位论文 性保持，特殊情况下，能使其与f n 范数获得同样的稀疏结果口8 i 。但是对于l p 的求解方 法，在维数较高的f - i 题中是不可行的。s l 0 范数方法是采用光滑函数厂( s ) 来近似f 0 范数， 并且它与，。范数的近似度以及函数的光滑程度可以用参数d 来调节，而且算法局部最优 解的问题可通过g n c 策略来解决，它与内点法相比，速度更快，大约快两个数量级， 并且效果与内点法相当甚至更好。d o n o h o 提出了软闽值与硬闽值收缩的方法，它实际 上是在正交基下，与厶范数的稀疏近似问题的最优解。迭代收缩算法就是在它的基础上 发展而来的，在( 紧) 框架系统下，使用迭代收缩的策略能够获得最优的稀疏近似。而且 在字典由多个正交基级联构成时，能够使用交替的软阈值收缩算法快速的求解b p 问题。 另外，大量的基于投影的稀疏分解算法被研究者们提出来，比如交替投影( a l t e r n a t e p r o j e c t i o n ，a p ) 、g p s r 等。对于基追踪问题，g p s r 算法用带约束形式的凸二次规划问 题来替换线性的规划模型，并使用梯度投影法进行求解，而且算法之所以可以快速收敛， 原因在于：使用b a r z i l a i b o r w e i n 算法对迭代步长进行线搜索。交替投影算法用求解两 个凸集的交点的方法对，。问题近似，然后通过交替投影策略找到这个交点。c h a r t r a n d 通 过使用非凸优化问题来近似组合优化问题，并使用找寻其驻点来近似求解【2 。总的来说， 冗余字典本身快速的变换与重建算法的存在与否决定了松弛优化算法的有效性，比如针 对正交基与紧框架字典其运算复杂度较低，但是针对一般的过完备字典，其具有较低的 效率，并且针对一般的过完备字典，该算法一般要从计算机的内存中提取过完备原字库， 这对于高维数据显然行不通，比如处理一幅2 5 6 2 5 6 的灰度图像，如果使用冗余度为6 的冗余字典，则其所对应的矩阵是6 5 5 3 6 3 2 7 6 8 ，要把这个矩阵存在内存里一般需要 2 4 g 的空间，以目前的p c 配置，根本无法做到。 ( 2 ) 贪婪追踪算法 贪婪追踪( g r e e d yp u r s u i t ，o p ) 算法是在给定的限制条件下进行不断迭代，从而在追 踪算法的帮助下，逐次挑选出字典中与待分解信号最为相近的原子的一种逼近过程，并 具有比松弛优化算法更低的复杂度。匹配追踪算法是第一种应用于稀疏表示问题的追踪 算法，它对待分解信号的处理是采取逐步逼近的策略，每次迭代过程都是由冗余字典中 挑选出与当前待分解信号相关性最强的原子，计算原子与信号的投影值决定二者是否相 似，m p 算法主体思想简单，易于应用，是比较活跃的稀疏分解方法 1 3 】。其中，针对原 子选择策略与残差更新提出很多改进算法，例如，高分辨率匹配追踪、正交匹配追踪、 s t a g e w i s eo m p ( s t o m p ) 、梯度追踪、c h a i n i n g 追踪、贪婪的基追踪等阻3 0 ，3 1 ，3 2 ，3 3 1 。匹配 追踪虽然与基追踪算法依据截然不同的策略求解稀疏分解问题，但是二者确有着千丝万 缕的关系。 第l 苹绪论 等价性定理：若给定信号u ，字典，记的相干系数为，则将其定义为 肛= 翌a xi 妒q ，啦l ，f 是字典中所有原子参数的指标集。如果信号u 在字典下可表 叫，y i ，t j 7 1 。1 ， 示为“= 口，且满足蚓i ，n 为信号的长度，所以这个字典是过冗余的， 用字典中少量的原子对信号进行逼近，即： ，=口，gm gy ( 2 4 ) 一厶“yy 厶一叶j l 、l 而由于n m ，所以也把这种逼近称为稀疏逼近。这种系数a 。不是唯一的，可以 通过应用的不同而灵活的选取系数，一般的从众多系数的选择中选取最为稀疏的系数， 也即系数矩阵里为零值的占大多数，仅含少量的非零系数，但是只需要通过这几个大系 数就能够很好的展现出信号的本质特征。这样在实际应用中我们仅用少量的几个系数就 可以对信号进行描述，简化后续处理的工作量。这个稀疏度可以用，。范数进行度量，建 立如下的数学模型并将下面的问题称为r 问题： r l p o ：m i nc c 。，s t 六，= a g 女 ( 2 5 ) 七譬0 ，。范数是，。范数中p - - - 0 的情况，定义为口中非零元素的个数。将字典中的所有原 子作为列向量依次排列，可以构成一个l ( l n ) 的矩阵，记为。式( 2 - 6 ) 给出了用 矩阵( 向量) 的形式来表示原有的稀疏表示模型。 m i n i i a s t f = a ( 2 - 6 ) 图2 1 用更形象的示意图来描绘这个矩阵的分解过程，可以看到系数矩阵a 中的非 零值仅占很小的比例，达到了稀疏的要求。 2 1 2 稀疏性的度量 在上一节中我们看到，过完备稀疏表示问题可以用一个有约束的，。范数问题等价和度 量，但是由于，。问题是n p h a r d 问题，现有的算法无法解决，所以只能另辟蹊径用其他 方法对它进行近似。，。范数准则可以在对稀疏表示系数的非零个数度量的同时兼顾信号 的重建误差，在数学分析理论中通常是使用，。范数进行稀疏度量，将，。范数定义如下【5 0 】： ? , d p ，= le i x ri ( 2 7 ) 第2 章信号的稀疏表示理论 n l | l l l l = 卜 图2 1 过完备稀疏表示 当o m 来表示，那么就会有下面两个问题【5 2 】： q 1 ：什么条件下可以唯一的确定稀疏解? q 2 ：能否确定候选解是全局最优也就是保稀疏的呢? 研究者们经过严密的推导得到下面的定理，回答上面的问题。 首先给出两个定义： 定义1 ：矩阵a 的s p a r k 是让a 中具有相关性的最少的列数。 s p a r k ( a ) = r a 拈i 。nd 。s t a d = 0 ( 2 9 ) 定义2 ：字典的相干系数为字典中不同的原子问的内积的绝对值的最大值。 p = m a x l ( ，) i ( 2 - 1 0 ) f # jo 正交基的相干系数为0 ，字典的相干系数越小，与正交基越相似。当相干系数为1 时，则意味着字典里至少有两个一样的原子。 定理2 1 唯一性定理：如果给定的欠定系统存在某一稀疏解仗满足 蚓l 。 印砒 ) 2 ，其中s p a r k ( c d ) 定义为字典中任意一组原子线性相关时所需的最小 个数，则该解是唯一的且为最稀疏解。 定理2 2 如果一个线性方程组厂= a 有一个解a ，满足蚓l 。 ( ，g ，) f 1 ，g ，( d ( 2 - 1 1 ) 所以，厂被分解为： f = ( f ，9 1 ) g i + r l ( 2 - 1 2 ) r 1 f 是第一次匹配后的残余。易知，r , f 与g 。是正交的，由此可以推导出如下关系： 2 - g 。) | 2 + 懈f 畦 ( 2 - 1 3 ) 从信号空间的角度出发，( ，g ，) g ，极大化意味着g ，是信号所在h i l b e r t 空间中和f 方向 最靠近的过完备原子库中的单位向量。再对残差r ，厂作类似匹配：从巾中再按照上面的 方法选出与r ，厂最为匹配的第二个原子。然后不断进行上面的同样的分解过程，至第k 次时有： r 女f = ( ，g ) g + r 川f ( 2 - 1 4 ) 2 - m g 。) l2 + 慨砸 ( 2 - 1 5 ) k = o 当残差r 帆厂足够小，也就是信号的稀疏表示跟信号的近似程度够好时，就可以停 止迭代。假设信号的长度为，要求m n 。 下面以g a b o r 原子的形成过程为例，给出一个具体的构造方法【5 5 | 。 首先，g ( f ) 取高斯型窗函数： g o ) = p 。r( 2 2 2 ) 对其进行尺度变换，时移及调制，能够获取形如式( 2 2 3 ) 的时频原子： g r o ) ：g f 竺1 c o s ( v ，+ c o ) ( 2 - 2 3 ) v s、s 这里，) ，= s ，甜，v ，国) 为时频参数，s 为伸缩因子( 或尺度因) ，甜为g ( f ) 的平移因子( 或位 移因子) ，v 为一般意义下的频率，为相位。所形成的这种时频原子就是g a b o r 型原子。 能够用下面的标准对以上的时频参数进行离散化处理：y = a jp a 7 a u ，k a a v ，i a 6 0 ) ，这 里，a = 2 、a u = l 2 、a v = 丌、a c o = 丌6 、0 ，l 0 9 2 。v 、0 p n 2 一，“、0 k 2 j “， 0 f 行的字典称为过 完备的字典。虽然i n = 门的情况，例如，离散傅里叶变换，也可以充分的得到这样的分 解，但是使用过完备字典在许多不同的应用中有大量的优点。 在所有这些应用中，我们将要用较少数目的原子用于表示信号，也就是相当于寻找 欠定线性方程组的稀疏解的问题。严格来说对于获取方程组的稀疏解，等价于寻求最小 ，。范数的解的问题，也就是最少非零项的组合。随着维数的增多寻找最小，。范数不是一 个多项式时间的问题，因此研究人员考虑用其他方法解决。众多成功的方法之一是b p ， b p 是寻找最小，范数的解。这样可以通过线性规划的方法很容易的寻找到解。这个b p 方法是基于大型观测方程组，并且可以证明在r i p 条件下，最小，范数的解同样也是最 小，。范数的解。通过使用快速l p 算法，特别是l p 内点法，那么大型规划问题及成千的 源信号和矩阵成为易于处理的。但是，这种方法仍然非常的慢，近年的几个研究者提出 了对b p 的改进，提高了算法的速度和处理噪声的效果。另一个算法体系是迭代更新加 权最小二乘算法，这种方法是在，范数的基础上研究的，f o c u s s 算法是一个重要的组 成。比b p 更快，但是它的估计质量差一些，特别如果大多数稀疏解的非零项不是非常 的小。 相反对于过去的方法，s l o 方法是基于直接处理最小，。范数的。这种方法在同样或 更好的精度的情况下比b p 方法要快2 3 个数量级。 哈尔滨工程大学硕士学位论文 ；i ；i 1 i ii 以下面的数学模型来说明问题。对于一个x = a s 欠定方程，通过观测信号x ，如何 求解稀疏信号s ，对于一个2 维的空问，它的求解可以表示如下： j m i ns 1 i ，+ s 2 p ( 3 - 1 ) l s j x = 口l s l + 口2 s 2 在不同的p 值下，我们将得到不同的解，图3 1 可以很好的描绘这个问题，图中当sp 1 时目标函数与约束条件所形成的曲线只有一个交点，且在竖轴上，这说明求得的解s ，和 s ，中必然有一个是为0 的；而p = 2 时，交点变成了两个，表示有两个非零解，因此没 有达到稀疏表示的目的。 0 p 1p = 1 、= q 气+ a l 、 一二纱逵这 二弋沁形。一 3 p ：= 2 、 l s 2 ， 蕊，+ 、_ 一 7 7 _ ，二! i s 、x = a ，s ，+ ( 一、，。： 1i 、 、 p jj j i 心 夕一 ? 、。一一一一。 图3 1不同范数约束得到稀疏解可能性示意图 为了得到( 3 1 ) 的最稀疏的解，必须寻找最小乇范数，也就是分量非零的最小个数，所以 不再借助7 l 范数，于是文献【2 4 中提出了一种平滑的如范数来近似求解，算法性能在后 面可以得到很好的证明。 第3 章基于l p 范数稀疏分解算法的研究 3 2s l o 算法 ，。范数的难题是主要在寻找最小值的计算问题以及对噪声非常敏感两个方面，而这 些都是因为它是向量的一个非连续函数，所以主要的想法是：使用一个连续函数来逼近 这个不连续函数，而且通过最小化这个连续函数，从而实现f n 范数最小化，比如最陡下 降法等求解极值的算法。在定义这个连续函数的过程中，需要一个控制参数仃，通过使 这个参数不断的减小至零来控制近似过程的质量。 首先，给出一个变量的函数： 厶( s ) = e x p ( 者) ( 3 2 ) 可以知道： 墓妥厶c s ，= 雾二i 巴 。r 厶c s ， ：，善i 芒l 姜： c 3 - 3 ， 然后定义： f o ( s ) = l ( s ，) = e x p ( - s ) 2 0 2 ) ( 3 4 ) 从式( 3 3 ) 可以很明显看出，当仃值较小时，例“门一c ( s ) ，而当仃j0 时，它们就相 等。因此，当仃值很小时，得到最小，。范数解，可以通过最大化c ( s ) 。万决定了c ( s ) 函数的平滑性，仃越大，则c ( s ) 越平滑，但是更不接近f 0 范数解；当仃值越小时，c ( s ) 越接近，。范数的近似。但是当o - 特别小时，c ( s ) 非常不平滑，则得到很多局部最大值， 要求它的最大值并不容易；反之，当仃越大时，则c ( s ) 平滑性越好，得到最大值更为 简单。因此通过逐渐改变盯的值，将其值从大到小改变，这样对于每一次新的迭代，o - 和c ( s ) 的初始值，相对于上一次迭代只是轻微变化的，而上一次迭代的结果是较大值仃 得到的，这样就可以使得算法尽可能不陷入局部最大值中。 除了式( 3 2 ) 给出的高斯族函数，还有很多函数只要满足式( 3 3 ) 就可以用来逼近，。范 数，比如三角函数族和截取双曲函数，分别给出如下所示： 厶( s ) = 当仃足够大时，在工= a s 下最大化c ( s ) ，对于高斯函数族而言，相当于求解x = a s 的，范数。 1 3 仃 h h 矿 扩 j 1 3 ， 一 厶 一 1 3 0 ，i = 1 , 2 ，r ，其余元素为0 ，为了运用时更方便，所以 这里的仃，是按数值的大小顺序排列的，这些值被称为奇异值。同时要申明的一点是，s v d 的结果并不唯一。图4 1 可以更形象的观察奇异值分解的矩阵结构，这种分解最大的特 点是大多为0 ，图中白色区域代表对角元素为0 。 上式就是最初的奇异值分解公式。可以证明矩阵a 的s v d 能用如式( 4 2 ) 的r a n k 1 矩阵的和来表示： a = 叮l u l v l 。+ + o - ，甜，v ，1 ( 4 2 ) 这说明了a 可以只由u 的前厂个行向量( 用u ，表示) ，v r 的前r 个列向量( 用以7 表示) ，以 及左上角的大小为r r 的子矩阵( 用，) 来决定，用图4 2 表示。我们会发现，矩阵4 中 有m f 个元素，u ，中有m 厂个元素，y r 中有，z 个元素，而，只需要存储主对角线 上的r 个非零元素即可，如果数据用奇异值分解形式存储的话，则只需要对( m + ”一1 ) r 个元素进行存储，并且如果r 是绝对小于m ，胛的，那么将数据转为矩阵形式，进而用 奇异值分解方法进行存储可以达到压缩的目的。这是奇异值分解的一个很重要的性质， 第4 章基于s l 0 算法的字典训练方法研究 i i 对于字典训练这种计算量特别大，内存要求相对较高的算法来说，应用奇异值分解的这 个特点，可以大大减小计算量，而且节省硬件成本。另外，同样有价值的一个特点是， 任意的矩阵其奇异值分解都是存在的，这样就不用拘泥信号的形式了。 ff 曰= 圜曰粤p 图4 1 疗 图4 2 去零后的形式 2 k 均值聚类算法 在统计和数据挖掘领域中，k m e f l n s 聚类方法是在最近邻域原则下的无监督学习方 法，这种方法应用范围极广，对所处理的数据没有类型上的要求【5 8 1 。具体的做法是：首 先任意找出尼个点，将这些点设为初始聚类中心，接下来计算其他样本点与这些中心点 之间的欧氏距离，将非聚类中心点归类到最近聚类中心所在的类。 这个算法每进行一次迭代，均检测各个样本点有没有正确的归类，当某样本被错误 划分时，则继续校正。当所有的样本点都校正结束时，则对当前的类别划分重新计算聚 类中心，进而替换原有的中心点，然后继续迭代，若在某一次迭代之后，全部的样本点 均被正确的归类，那么聚类中心点将不再更新，表示这种聚类准则已经收敛，走出迭代， 算法完成。对于寻求最佳码本的问题，算法最终达到的目标是，采用最近邻原则，寻找 可以表示样例集合 y i 髭。的最佳码本，等同于寻求式( 4 3 ) 的最小化问题： m i n y 一以v i ，3 k 薯= ( 4 - 3 ) 算法的具体步骤如下： ( 1 ) 初始化，构建初始码本矩阵c 【o ) r “芷。 ( 2 ) 稀疏编码阶段，将训练样例集合y 分成k 个集合， r ? = t v i 尼，f | 少，一c ，一l i ： y i - - c y 一虬j 。 哈尔滨工程大学硕士学位论文 ( 3 ) 码本更新阶段，对于码本c 卜1 中的第后列，根据公式= 击- 对其进行 j kj ，月5 “” 更新。 ( 4 ) 重复( 2 ) ，( 3 ) 至达到目标函数最小。 3 由k m e a n 到k s v d 算法 k s v d 算法和k 均值聚类算法有着很深的联系，当k s v d 算法中要求的每个信号 只一个原子来近似时就退化为k 均值聚类算法【5 8 】。 对图像进行稀疏分解，字典的结构是一个重要的方面，原始的字典构造方法是对符 合条件的窗函数进行伸缩、平移和调制得到的，但对于图像信号特定的处理，训练字典 更能符合其特征。在各种现有的字典训练方法中，k s v d 算法其计算成本较低，更适 合图像信号的处理，本文的字典训练就是结合s l 0 算法与k s v d 算法进行的。 采用稀疏表示方法表示一个样例信号，该过程可以数学化描述为： m 争i y 一蹦s u b j e c t t o v i ，l 。- t o ( 4 4 ) ( 4 4 ) 式就是要求解的目标函数。 首先进行稀疏编码，这一过程是在假设字典d 固定情况下，来求解满足条件的稀疏 矩阵x 。其中， y d x l ；= 怫一眈，幢 ( 4 5 ) 贝i j ( 4 5 ) 被分解成个如下问题： m i n 她一d x ，耐2 s u b j e c tt ol l x i 扎- t of = 1 2 一n ( 4 6 ) 经过稀疏编码后，再做字典及稀疏矩阵的更新。首先假设字典d 和系数矩阵x 的其余 项是固定的，只研究字典中任意一列d 。和相对应的系数，也就是在系数矩阵中的第k 行，记做x ；。再次回到目标函数，则惩罚项就能够用下式来表示： 眵删= 峰咖轷卜黔卜小忙。叫蚓4 忉 从上面的公式可以看出，矩阵d