GESPAR:有效的稀疏信号相位复原

GESPAR：有效的稀疏信号相位复原

摘要

我们认为相位复原问题就是将一个信号从它的傅里叶变换或其他线性变换中恢复。由于傅里叶变换相位信息的丢失，这个问题是不适定的。因此，这个信号的先验信息在其信号恢复过程中是必不可少的。在这篇文章里，我们认为信号是稀疏的，也就是，它将少量的非零元素组成为一个合适的主要成分。我们提出了一个快速局部搜索方法，来测量一个稀疏信号以其傅里叶变换（或者其他的线性变换）形式下的大小，我们叫它GESPAR。我们的算法不需要矩阵变换，不像以前的方法，因此可广泛适合大规模问题，例如图像。仿真结果表明GESPAR是比现有的具有很多设置的方法快速而更准确的。

关键词——非凸优化，相位复原，稀疏信号处理

1. 概述

从傅里叶变换中恢复一个信号也叫相位恢复，在类似于光学成像，结晶学等更多的应用中具有极大的兴趣。因为傅里叶变换信息的丢失，在一维中的问题就是普遍不适定的。克服这种不适定行的通常方法是利用信号之前的信息。很多方法是基于利用以前信息发展的，这些信息可能是信号的支持域（信号的非零域上），非负性，或者是信号的大小。

一种流行的经典算法是基于不同约束下的交替预测的使用。为了增加正确恢复的可能性，这些方法需要非常精确地先验信息，例如，精确地或者几乎精确的支持域信息的设定。自从这些预测都一般基于非凸设定，就不能保证能收敛到一个精确复原。一个现代的方法是使用矩阵变换，这样的信号允许将相位复原问题可认为一个半定义的编程问题。

这样的算法不需要信号的先验信息，但是使用很多的信号测量值（例如在光学设置里使用不同的照明设定值）。

为了在不需要多种测量值得情况下的有力的复原，我们研究了一种使用信号的稀疏性的方法。现有的方法是致力于从他们的傅里叶形式中恢复出两种主要的不同的稀疏信号：基于的SDP技术和使用交换预测的算法(fienup型方法)。稀疏信号的相位复原可以认为是基于sdp技术下更加常规的二次压缩传感器（QCS）问题的特殊例子。特别的，QCS处理稀疏矢量的复原是根据方程式，i=1，...，N，并二次测量得到的，其中x是未知的待复原的稀疏矢量，是测量值，Ai是已知的矩阵。在（离散）相位复原，有，其中是是离散傅里叶变换矩阵的第i行。QCS是我们以前遇到过的，例如，当一个稀疏的对象使用部分空间不相关的照明度时的成像时。

一个一般的解决QCS方法在[8]中提出，它是在矩阵变换的基础上形成的。更特殊的是，这个二次方程式定义了一个矩阵变量，限制了其转换成更高维数.问题就变成了一个包括变换后的矩阵列数的最小化SDP，这个变换后的矩阵服从复原的限制条件和X的列稀疏型条件。之后，一种基于SDP序列的可以恢复稀疏解的迭代阈值算法被提出来。类似于SDP类型的方法最近被使用于相位恢复的问题中。然而，由于矩阵变换过程中产生的维数的增加，这个SDP方法不适合大规模问题。

这篇文章中我们提出相位恢复的有效的方法也能有很好的恢复性能。我们的方法是基于快速2-选则的本地搜索方法（查[13]能查到一个优秀的这类技术的介绍），应用于这个问题公式的稀疏性的非线性优化。我们提出了一个产生算法GESPAR：GrEedy稀疏相位复原。稀疏性约束的非线性优化问题在[14]中考虑过，这个论文导出的方法是有目的的——即使许多方面不同——是基于在[14]中本地搜索类技术。实质上，GESPAR是一个本地搜索方法，待求信号的支持域是根据第三部分详述的选择法则反复更新的。若给出使用衰减高斯牛顿算法求出的瞬时支持域，则能求出目标函数的局部最小值。原理1揭示了在合适条件下迭代次数到达一个目标定点的收敛性。

