Vol. No.(), Article ID:,0 pages

A Projection Algorithm for Compressive Sensing

Lichao Yu*, Biao Qu

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.

期刊菜单