两类混合范数极小化问题研究

硕士学位论文 要 压缩传感是2006年它突破了传统信号处理方式对采样率的要求, 能够从 低维样本空间重构出高质量的高维 信号, 大量节约了采样成本, 可应用在磁核共振、探地雷达、信源编码、人脸识别等多领域. 压缩传感的核心包括设计满足理的重构模型及精确的重构算法, 其中重构模型一般是含有两类或两类以上 混合范数的极小化问题, 本 文称这类极小化问题为混合范数极小化问题. 混合范数极小化问题除了在 压缩传感中, 还在电容层析成像等领域均有广泛的应用, 因此研究对这类问题具有一定的理论意义和应用价值. 本文对混合范数极小化的研究主要集中在以下两个方面: （1）结合实际提出了新的重构模型, 并在将 其转化为最小绝对偏差问题的基础上设计了有效的算法. 文中根据压缩 传感的背景, 对现有模型加以 改进, 提出了一类新的混合范数下极小化模型, 即最小二乘约束下1l 文中称为第一类混合范数极小化问题）, 并通过在研究最小二乘问题通解结构的基础上, 将问题转化为最小绝对偏差拟合问题; 结合最小 绝对偏差相关理论给出了第 一类混合范数极小化问题的最后通过数值例子说明该算法是有效的. （2）将已有的模型之一转化成带有边界 约束的二次规划问题, 并设计了有效的算法. 文中将已有的目标函数为1l 范数加权组合的极小化问题称为第二类混合范数极小化问题, 通过将其转化为带边界约束二次规划问题, 结合罚函数法、影法等, 给出了该模型转化后的问 题的一些算法; 最后通 过数值例子说明这些算法都是有效的. 关键字: 最小绝对偏差;法;二次规划;罚函数法;影梯度法;混合范数;压缩传感;电容层析成像 硕士学位论文 is a of is 006, it of on we of a of on be in of IP in is a or of we of be in is in so to of on In is as (1) to a is an on is on of to a of is in by in it is to as of , of to it is to a of of an is to of In to is (2) A is to it is is to of by a BR 士学位论文 号说明 # M . 1. 2. .I . () () 证明结束符号 M 维实数列向量空间 M N 阶实矩阵空间 向量的0l 量的1l 量的2l 量的无穷范数 集合 I 中元素的个数 缩写 矩阵的最小特征值 矩阵的最大特征值 矩阵 的 M P 广义逆 矩阵 的秩 迭 代的第 k 步值硕士学位论文 V 目 录 学位论文原创性声明及学位论文版权使用授权书 .要 .号说明 . 1 章 绪论 . - . - . - 量及测量矩阵. - 构模型及算法. - 文研究的主要问题 . - 文的具体工作安排 . - 第 2 章 第一类混合范数极小化问题研究 . - 小绝对偏差问题 . - 小绝对偏差解的存在性. - 小绝对偏差问题解的判定及唯一性.1 - 小绝对偏差问题解的算法.8 - 一类混合范数极小化问题 .4 - 小二乘问题（通解.5 - 一类混合范数转化为最小绝对偏差问题.6 - 法及数值例子.7 - 第 3 章 第二类混合范数极小化问题研究 .1 - 二类混合范数极小化问题的转化 .1 - 二类混合范数极小化问题的算法 .4 - 于外点罚函数法的算法.4 - 于 .6 - 于共轭梯度法的算法.0 - 值例子 .4 - 结论 .9 - 参考文献 .2 - 附录 .6 - 附录A .6 - 附录B 实例1) .2 - 附录C 例2） .3 - 致谢 .5 - 硕士学位论文 - 1 - 第 1 章 绪论 究背景及意义 传统的信号处理过程对采样率要求比较严格 , 一般要求采样率在信号最高频率的 2倍以上 , 即采样率要满足信号 采样的奈奎斯特定理 . 这对海量信息处理的采样设备提出了较高要求 , 甚至采样率的要求成了海量信息处理的瓶颈 . 2004 年 ,2框架 , 为海量信息处理提供了新的理论工具 . 它的主要思想就是将传统信号处理过程中的采样和压缩两个过程合二为一 , 降低了采样率 . 传统的信号处理过程分为采样、压缩、传输、解压缩（重构）四个步骤 , 先对原始信号按照奈奎斯特定理 所要求的频率进行采样 , 再对采集到的信息进行压缩 , 在信号压缩中时先对信号进行某种变换 , 如小波变换、离散余弦变换等 , 变换后保留绝对值较大的系数 , 并对其进行编码 , 舍弃了那些绝对值很小甚至几近于零的系数 . 通过这个数据压缩的过程 , 舍弃了采样所得的大部分无用的数据 , 压缩之后再进行传输和解压缩 , 虽然舍弃的数据对于信号的重构影响不大 , 但是在压缩阶段对信号采集造成了一定的浪费 . 在压缩传感理论中 , 将压缩的过程并入采样过程 , 直接采集压缩后的信号 , 再对采集到的信息进行传输、重构 . 这样以来 , 原本一个信号假设包含了十万个数据 , 按照传统的信号处理过程需要做一万次测量才能完整地重构原始信号 , 从而需要一万个方程才能解出这一万个未知量 假设原始信号具有稀疏性 , 并对稀疏信号进行非自适应线性投影 ,直接采集投影值（测量值） , 那么或许只要对原信号做两百次的测量 , 采集两百次测量值 , 就可以将这个信号完整地复原 , 这样以来就只要解一个只有两百个方程的方程组了 . 这样做的优点在于采集信号投影值数量要远远少于采样定理所要求的数量 , 突破了采样定理对采样数目限制的瓶颈 , 同时大大节约了采样设备的成本 . 传统模式： 采样 压缩 传输 解压缩压缩感知模式： 线性投影测量 传输 解码重构图 1 两种方式的信息获取与处理过程 压缩感知的理论框架主要包括 : 信号稀疏表示、测量和重构模型及算法三个方面 , 下两类混合范数极小化问题研究 - 2 - 面对其每个方面进行简述 . 号稀疏表示 一个信号如果它只有少数的非零分量, 那么就称其为稀疏信号,自然界里的信号一般来说不具有稀疏性质,但是可以通过下列变换使其稀疏: 假设一个长度为 N 的一维信号 f ,( )12, ,.,= ,12, ,., 为一组标准正交基（称为变换基,通常的变换基有离散余弦变换基、离散小波变换基、快速傅里叶变换基、 ,那么 f 可以表示为 1=. （ 此时 即 并称 f 为可稀疏信号. 如果信号不能用标准正交基（称为变换基,通常的变换基有）来稀疏表示时, 可用冗余字典55稀疏表示. 另外 那么就称 f 是可压缩的, 同时若 个, 则称 f 为 疏的, 或者称 f 的稀疏度为 K . 量及测量矩阵 假设已知一个测量矩阵M , 以及某未知信号在该测量矩阵下的线性测量值, 那么信号重构就是解方程组 . （ 但是当 M N . ()当 0 时, 由于 ()10y 及上面的讨论知 f 是分段线性函数, 硕士学位论文 - 9 - 由其图形知 f 在处达到最小. （）同理当 0 时, 可任取11 , ,使 ( ) ( ) . 根据上面的讨论得如下引理 引理 8在一维情况下, 存在 p , 1, 2,p n , 使得 ()1在处达到最小. 关于一维情形我们做如下讨论, 假设 ( )01,2ix = 且11yx x+ , 那么 111111112 21 x=+= 令1112j =, 根据11()p cx x=+ = , 易知是 () 解. 根据上述讨论定义如下分布函数 ()1x x= . 其中 :=. 由前面对点 p 讨论知, 在点,满足()12 , 当得 ()21,因为当21c = 时, 由 ()1() ,是连续函数, 21c = 是有界球面,知 ()上能取到最小值, 即 0t 满足()21,=. 于是对于任意的, 由上面讨 论知 0t 使得12,即 ()21,. 从而对于所有的有 () () ( )()11210,cf =+= + 现在取 12220=, 代入上式得 ( ) ( )0fc f . 这表明在紧集122|=外, 不存在 f 的最小值点, 因此 M S 是有界的. 易知 f 是连续的, 所以 f 在 S 中存在最小值点, 得证 M ; 另一方面若 () , 由于 是固定的数, 所以最终存在( )() . 事实上, 接下来讨论如何判断某一点 , 如果它属于 M 是否唯一的问题. 从现在开始, 我们讨论的问题都假设 ( ) = . 若不然 , 我们则称 化的 ;cZ k= , 称 退化的 . 定义 8任取 0 , 如果极限 ()( ) ( )0,ct + = . 存在, 称(),f c 为( )f c 的 方向导数 . 引理 8点属于 M , 当且仅当对于所有的 0, 满足(),0 ,即 . (其中 :0, :0, :0,:0,i i ir = . 一方面引理 诉我们, 对于所有的 0 满足 ( ),0 , 则点问题 () 的解. 若不然存在点 , , 使得 ( )()f . 取 ,)f c 是凸函数, 则会有 ( ),0 可以写成, 这是因为对于 ,0和 0t , 有 两类混合范数极小化问题研究 - 14 - () ( )()(),y ct xy cx t +=(其中 () (), ,ii ii = .（右边可以被写成 i + . (其中 : 0 , : 0, , : 0, , : 0,i = = 时, . 有了引理 我们仍难以判断某点是否属于 M , 因为它需要去验证（于所有的 0 是否满足, 这是难以做到的. 但是有了引理 文献48在它的基础建立一些更有效的判别方法. 根据引理 若, 则一定会有cZ k , 因此在找寻 M 中元素时, 我们可以限制到极值点上. 如果是非退化的, 我们可以很容易去判别它是否属于 M . 在这种情况下()k=, 对于 , 它能被 ,唯一的线性表示. ,ax j Z= . (记 ( )( ),c i . (引理 8: 是非退化的极值点, 当且仅当 1, 成立. 事实上, 取 0,kR , 则 硕士学位论文 - 15 - () ( )()()() ( ),y ct xy cx t t +=对于足够小的 0t , 此时可认为 ( ) ( ),t 的正负由 ( )故有 () ()( ) ( )( ) ( )()(),cc iZ c t t x t += + . 对 ()f 关于 ) ( ) ( ) ( )( ), = . (由（、 （ () ( ) ()()() () ()()()(), ,jZ iZ x =( 一方面,若 1, 则由（ , 对于所有的 , 有 (),0 , 有 . 另一方面, 若 , 则 1, 若不然存在 使得 1 . 选取 , 满足 (),0,且 , 同时(),0 , 则 () ( ) ()( )()(), =若 1 , 取 满足(),0 , 则有( ),0严格成立. 现在讨论点是退化的极值点即cZ k 的情形. 选择, 满足 且 :ix 能张成间. 类似于（ 对于每一个 ,jx ,它能被 , 线性表出 ,ax j J= (对于 , 定义同（ 类似上述讨论, 从（们有 () ( ) ( ) ( )( ), =将（入化简得 () ( ) ( )() ()()/, , =+(如果 1, 则意味着(),0 对于所有的 0 成立. 因此, 有如下引理. 引理 8:是极值点, 如果对于某些, 其中 J 满足 且 :ix 能张成间 1, . (成立, 则 . 格成立. 硕士学位论文 - 17 - 用 ,0 表示退化的极值点的阶数. 现在来构造一个关于方向的有限集, 使得只需对所有这个有限集中的 ( ),0 , 就能判断 , 这将比前面所述的引理都要方便. 对于每一个, 定义 ( ) |, 0为正交补. 我们取相互独立的集合 J , 其中 J 满足 () 1ix iJ k=. 显然 1, 并且这样的 J 至多有1kk kd + + + 个,至少有1+个, 当极值点是非退化时, 0d = 且这样的 J 有1=个. 对于 每个这样的 J , 取J = , 则 ( ),0 对于所有的 1ix iJ k=, 所以一维子空间. 我们称这样的 J 为 边缘集 ,缘方向 . 有上 讨论知, 如果一个极值点是非退化的, 则 0d = 且 c有 k 个边缘集, 推论 明此时 当且仅当 0f 在所有的边缘方向上成立. 对于一般的情况, 我们有如下引理. 引理 8:是极值点, 当且仅当对于所有的边缘集, 有 ( ),0,. (一方面, 若 , , 有 ( ),0,. 另一方面, , 根据前面定义可知, |J JJ = 能张成间, 由此 可被线性表示为 J =. 如果(),0到第11步; 10 ; 返回到第3步; 11 找 m: ; 取 ; 返回到第3步; 出 12 (),11,11,1, ,+= = =一类混合范数极小化问题 本章刚开始指出第一类混合范数极小化问 题可以转化为最小绝对偏差问题进行求解, 接下来我们将给出具体的转化过程. 由于转化要用到最小二乘问题（士学位论文 - 25 - 2= 的通解结构, 因此先给出（通解结构. 小二乘问题（通解 最小二乘问题（通解将从两个方面给出. 一方面,对M 进行奇异值分解 0,00 = = . 其中 ,M N 阶酉矩阵, ( )12( ), , ,.,rr = , 1,., 为 的奇异值. 则 2=2 =2 =2 . 记 ()( )111112 1 21112 12, , ,., , , ,., += = =, ()( )11111 1 21112 1 112 , , ,., , ,., , ,( 1, 2,., )s s s s s s s s s us j = = =， ,则 ()()11122222222111 11 1 1 11 1 000. . r r Ms + = = = + + +故 ()()2222111 11 1 1 11 12. . r r = + + + = . 显然其解为 1211 111 112, ,., , ,.,ii ii us += , 11 1,.,+为任意值. 从而最小二乘问题（通解为 = . （ 其中 如上所示. 另一方面,如文献42中所示利用矩阵的 M P 广义逆给出了其如下另一种通解 (),z + （ 通过上述分析, 得到如下关于2= 的通解结构定理. 两类混合范数极小化问题研究 - 26 - 定理 给定M , , 则2= 的通解结构为 ( )sE + 或 = . 其中1211 111 112, ,., , ,.,ii ii us += , 11 1,.,+为任意值. 为任意向量. ,M N 阶酉矩阵, 满足奇异值分解, ()r ,1,.,为 的奇异值 接下来基于定理 出第一类混合范数极小化问题转化为最小绝对偏差问题的过程及证明. 一类混合范数转化为最小绝对偏差问题 . 定理 一类混合范数极小化问题可以转化为最小绝对偏差问题, 即给定,M , 求 12= . = . 可转化为求 01). 其中 ,M N 阶酉矩阵满足奇异值分解, ( ),()12, ,.,v= 1,., 为 的奇异值, ()r . ()( )()12 11 1, ,., , ,., r v R c + += = , 101=. 证明 ：由定理 最小二乘问题2= 的解为 ()112 111= , ,., =+=. 其中 硕士学位论文 - 27 - 1211 111 112, ,., , ,.,ii ii us += , 11 1,.,+为任意值. 为任意向量. ,M N 阶酉矩阵, 满足奇异值分解, ()r , 1,., )111111111 1 12 2 11101.=+ +=+=定理得证. # 注 2= 的通解的另一表示为 (),z + 为任意向量. 因此 ( )111z += . 其中,y = = . 这么以来, ,便于程序的编写, 而定理 转化除了编程不便之外, 其中奇异值分解等会增加计算的工作量, 法及数值例子 . 上述讨论已经将第一类混合范数极小化问题转化为最小绝对偏差问题, 结合最小绝对偏差上面的理论和下面我们直接给出第一类混合范数极小化问题的算法 一类混合范数极小化问题的 定 ,M , 11,()s X E E R k = = . 两类混合范数极小化问题研究 - 28 - 初始化 1 120 ; 2 ()( )110; , , , , 0 = = ; 一个下降方向 3 ,1,1 : 0 , 1, ,2 N+ = = ; 4 对于 到 N , ()(),1, ;+5 如果 j N 到第 11步 ; 10 ;返回到第 3步 ; 11 找 m : ; 取 ;返回到第 3步 ; 出 12 ()(),111,1, ,i = = + 硕士学位论文 - 29 - 下面通过如下算例来说明将（化成最小绝对偏差问题（有效地, 第一步, 生成如下高斯随机随机矩阵 215 , 给定 () . 第二步, 序见附录A）, 程序迭代9次得出 值为 此时1= 第三步, 结果比较. 分别取8=I ( 1,2,.,8) ,其中 , 其余为 0 )1sE + . 并计算1 , 与第二步中的1 进行比较, 表 法 算第一类混合范数的结果比较 1 0 ( ( ( ( ( ( ( ( ( 其中标号0中的 为第一类混合范数极小化问题 第310行中的()11 = + （第 其余为0）. 两类混合范数极小化问题研究 - 30 - 由上表比较结果可以看出, 由第一类混合范数极小化问题 比其它满足2= 的()1sE + 的1l 可以说明将第一类混合范数极小化问题（化成最小绝对偏差问题（硕士学位论文 - 31 - 第 3 章 第二类混合范数极小化问题研究 本章将研究如下混合范数极小化问题, 即为给定 ,M , 求 2211=+), 0 . （ 本文称这类混合范数极小化问题为 第二类混合范数极小化问题 . 极小化问题（要求信号的噪声分布已知,极小化问题（求信号的稀疏程度已知, 文19则针对信号的稀疏度和噪声分布情况都未知的情形, 提出了（极小化问题. 文18 中采用了梯度投影法对（ 行了有效地求解. 极小化问题（一个二次约束线性规划问题（ 极小化问题（一个二次规划问题（ . 利用凸分析相关理论可以证明, 极小化问题（解要么是 0 = ,要么就是( 极小化问题 （的解, 也是( 取某些值时的解. 具体可以利用43,证明, 这里不详细证明. （同时对信号的稀疏度和噪声进行约 束, 它的研究工作具有很大的应用价值, 本文主要研究了它的转化及相应的算法设计. 二类混合范数极小化问题的转化 事实上如定理 示, 第二类混合范数极小化问题（以转化为标准的带边界约束二次规划问题来进行求解. 定理 二类混合范数极