我们通过数值仿真证明了GESPAR是有效而且比现有技术更加准确的方法。这种算法的其他不同方面已经通过仿真测试了，例如噪声鲁棒性，大规模扩展。在仿真表现中我们发现测量值的数量需要根据傅里叶大小的可靠复原来定，傅里叶大小的数量就像，其中s是稀疏水平。

GESPAR对于一般二次测量中的稀疏矢量的恢复是可适用的，并且这并不能限制傅里叶大小的测量。尽管如此，当测量值包含在傅里叶域中时，这种算法可以通过利用快速傅里叶变换能有效的实施，就像在第四部分我们讨论的那样。

这篇论文剩余的部分是如下组织的。我们在第二部分中用公式表示这个问题。在第三部分中详尽的叙述了我们提出的算法，并且建立了局部迭代次数的收敛性。傅里叶基础问题细节的实施将在第四部分提供。第五部分里叙述了大量的数值实验说明了GESPAR的实际性能。

shou2.问题规划

A.稀疏相位复原

我们给出出一个矢量，它相当于矢量x（）的N点离散傅里叶变换的幅度的平方，即

X被构造成（N-n) 0填充的矢量 ，其中元素xi，i=1,2,3......,n。被表示为，元素为 的离散傅里叶变换，我们可以表示y为

y=|Fx|2 ，其中| .|2表示为元素点乘的绝对值的平方。矢量 被认为是s-sparse，它包含s中最多的非零元素。我们的目标是恢复或x，和给出y的值，稀疏程度s。

关于这个问题的数学构想，我们认为误差平方的最小值属于稀疏约束：

其中Fi是离散傅里叶矩阵F的第i行，||.||0 代表0“标准”，它是非零元素的个数。未知矢量x的微弱的衰减引起傅里叶相位信息的丢失，循环移动，总体的相位，信号的“反射”。

支撑信息：为了帮助解决相位恢复问题，我们可以依靠自相关序列（第一个n组成x）可以被y确定，如果N>=2n-1。特别的，使

表示相关序列的长为2n-1。如果我们选择N>=2n-1，则{gm}可以通过y的DFT反变换获得。

确定gm要求采样过密，或x的0填充，这个额外的信息证明了恢复表现，它在模拟部分证明，它并不需要用到GESPAR。然而当这个信息是有效的，GESPAR通过以下方法拓展了它。第一，我们假设没有支撑集被取消在{gm}中。即，如果某一x i≠0，x j≠0，g|i-j|≠0。

当x的值是随机的，可能性1是真的。这可用在GESPAR，用于在x的支撑集中获得最初信息，我们可获得两个集合J1和J2。

J1表示为指数集预先在支撑集中，为了得到J1，由于自由度的存在关系到x的平移不变性，指数1假定在支撑集中，因此平移这个自由度。因此，这个指数符合在相关序列的最后非零元素是在支撑集中，

因此，J1={1，i max}。

第二，我们定义J2为指数集，作为候补在支撑集中，这个指数不是提前的在非支撑集（支撑集的补集）。特别的，J2包含所有指数的集k∈{1,2,3...,n}其中g k-1≠0。显然的，我们认为x k=0当k>n,则J2包含于{1,2,3...,n}。

举个例子，信号。它的一致的11点自相关函数gm为。因此J1={1,6}。其次，通过检测gm的非零元素，通过我们支撑-取消的推论，我推断没有两个非零元素xi和x j 使得|i-j|=1,4.

因此，x的第一个元素为非零，移动的衰退，可以得到x2=x5=0。通过这种方式我们得到J2={1,3,4,6}。定义，问题（2)和支撑信息可以写为

这会是个被研究的构想。

既然确定x的准确的支撑集也不能保证上述的不重要的失真的唯一性。举个例子矢量u=（1,0，-2,0，-2）和。这两个矢量的稀疏度s=3，它们有相同的自相关函数gm=（-2,0,2,0,9,0,2,0，-2）。这个不确定因此不能通过单独的使用稀疏性（即使是精确支持信息）和自相关（或傅里叶级数）而被解决。

