Nesta 算法以及一些推广各位老师，各位同学，大家好。

今天我给大家讲下Nesta 这个算法。

这个讲稿我写的比较啰嗦，有大量的重复语言，这样做呢，是刻意为之，因为我想给大家留足思考缓冲时间，所以故意写的比较啰嗦。

压缩感知是一种全新的采样方式，当被采样信号很稀疏时，只需要少量的随机采样即可得到信号的全部信息或者近似全部信息。

但是，俗话说，上帝为了打开了一扇门的同时也会关上另一扇门，压缩感知存在的一个重要问题就是如何有效地从压缩后的测量值中恢复出原始信号。

关于压缩感知的理论和应用，文章很多，这里就不介绍了，我们直奔主题。

压缩感知的信号恢复，本质上就是求下面这个优化问题12min ..x s t b Ax ε-≤这个公式的含义，想必大家都比较清楚了，我就不再赘述。

需要说的一点是，实际上，一些二阶算法比如内点法，在求解上述问题时很准确，但是二阶算法计算复杂度很高，难以满足大规模问题。

所以一般来说，我们在设计求解上述问题的算法时，只考虑一阶算法，就是最多只求一阶导数。

目前比较好的一阶算法比较多，例如TWISA[1]，FISTA[2]，primal-dual[3]算法，增广拉格朗日法[4]，approximate message passing[5]算法，贪婪算法，同伦法，很多很多，大家可以在网上搜索文献看。

一般来说，这些算法速度是足够的，但是，一般不够精确，因为拉格朗日乘子λ一般无法精确确定。

还有一个比较现实的问题，就是这些算法（不是全部）很难处理大动态范围信号，什么叫大动态范围信号？其实很简单，就是有时候信号幅度是10，有时候又是0.0001，变化极大。

再有一个问题就是，现实中的信号一般都不是绝对稀疏的，即便通过正交变换，也都不是绝对稀疏，而是近似稀疏，就是少量元素幅值较大，其余的很接近0，但不是0，这也是一个现实的问题。

Nesta 这个算法呢，它的全名叫Nesterov ’s algorithm ，这里的Nesterov 就是大名鼎鼎的Yuri Nesterov ，这个家伙是优化界非常牛的人，他和Arkadi Nemirovski 一起把线性规划推广为锥规划。

Nesta 这个算法，本质上是Nesterov 的一些思想的综合，主要是他三篇论文的综合，第一篇是A method for unconstrained convex minimization problem with the rate of convergence O(1/k 2)，这个论文催生了非常著名的FISTA 算法；第二篇是Smooth minimization of non-smooth functions ，这个论文同样非常重要，是讲如何平滑一个不光滑的函数。

为什么重要呢？很简单，因为我们压缩感知里的l 1范数就是不光滑的凸函数，它在0点是不可导的，所以应用了光滑技术就可以变成光滑函数，就是处处可导函数，这样就很好处理了；第三篇论文是Gradient methods for minimizing composite objective function ，这个论文开发了一种优化方法，收敛速度很快，而且计算很简单。

Nesta 是这三篇论文的综合，后面我们会具体讲。

在上述Nesterov 的第三篇论文里，就是Gradient methods for minimizing composite objective function 这篇论文里，他开发了一种算法，用于求解以下问题()min px Q f x ∈这里呢，要求f (x )是一个处处可导的函数，注意，要求f (x )是可导的，不可导就不行。

p Q 是一个凸集。

此外，还有一个要求，就是f (x )的梯度是有界的，通俗来说，就是f (x )的梯度要满足下面这个不等式()()22f x f y L x y ∇-∇≤-对任意的x,y 都成立L 是个常数。

当满足这些条件以后，反复迭代下面的算法，就得到优化问题的解。

注意，这个算法我们叫它算法1，这个算法看着很复杂，迭代步骤很多，其实不然，这个算法是比较简单的。

因为注意观察，首先，k y 这一步，第一项是个凸函数，后面那一项是个线性函数，可行域是凸集，这可以用传统的拉格朗日乘子法就能解。

k z 呢，p(x)这个函数是我们自己选的，后面会说，p(x)一般也是个l 2范数，所以k z 的求解跟k y 其实是一样的，没区别的。

所以算法1其实是个看似复杂，实际简单的算法。

如果我们取()121k k α=+，()23k k τ=+，那么算法1的收敛速度就是()()()()241k Lp x f y f x k **-≤+，这个收敛速度跟FISTA 基本差不多，都是属于O(1/k 2)级别的收敛速度，已经逼近了一阶算法的理论极限。

注意，算法1只是一般形式，接下来的问题是如何用它来解压缩感知的恢复问题呢？那么很自然地，我们先看看这二者的联系和区别。

首先，压缩感知的恢复问题里可行域是2b Ax ε-≤，这是一个关于x 的凸集，很好验证，所以2b Ax ε-≤可以对应为算法1里的p Q 。

那么1x 是否可以直接套到f(x)呢，答案是不行，因为1x 在0点处是不可导的，它不是处处可导的函数，而算法1是要求f(x)是处处可导的函数，所以1x 不能直接套到f(x)。

