School of Management, Qufu Normal University, Rizhao Shandong
*通讯作者。
Email: *1002218442@qq.com
Received: Jan. 23rd, 2015; accepted: Feb. 4th, 2015; published: Feb. 11th, 2015
Copyright © 2015 by authors and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
ABSTRACT
In the paper, we first transform the optimization problem of compressed sensing into a convex feasibility problem. Then, a projection method is presented to solve it.
Keywords:Convex Feasibility Problem, Compressed Sensing, Projection Method
求解压缩传感问题的一种投影算法
于丽超*,屈彪
曲阜师范大学管理学院,山东 日照
Email: *1002218442@qq.com
收稿日期:2015年1月23日;录用日期:2015年2月4日;发布日期:2015年2月11日
摘 要
本文在将压缩传感的最优化问题转化为凸可行问题的基础上,设计了一种投影算法来求解凸可行问题,进而来求解压缩传感问题。
关键词 :凸可行问题,压缩传感,投影算法
1. 引言
近年来,Donoho、Candes及Tao等人 [1] [2] 提出了一种新的信息获取指导理论——压缩传感(Com- pressive Sensing or Compressed Sensing,简称为CS)。该理论表明:如果原始信号具有稀疏先验性,通过选取适当的优化算法,在获取少量测量值的基础上,对原始信号进行恢复重建。区别于传统的奈奎斯特采样定理,这种新颖的信号处理方式可以认为是一种全局采样,它将采样与压缩同时进行,用极少的观测值拾取足够多的原始信号的信息,有效地减少采样的数据复杂度,同时也节约了信号采样所需花费的时间,在实际应用当中可以降低采集系统的成本,选择适当的重构算法还可以加快图像的重建速度,提升图像的重建质量 [3] 。
压缩传感理论的提出,为信号采样领域注入了新鲜血液,引起信号处理领域的研究热潮,具有广阔的应用前景。目前,压缩传感理论被应用于许多领域,例如:压缩成像、生物传感、医学成像、模数信息转换以及地球地理数据分析等 [4] 。
从信号重构的角度出发,利用具备某种分布特性的测量矩阵,对原始信号进行测量,在该测量矩阵的线性测量值为,其表达式为:
在上式中,测量值y也可以认为是原始信号x在H上的线性投影,我们需要求解一个逆问题,通过测量值y对x进行重构。理论证明 [2] ,在y与H满足一定条件的前提下,我们可以通过求解最优范数达到精确重构原始信号的目的:
其中,表示向量x的范数,即x中非零分量的个数。
但是,对于范数的最优化问题而言,其本质是NP问题,很难在多项式时间内求解,甚至对于解的可靠性都无法给出证明。所以,通常我们都将最优化问题转换成最优化问题来求解。即考虑如下问题:
(1)
其中,表示向量x的范数。
我们在本文中,我们通过求解如下问题来求解问题(1):
(2)
其中是可任意选择的。
受文献[5] 的启发,我们将问题(2)转化为一个凸可行问题,通过设计投影算法来求解该凸可行问题,从而得到问题(1)的最优解。
本文组织如下:在第二部分提出了问题的转化过程,第三部分提出了投影算法求解凸可行问题,并给出算法的收敛性分析。
2. 问题的转化形式
定义:
(3)
(4)
其中表示内积,是矩阵的第j列,表示y的第j个分量。
则问题(2)可等价地转化为如下凸可行问题:
(5)
注:由定义可知,均为超平面,从而为闭凸集,为闭凸集。
3. 算法及收敛性分析
设为非空闭凸集,对任意,定义:
,并称其为x到W上的投影。称为从到W上的投影算子。
当W是某些特殊的闭凸集时,求x在W上的投影是很好求的,能够用显式表达出来。如,当W是中的超平面 (其中为非零向量,)时,我们有如下结果:
引理3.1 [6] 令 (其中为非零向量,),则对任意的,到W上的投影为:
.关于投影算子,有如下性质:
引理3.2 [7] 令是非空闭凸集,则对,,有:
1);
2);
3);
4).
下面,我们给出我们的投影算法:
算法3.1:
任取对,
计算:,.
令:;.
计算:.
其中:和分别由(3)、(4)定义。
注:由引理3.1知,到上的投影是好求的。
我们分析算法3.1的收敛性:
引理3.3令是问题(2)的一个解,是由算法3.1产生的点列,则
证明:因为是问题(2)的一个解,所以也满足问题(5),即且,结合引理3.2,有:
从而可得:
定理3.1 若是由算法3.1产生的点列,则它收敛到问题(2)的一个解。
证明:令是问题(2)的一个解,则也满足问题(5)。因为,故:
由引理3.3得:
由此知是单调递减的,从而是收敛的,且,均是有界的。且由此可得:,从而有:
(6)
又因为和,由(6)可得,
(7)
假设是的一个聚点,则存在的一个子列收敛到,下证是问题(5)的一个解。
首先证明:。
事实上,由(7)得
.从而得,。则。
其次证明:.
因为,故
(8)
先证收敛。事实上,因为是有界的,所以也是有界的,故存在收敛子列。假设为的任意一个收敛子列且,又因为收敛,故收敛,从而有
(9)
由(8),有,由引理3.2得:
又由(9),得。综上可知,收敛且收敛到,由于为闭凸集,故有。
这样,为问题(5)的一个解,从而也是问题(2)的一个解。用代替上述证明中的,则得是收敛的。而收敛到0,故整个点列是收敛到0的,即收敛到。
基金项目
本文为国家自然科学基金(11271226)和山东省优秀中青年科学家科研奖励基金(BS2012SF027)资助项目。
参考文献 (References)
[1] Donoho, D.L. (2006) Compressed sensing. IEEE Transactions on Information Theory, 52, 1289-1306.
[2] Candes, E., Romberg, J. and Tao, T. (2006) Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52, 489-509.
[3] 杨凡 (2010) 压缩传感图像重建的研究. 硕士论文, 江西科技师范学院, 南昌.
[4] Gamper, U., Boesiger, P. and Kozerke, S. (2008) Compressed sensing in dynamic MRI. Magnetic Resonance in Medicine, 59, 365-373.
[5] Carmi, A., Censor, Y. and Gurfil, P. (2012) Convex feasibility modeling and projection methods for sparse signal recovery. Journal of Computational and Applied Mathematics, 236, 4318-4335.
[6] Boyd, S. and Vandenberghe, L. (2009) Convex optimization. Cambridge University Press, New York.
[7] Zarantonello, E.H. (1971) Projections on convex sets in Hilbert space and spectral theory. In: Zarantonello, E.H., Ed., Contributions to Nonlinear Functional Analysis, Academic Press, New York, 237-424.