最终，当测量有噪声，自相关信息不能准确的用于估计，在自相关序列中即使一个很小的值（噪声等级）不能认为是0。由于这个原因，自相关导出的支持信息不能被用在GESPAR当在噪声环境中。形式上的当设置J1={1}和J2={1,2,3......n}忽略这个信息是相等的。

B: 稀疏相位恢复：一般测量

尽管上述问题公式化假设傅里叶测量和x向量的稀疏度, 下面我们证明了我们的方法适用于任意的二次测量。这包含这种情况，在这种情况中在一个基底上是稀疏的，而在单位基底上不是稀疏的。事实上，在一般情况下，（4）中给出的公式是保持不变的，唯一改变的是矩阵Ai的定义。

考虑相位恢复问题相对于任意线性测量，所以

， （5）

对一组测量向量.相应的相位恢复问题可以在（4）写成。同样的，假设，，在这个基底下市稀疏的，而且也是稀疏向量。在这种情况下，。因此，我们的公式可同时容纳任意稀疏基地和一般二次

测量。

在下一节中，我们提出GESPAR，为了求解（4）式提出的一种基于算法的迭代局部搜索方法。我们注意到尽管在参数相位恢复情况下,有特殊的性质（例如，在秩为2的时候是半正定的，），我们在GESPAR中不使用这些性质。因此，我们唯一假设对于任意都是对称的，用这种方法来处理（4）式的一般情况。在傅里叶变换的情况下，该算法可以更有效的实现，我们将在第IV部分讨论。

Ⅲ GREEDY SPARSE PHASE RETRIEVAL(GESPAR) 贪婪的稀疏相位恢复算法

A 阻尼高斯—牛顿法

在描述算法之前，我们首先介绍一个阻尼高斯—牛顿法的变体【15】【16】，事实上，那是我们算法的核心步骤。阻尼高斯-牛顿法是用来解决在给定支撑集上目标函数的最小化问题：

（6）

是由单位矩阵对应的指数集的列组成的向量。用这个符号，（6）可以明确的写为

（7）

(7)式的最小化是一个非线性最小二乘问题。解决这个问题自然是通过DGN（阻尼高斯牛顿法）。这个算法首先引入一个任意的向量，在我们仿真时 ，我们选择零均值和单位方差的向量作为白随机高斯向量。在每次迭代时，附近域内所有的结果都是线性的，而且与先前的预测结果相差很小。也就是说我们可以从（7）式中求出：

（8）

其中，。在每一次迭代时，我们用附近的线性近似值代替：

（9）

然后我们选择为问题的解。

（10）

问题（10）可以写为一个线性最小二乘问题。

（11）

的第i行为，的第i个元素为这个解与相等。然后我们定义一个方向向量，这个方向向量用…一个适当的步长…来更新这个解，步长的选取应保证其收敛于的驻点。步长的选取通过一个简单的回溯法。算法1详细的描述了DGN方法。在我们运算时停止参数选为和。

下面的定理建立了目标函数收敛速度的规范梯度为0，从而证明了该序列的极限点是驻点。

定理1：如果是DGN方法生成的序列，假设，而且存在，对于所有的，都满足：

当时有，存在一个常数使下式成立：

（12）

此外，该序列的每一个极值点都是函数g的驻点。

证明：见附录A。

需要注意的是为满列秩，事实上，的最小特征值一致有下届。我们大多数的运行都是有效的，然而，我们在进行数值实验时也遇到了一些情况，在这些情况下假设是无效的。在这些情况下，我们选择一个相应最小二乘问题的最优解。我们质注意到这些情况对结果的影响可以忽略不计。

算法1 用DNG法解（7）式

输入：

-------对称矩阵

--------指数集

-----------停止标准参数

----------最大迭代次数

输出： -----（7）式的最优解

初始化：设是随机向量。