这时候，很自然地，我们需要平滑1x ，给它加个东西，让它变成处处可导的函数，而且还不能影响最小化问题的解。

不能说我给1x 加了个东西，然后求解最小化问题，得到的解跟求解l1范数最小化问题的解不一样，那就不行了。

这个时候就要用到Nesterov 第二篇论文里的内容了，就是Smooth minimization of non-smooth functions 。

Nesterov 在这篇论文里提了一种平滑方法，它说如果你的f(x)可以写成如下形式，那就可以平滑，否则，就不一定了()max ,du Q f x u Wx ∈=W 是一个矩阵。

注意看上面这个式子，当一个人拿到这样一个公式，很自然地就会想，什么样的函数f(x)可以写成这样呢？看起来似乎没有哪种函数是这个样子的。

如果你很懂泛函分析的话，就会知道，这种写法，其实指的是范数。

比如l1范数，就可以写成11max ,u x u x ∞≤=这里W 就是I 。

再比如l2范数，也可以写成 221max ,u x u x ≤=这里面有啥规律呢？很简单1max ,n mu xu x ≤=这里m 和n 是一对共轭数，就是说111m n+=。

那为啥要多个W 呢，这是因为比如我们要处理analysis 模型，analysis 模型一般就是12min ..Wx s t b Ax ε-≤这时候11max ,uWx u Wx ∞≤=。

在Nesterov 的文章里，他说如果()max ,du Q f x u Wx ∈=，那么可以这样平滑()()max ,dd u Q f x u Wx p u μμ∈=- （1）这里()d p u 一般选为l2范数就可以，就是()221=2d p u u 。

注意了，我们接下来要用()f x μ代替()f x ，因为()f x μ是一个处处可导的函数，而且对()f x μ求最小化和对()f x 求最小化得到的结果非常非常接近。

Nesterov 给出了()f x μ的梯度为()()f x W u x μμ∇=*，这里()u x μ是公式（1）的最优值，就是公式（1）关于u 的最大值。

而()f x μ∇对应的Lipschitz常数为21L W μ=。

注意了，一般呢，我们要把μ取得很小，因为μ越小，()f x μ和()f x 就越接近。

既然我们得到了平滑后的函数，就可以套用算法1了，这个时候压缩感知的修复问题就变成了()2212min max ,2..xuf x u x us t b Ax μμε∞≤=--≤注意，此时，()()1,,i i i x x f x sign x otherwiseμμμ-⎧<⎪∇=⎨⎪⎩，1L μ=，这两个都很好验证。

这时候我们就可以舒舒服服的套用算法1了，我把算法1再粘一遍现在我们需要考虑的就是k y 和k z 这两步怎么解。

先看k y ，我们把这个问题先写出来()222arg min,2..k k k kx L y x x f x x x s t b Ax με=-+∇--≤这个问题，并不困难，因为目标函数是凸函数，可行域是凸集，所以可以用标准的拉格朗日乘子法来解。

首先我们构造拉格朗日函数就得到()()()22222,,22k k k L L x x x f x x x b Ax μλλε=-+∇-+-- 注意这里用2λ而不是λ是为了求导的时候方便。

构造出拉格朗日函数以后，我们假设(),k y ελ是拉格朗日问题的一对儿对偶解，则(),k y ελ一定满足KKT 条件，就是下面的几个公式ελ()()()()22220kk k k k k b Ay b Ay L y x A Ay b f x εεεμελλελ*-≤≥--=-+-+∇=第一个公式就是可行域，第二个称作拉格朗日乘子的非负性条件，第三个叫complementary 条件，第四个条件是说目标函数的梯度一定可以由约束条件的梯度合成。

KKT 条件就不细讲了，不明白的同学随便找本凸优化的书就可以找到这方面的内容。

根据KKT 条件中的第四项，只要经过简单的运算，我们很容易可以得到()1+kk k I A A y A b x f x L L L εεμλλ**⎛⎫=+-∇ ⎪⎝⎭很明显，要计算出k y ，我们需要计算+I A A L ελ*⎛⎫⎪⎝⎭的逆，此时需要用一个工具，就是著名的Sherman-Morrison-Woodbury 求逆公式，这个求逆公式大家可以在网上查到，这里就不细说了，总之，最后解得的()1k k k y I A A A b x f x L LL εεμελλλ**⎛⎫⎛⎫=-+-∇ ⎪ ⎪+⎝⎭⎝⎭这里要注意了，到目前为止，ελ是未知的。

下面我们要求ελ。

要求ελ，就要用到KKT 条件中的第三个条件，就是complementary 条件()2220kb Ay ελε--=，这个条件其实是说，当222=kb Ay ε- 时，ελ是大于0的，而当222kb Ay ε-≠时，ελ是等于0的。

所以，我们令222=kb Ay ε-，再把k y 代进去，最终得到 ()()()-11=max 0k k L b A x L f x L εμλε---∇-，需要说明的一点是，上面这个公式当=AA I *时才成立，否则不成立。

=AA I *实际上就是说我们的测量矩阵A 是部分傅里叶矩阵，或者部分DCT 矩阵这种。