一般步骤考虑到迭代，下一次的迭代又下面的步骤确定：

1， 高斯-牛顿方向：让为线性最小二乘问题（11）的解，

的第行是，的第个元素为。则高斯-牛顿方向为：

2， 通过回溯法选择步长：设，选择一个步长，（7）式中满足：，是最小非负整数。

3， 更新：设。

4， 停止规则：当时停止运算。

B， 2-opt局部搜索法（The 2-opt Locial Search Method）

GESPAR方法包括在一个初始随机支撑集内反复调用局部搜索法。在这部分，我们将要描述局部搜索过程。首先，支撑集选择一组满足的随机指数集。然后，在每次迭代执行支撑指数集和非支撑指数集之间的交换，最终通过DGN的方法提高了目标函数。由于在迭代时只有两个元素交换了（一个在支撑集，一个在非支撑集），所以这就是所谓的“双选择”方法（见【13】）。指数之间的互换总是在当前迭代取最小绝对值所对应的指数和非支撑集中取最大绝对值所对应的指数之间互换。这个过程持续进行，只要当没有提高的时候目标函数减少和停止，这一过程也就停止。这一算法的详细介绍在算法2中给出。

算法 2 （2-opt）

输入：

------------对称矩阵

输出： ---------公式（4）的一个建议解

---------------需要交换的总次数

1） 初始化：

a） 设

b） 生成一个随机指数集，满足条件，

c） 调用DGN方法，参数为，得到一个输出。设

2）一般步骤：（）

a）为取最小绝对值是对应的指数。为取最大绝对值时对应的指数。

b）设，交换指数和

。

调用输入为的DGN算法，得到一个输出。设，自加。

如果，则设，，自加，从2.a开始重新执行。

c）如果没有更好的目标函数值用来交换，则停止运行，输出为和。

C GESPAR算法

2-opt法在解决局部极值点时有困难。因此，我们把最终算法成为GESPAR，它是2-opt法的一个新版本。2-opt法重复调用不同的随机初始支撑集直到目标函数值小于某一阀值（成果）或者到达最大允许的交换次数（失败）。算法3详细描述了这种方法，但是有一点没有提到，那就是在我们执行的时候用到了目标函数的随机权重，随机权重就是根据不同测量量取不同的权重。也就是说，我们选用的目标函数为，是等可能的。在每次调用DGN过程时随机产生权重。我们发现这个修正算法降低了2-opt算法在非极值点受阻的可能。

算法 3 GESPAR

输入：

--------对称矩阵

--------阀值

-----------最大允许交换次数

输出： ---------（4）式的优化（次优化）解

初始化：设

重复步骤：

调用输入参数为的2-opt算法，得到输出和。设，自加。当或是停止调用。

输出：，其中。

Ⅳ 傅里叶实现过程

原则上，GESPAR算法可以求解任何系统的二次方程的稀疏解，二次方程的形式如下：

（13）

然而，当矩阵可以转换为更有效的实现形式时，GESPAR就变为一个非常简单的形式。

例如，考虑为傅里叶测量量的情况，在这种情况下，矩阵的产生与存储已经在第Ⅱ部分定义，在实现的时候可以用快速傅里叶变换（FFT）可以避免。特别的，为了计算目标函数的权重，我们注意

（14）

其中，是的第个离散傅里叶变换，可以通过快速傅里叶变换计算。明显的，DGN算法（算法1）中用到的也可以有效的计算，这是因为仅仅包含傅里叶矩阵F中的一小部分。

快速傅里叶变换也可以用来计算梯度，在2-opt第二步使用：

（15）

因此，在算法的任何步骤中准确的计算矩阵的集合是很有必要的。

在二维傅里叶相位恢复问题上上述事实更加重要，并且随着相关向量的大小重要性变得更大。因为GESPAR算法超过其他算法的优势是计算成本较低，GESPAR可以用来解决二维傅里叶相位恢复的稀疏解问题，也可以用来解决图像相位恢复问题。在算法实施的时候唯一要调整的是用FFT2而不是存储大型矩阵。

图1，是一个稀疏的像素的图像恢复的例子，该图像在一个包含225个点的网格上在15个随机的位置上赋予随机的值的点，用GESPAR算法，从38.025的二维傅里叶级测量。本例中使用的字典包含位于笛卡尔网格上非重叠的225圆圈，每一个圆圈的像素直径都是13。解这个过程用了80秒。解决相同的问题，用稀疏Fienup算法没有成功的恢复图像，用SDP方法是不实际的因为矩阵的尺寸太大。

关于二维情况下算法性能的进一步研究在第Ⅴ部分介绍。一维和二维的傅里叶情况下的GESPAR事例可以再网上找到。

Fig.1 2D傅里叶相恢复示例。（a）真实195*195稀疏环图像（s=15 环）。（b）测量的傅里叶级数（38025次测量，对数尺度）。（c）真实的恢复稀疏矢量，相当于每225个网格点上的环幅度。

V. 数值仿真

为了演示GESPAR的特性，我们进行了几组数值仿真。将所用算法与其他现有方法相比较，并在信号恢复精度、计算效率、抗噪能力等方面进行了评估。

A.信号恢复精度

在这个部分，我们将GESPAR的成功恢复速率作为信号中的非零元素的数值的函数，进行检测。并且，测试方法的运行时间之间也进行了对比。

我们选取x作为一个长度为n的随机矢量。该矢量包含了在s随机选出的元素中，在范围内均匀分布的值。信号的N点DFT被计算出来，其大小的平方付给测量矢量y。2n-1点相关性也进行了计算。为了恢复未知矢量x，GESPAR算法中采用和ITER=6400。为了对比，我们还测试了另外两种算法：基于SDP的算法和有稀疏度约束的迭代Fienup算法。在我们的仿真中，n=64,N=128。Sparse-Fienup算法使用了100个随机初始点，从中选择与测量最匹配的作为结果。即，Sparse-Fienup算法下，100次运行里使得最小消耗的x被选为s稀疏输出。

Fig.2 恢复概率与稀疏度（s）

信号恢复的数值仿真结果如Fig.2所示，在不同的稀疏度下，成功恢复的概率标注于图中。成功概率的定义是100次仿真中正确恢复的信号x的比例。在每次仿真中，支持和信号值都是随机选择的。三种算法（GESPAR，SDP，Sparse-Fienup）进行比较。结果清晰地显示，GESPAR在成功恢复概率方面有更优越的表现-超过90%的成功恢复，上至s=15,在另外两种方法中，分别为s=8和s=7。

TABLE I 运行时间比较

n=64与N=128时，三种算法的平均运行时间对比如Table I所示。平均时间建立在所有成功的恢复上。所用计算机配有i5CPU和4GB的内存。如表中所示，基于SDP的算法明显慢于另外两种方法。Fienup迭代比GESPAR稍微慢一点，也导致了更低的成功率。在这些仿真中，GESPAR在速度和精度上都优于其对手。

B.精确稀疏性知识的灵敏度

由于当仅仅给出一个s的上限值的时候，信号稀疏性s的精确值无法知道。为此，我们将GESPAR运行了两次：一次用完全已知的s值进行实现，一次仅仅用一个s的上限值进行实现。这个上限值采用25.其他仿真设置和V-A部分的相同。

Fig.3 未知精确稀疏度水平s对恢复概率的影响

C.允许转换的数值的效率

GESPAR算法的一个终止标准是转换的总个数超过了一个预定义的参数（算法3中的输入参数ITER）。自然地，提高索引转换的允许数就能提高找到正确解的概率，而其代价是增加了运算时间。因此，当前仿真的目的——对该效应进行量化就非常重要。

Fig.4 转换（ITER）个数对恢复概率的影响

我们在与V-A部分相同的参数下运行GESPAR，每次仿真采用一个不同的参数ITER值，范围在[100,25600]。Fig.4显示了其结果。正如预期，增加可能转换的个数能提高恢复的概率。注意，在6400以上提高ITER的值，对恢复结果没有改善（由于不成功的恢复），提高转换的个数，甚至ITER=25600也没有帮助。这意味着，对于这些仿真值，使用一个值大于6400的ITER只会增加运算时间，并不能改善结果。

D.过度取样效应与支持信息

此处，我们测试了过度取样和自纠错导出支持信息的效果。GESPAR是在长度为n=64的随机矢量x上运行的，并采用不定量的白噪声傅里叶级数量度，这些量度来自于N=64，128，256时的N点关于x的DFT。在这些情况下，支持信息没有被用到，比如J1={1}以及J2={1,2，..，n}。另外，为了研究支持信息的效果，我们在n=64,N=128的条件下运行GESPAR（例如在因素2时过度取样），然后使用源于自纠正序列的支持信息。这些结果，如Fig.5所示，清晰地显示出，过度取样和支持信息都能提高性能。

Fig.5 过度取样和来自自纠正序列的支持信息的影响

E.抗噪能力

现在，我们将GESPAR作为SNR的函数进行评估，并将之与稀疏Fienup比较。基于SDP的方法（如【9】中所介绍）不是被设计于解决噪声的目的，因此我们此处不采用。【10】的SDP方法考虑了随机量度，而且不产生能与直接傅里叶级数相比的结果。

正如在V-A部分，我们在包含了均匀分布的值的元素中随机选取s，选取长度为n的矢量x，评估其N点傅里叶级数的平方。在不同的SNR值下，将高斯白噪声v加到测量中，定义。为了恢复未知矢量x，GESPAR算法采用了，ITER=10000，同时对稀疏Fienup算法进行了同样操作，以作对比。在我们的仿真中，n=64，N=128。稀疏Fienup算法在不高于1000次迭代下运行，且有100个随机初始点。

注意到，即使使用了一点点的噪声，来自自纠正零点的支持信息将不再可用。这是因为，有噪声存在时，测量的（或计算的）自纠正中将不存在真正的零点。然而，这或许会导致真正的自纠正函数的小值（非零）归零。所以，在有噪声的情况下，GESPAR中我们不用来自于自纠正函数的支持信息，即J2={1,2，...，n}。

Fig.6 标准化的MSE与稀疏度水平。在若干个SNR值下的性能，GESPAR实线，稀疏Fienup虚线

作为对于不同的SNR值的稀疏函数，Fig.6显示了标准化平方重构错误（NMSE——其定义为），每个点代表一个超过100个不同的随机实现的平均。在不同SNR值下的特性示于图中，GESPAR是实线，稀疏Fienup是虚线。GESPAR的性能随着SNR提高而自然提升，并且在抗噪声方面明显优越于稀疏Fienup。

F：扩展性

GESPAR比基于SDP方法的主要优点在于它能有效地解决大问题。接下来我们分析他在不同大小向量下的表现。

我们模拟对n[64,2048]取不同值的GESPAR。都令N=2n。其它仿真参数和V_A部分一样。图7显示的是对应不同矢量长度恢复性能和稀疏度s的关系。能成功恢复的条件下，最大稀疏度s的值正比于与矢量n的长度。大概比例为。这也符合从【9】中观测到的比例。从N=1024的测量值中（n=512，s=35），并且允许ＩＴＥＲ＝６４００的替代下，一个信号的平均重建时间为３３.５秒。作为对比，图８是在相同条件下sparse-Fienup算法的扩展性。画基于ＳＤＰ方法下相似的稀疏度的图是不大可能的，因为计算成本高（在我们模拟条件的限制下，这种方法的应用范围是ｎ～４００）.

Ｇ．计算时间

ＧＥＳＰＡＲ最耗时的部分是算法中ＤＧＮ部分的矩阵求逆的过程。因此，计算时间的长度近似的线性与ｔｈｅ　ｎｕｍｅｂｅｒ　ｏｆ　ｓｗａｐｓ，每一次交换对应一次ＤＧＮ的迭代。图９近似的表示了这种线性关系。图中每一个点代表用GESPRA执行ITER迭代的平均时间，在N=128，n=64，s=10，的情况下平均值超过50的随机输入信号。决定计算时间的一个主要因素是求解时指数掉期的次数。掉期的平均数是s和n的函数，有图10显示。除了成功恢复的区域（图7中的白色部分），使用掉期的最大值（6400）产生一个正确的解。

图7.一维—扩展性---GESPAR恢复性作为稀释度s信号的函数，对应不同的矢量长度（n[64,2048]），和过采样，例如N=2n。白色区域对应高恢复概率。

图8. 稀疏Fienup可伸缩性--- 恢复率作为稀释度s信号的函数，对应不同的矢量长度（n[64,2048]），和过采样，例如N=2n。白色区域对应高恢复概率。

图9.时间和掉期数（ITER）

图10.掉期数作为s和n的函数，图中彩条以比例，例如10掉期

H．二维傅里叶相位恢复

这部分我们把GESPAR用到2维傅里叶相位恢复问题中，展示其解决大规模问题的高效能力。我们随机生成s-sparse的2维信号大小为X，s和n的取值范围为s[2： 82]，n[256：6400]。

采用GESPAR并且没有过取样的情况下，每一个信号都从它的2维 DFT无噪量级中恢复过来。和1维噪声模拟一样，这里没有使用自相关衍生支持信息。ITER的的参数被取为6400.图11显示的是恢复度和不同矢量大小的稀释度s的关系。类似1维的情况，可以成功恢复的最大稀释度随着n增长。作为比较，图12显示的是同样情况下，每个信号取200个初始点（能加这个参数不会显著影响结果），2维的sparse-Fienup算法可扩展性的仿真结果。结果显示GESPAR在2维情况下同样比sparse-Fienup方法要好。和一维的类似，这里这里并没有拿基于SDP的方法作比较。因为在2为情况下，由于内存的现在基于ＳＤＰ的方法实现很困难。ＧＥＳＰＡＲ和ｓｐａｒｅ－Ｆｉｅｎｕｐ的方法对比在图１３中。对比显示仿真中成功恢复所花的平均时间是矢量ｎ的函数。可以看出，ｓｐａｒｓｅ－Ｆｉｅｎｕｐ更快，然而对比图１１和图１２,可得ＧＥＳＰＡＲ对于较大能的ｓ也可恢复信号。例如，当ｎ＝６４００时，ＧＥＳＰＡＲ当ｓ＝５７时恢复概率依然很高，而ｓｐａｒｓｅ－Ｆｉｅｎｕｐ只能到ｓ＝４２.

图１１ＧＥＳＰＡＲ　２维－扩展性―――恢复概率作为信号稀释度不同图像尺寸的函数（ｎ＝２５６,１０２４,２３０４,４０９６,６４００）

图１２ｓｐａｒｓｅ－Ｆｉｅｎｕｐ２维－扩展性―――恢复概率作为信号稀释度不同图像尺寸的函数（ｎ＝２５６,１０２４,２３０４,４０９６,６４００）

图１３执行时间比较―――ＧＥＳＰＡＲ和Ｓｐａｒｓｅ－Ｆｉｅｎｕｐ成功恢复的平均计算时间，ｎ的函数

第六部分　结论

我们提出并论证ＧＥＳＰＡＲ是一种从傅里叶幅度恢复稀释向量的快速算法，更一般地说，是从测量值的二次方程式中恢复。我们通过仿真得到ＧＥＳＰＡＲ在复杂性和成功概率上要优于此问题的替代方法。这种算法不需要矩阵提升，因此更适合大规模问题例如２维图像。仿真已证明ＧＥＳＰＡＲ对噪声和其他不确定因素的稳健性。同时也证明它在一维和二位相位恢复的成功。

附录

本文来源：https://www.2haoxitong.net/k/doc/eab082df284ac850ad0242f0.html