在 ADMM算法简介 和 最大化速率的智能反射面波束成形（下）： ADMM 我们对ADMM算法进行了简单的介绍，前者主要侧重于原理，而后者则以IRS波束成形设计的实例展示了ADMM算法的实际应用。 这篇博客基于Millimeter-Wave Beamformed Full-Dimensional MIMO Channel Estimation Based on Atomic Norm Minimization 这一原子范数信道估计经典论文，介绍ADMM算法在应对SDP问题时的应用，以降低求解复杂度。不过，考虑到形式的简单性，我们选取了Super-Resolution Channel Estimation for Arbitrary Arrays in Hybrid Millimeter-Wave Massive MIMO Systems Yue中的例子，基于其更简单的形式，来更好地提升可读性。
对于稀疏信道估计，通过之前介绍过的原子范数技术 压缩感知的尽头: 原子范数最小化， 我们可以将信道估计问题转化为如下SDP问题：
arg min T ( u v ) tr ( T ( u v ) ) + τ 2 ∥ R ^ y − Φ T ( u v ) Φ H ∥ F 2 s.t. T ( u v ) ⪰ 0 \begin{gathered} \arg \min _{\mathrm{T}\left(\boldsymbol{u}_{v}\right)} \operatorname{tr}\left(\mathrm{T}\left(\boldsymbol{u}_{v}\right)\right)+\frac{\tau}{2}\left\|\hat{\boldsymbol{R}}_{y}-\boldsymbol{\Phi T}\left(\boldsymbol{u}_{v}\right) \Phi^{H}\right\|_{F}^{2} \\ \text { s.t. } \quad \mathrm{T}\left(\boldsymbol{u}_{v}\right) \succeq 0 \end{gathered} argT(uv)mintr(T(uv))+2τ∥∥∥R^y−ΦT(uv)ΦH∥∥∥F2 s.t. T(uv)⪰0
其中 T ( u v ) \mathrm{T}\left(\boldsymbol{u}_{v}\right) T(uv)代表以 u v \boldsymbol{u}_{v} uv作为第一行得到的Toeplitz矩阵，除此外的全部矩阵均为已知变量。 观察该问题可以发现， 其主要的难点在于 T ( u v ) ⪰ 0 \quad \mathrm{T}\left(\boldsymbol{u}_{v}\right) \succeq 0 T(uv)⪰0 这个正定条件不易处理，尽管这是一个凸约束，问题也是个标准的SDP问题可以直接通过CVX求解，但复杂度为矩阵维度的 3.5 3.5 3.5次方量级。 因此，我们使用ADMM算法以求复杂度的降低。 其核心思想在于，既然 T ( u v ) ⪰ 0 \quad \mathrm{T}\left(\boldsymbol{u}_{v}\right) \succeq 0 T(uv)⪰0 这个约束不易处理，那我就通过引入一个新的人工变量，再通过ADMM算法的迭代求解，使得该约束只需要在迭代过程中的其中一步中被考虑，而在其他步骤中都是简单的无约束更新。 这一思想与最大化速率的智能反射面波束成形（下）： ADMM 一文中对恒模约束的应对异曲同工。从这个例子也想告诉大家的一点是：
对于约束优化问题，如果约束不易应对的情况下，可以通过引入人工变量， 然后利用ADMM算法，对原始变量和人工变量进行迭代求解， 从而使得只需要在人工变量的更新中考虑这一约束，而原始变量的更新变成了无约束问题。
回到例子之中， 原问题可以引入一个看似多余的人工变量 U U U，改写为如下形式： R ^ v = arg min T ( u v ) tr ( T ( u v ) ) + τ 2 ∥ R ^ y − Φ T ( u v ) Φ H ∥ F 2 s.t. U = T ( u v ) , U ⪰ 0 , \begin{aligned} &\hat{\boldsymbol{R}}_{v}=\arg \min _{\mathrm{T}\left(\boldsymbol{u}_{v}\right)} \operatorname{tr}\left(\mathrm{T}\left(\boldsymbol{u}_{v}\right)\right)+\frac{\tau}{2}\left\|\hat{\boldsymbol{R}}_{y}-\boldsymbol{\Phi T}\left(\boldsymbol{u}_{v}\right) \Phi^{H}\right\|_{F}^{2}\\ &\text { s.t. } U=\mathrm{T}\left(\boldsymbol{u}_{v}\right), \boldsymbol{U} \succeq 0 \text {, } \end{aligned} R^v=argT(uv)mintr(T(uv))+2τ∥∥∥R^y−ΦT(uv)ΦH∥∥∥F2 s.t. U=T(uv),U⪰0, 我们可以发现，其核心在于，原始变量 T ( u v ) \boldsymbol{ T}\left(\boldsymbol{u}_{v}\right) T(uv)已经没有了约束，约束被转到了人工变量 U U U之上。 这一步虽然看上去很尬，但要知道后面我们的迭代求解中就可以让原始变量的优化变成了无约束问题。 接下来，我们可以写出其对应的增广拉格朗日函数如下：
L ( u v , U , Λ ) = tr ( T ( u v ) ) + τ 2 ∥ R ^ y − Φ T ( u v ) Φ H ∥ F 2 + ⟨ Λ , U − T ( u v ) ⟩ + ρ 2 ∥ U − T ( u v ) ∥ F 2 \begin{aligned} \mathcal{L}\left(\boldsymbol{u}_{v}, \boldsymbol{U}, \boldsymbol{\Lambda}\right) = \operatorname{tr}\left(\mathrm{T}\left(\boldsymbol{u}_{v}\right)\right)+\frac{\tau}{2}\left\|\hat{\boldsymbol{R}}_{y}-\boldsymbol{\Phi} \mathrm{T}\left(\boldsymbol{u}_{v}\right) \boldsymbol{\Phi}^{H}\right\|_{F}^{2} +\left\langle\boldsymbol{\Lambda}, \boldsymbol{U}-\mathrm{T}\left(\boldsymbol{u}_{v}\right)\right\rangle+\frac{\rho}{2}\left\|\boldsymbol{U}-\mathrm{T}\left(\boldsymbol{u}_{v}\right)\right\|_{F}^{2} \end{aligned} L(uv,U,Λ)=tr(T(uv))+2τ∥∥∥R^y−ΦT(uv)ΦH∥∥∥F2+⟨Λ,U−T(uv)⟩+2ρ∥U−T(uv)∥F2 这个怎么来的在之前博客中已经讲过，不再赘述了。 简单来说， 就是对原始的目标函数中加入对应于约束条件 U = T ( u v ) U=\mathrm{T}\left(\boldsymbol{u}_{v}\right) U=T(uv)的两项，一项即 ⟨ Λ , U − T ( u v ) ⟩ = t r ( Λ H ( U − T ( u v ) ) ) \left\langle\boldsymbol{\Lambda}, \boldsymbol{U}-\mathrm{T}\left(\boldsymbol{u}_{v}\right)\right\rangle = \mathrm{tr}(\boldsymbol{\Lambda}^H( \boldsymbol{U}-\mathrm{T}\left(\boldsymbol{u}_{v}\right))) ⟨Λ,U−T(uv)⟩=tr(ΛH(U−T(uv)))，也即通过引入拉格朗日乘子将限制条件写入目标中，后面这个二乘项 ρ 2 ∥ U − T ( u v ) ∥ F 2 \frac{\rho}{2}\left\|\boldsymbol{U}-\mathrm{T}\left(\boldsymbol{u}_{v}\right)\right\|_{F}^{2} 2ρ∥U−T(uv)∥F2则是为了确保强凸性和收敛性所引入的。 那么，最关键的问题是， U ⪰ 0 , \boldsymbol{U} \succeq 0 \text {, } U⪰0, 这个最棘手的约束去哪了呢？
关于此，我见过的最常见的做法是通过引入一个示性函数 I ( U ) I(U) I(U)加到目标函数中，即当 U ⪰ 0 U\succeq 0 U⪰0时为0，否则则为 + ∞ +\infty +∞，以此等效地代替这一显式的约束。最大化速率的智能反射面波束成形（下）： ADMM 中也是如此的做法。 不过我更喜欢本文中的做法，也就是在求解 U U U的时候考虑这一约束，不需要强行地转化成一个完全的无约束问题。 这两种做法实质上是完全等价的。 我们继续看，那么根据ADMM算法的思想，我们只需要进行如下的更新来对问题进行求解： u v l + 1 = arg min u v L ( u v , U l , Λ l ) U l + 1 = arg min U ⪰ 0 L ( u v l + 1 , U , Λ l ) Λ l + 1 = Λ l + ρ ( U l + 1 − T ( u v l + 1 ) ) \begin{aligned} \boldsymbol{u}_{v}^{l+1} &=\arg \min _{\boldsymbol{u}_{v}} \mathcal{L}\left(\boldsymbol{u}_{v}, \boldsymbol{U}^{l}, \boldsymbol{\Lambda}^{l}\right) \\ \boldsymbol{U}^{l+1} &=\arg \min _{\boldsymbol{U} \succeq 0} \mathcal{L}\left(\boldsymbol{u}_{v}^{l+1}, \boldsymbol{U}, \boldsymbol{\Lambda}^{l}\right) \\ \boldsymbol{\Lambda}^{l+1} &=\boldsymbol{\Lambda}^{l}+\rho\left(\boldsymbol{U}^{l+1}-\mathrm{T}\left(\boldsymbol{u}_{v}^{l+1}\right)\right) \end{aligned} uvl+1Ul+1Λl+1=arguvminL(uv,Ul,Λl)=argU⪰0minL(uvl+1,U,Λl)=Λl+ρ(Ul+1−T(uvl+1)) 这个顺序其实就是所谓的交替优化，在每一步中只优化一个变量而固定其余变量。 需要注意的有以下几点：
- 通过我们引入人工变量的骚操作， 在函数中出现最多的原始变量 u v \boldsymbol{u}_{v} uv (与 T ( u v ) \mathrm{T}\left(\boldsymbol{u}_{v}\right) T(uv)一一对应，因此等价)， 此刻已经没有任何的约束。
- U \boldsymbol{U} U的优化中则需要考虑 U ⪰ 0 {\boldsymbol{U} \succeq 0} U⪰0这个约束。 很明显， U U U起到了给原始变量挡刀的作用。需要指出的是， 如果通过示性函数的方式将约束写进目标函数中，则此处也是无约束优化问题，但由于示性函数的存在，本质上求解的时候还是约束优化。所以我个人觉得没必要引入示性函数，就按这篇作者的做法就挺好， 相当于ADMM就是个约束转移大法。
- Λ \boldsymbol{\Lambda} Λ的更新直接就写出来了，这是因为可以直接通过导数为0的一阶条件，求得其闭式解，就是这一更新步骤。
- 需要注意的是， 对每个变量的更新能要求取到的是全局最优解。 笔者不太清楚，如果对变量的更新是局部最优解的话，算法还能有效吗? 如果可以的话，将进一步拓宽ADMM算法的适用性。
因此，通过 ADMM算法来求解问题，只剩下最后两步，即 u v \mathbf{u}_v uv的具体最优解和 U U U的具体最优解。为此，我们使用 ADMM算法简介中所介绍过的ADMM算法的scaled形式，增广拉格朗日函数可以改写为： L ( u v , U , Λ ) = tr ( T ( u v ) ) + τ 2 ∥ R ^ y − Φ T ( u v ) Φ H ∥ F 2 − 1 2 ρ ∥ Λ ∥ F 2 + ρ 2 ∥ U − T ( u v ) + ρ − 1 Λ ∥ F 2 \begin{aligned} \mathcal{L}\left(\boldsymbol{u}_{v}, \boldsymbol{U}, \boldsymbol{\Lambda}\right) =& \operatorname{tr}\left(\mathrm{T}\left(\boldsymbol{u}_{v}\right)\right)+\frac{\tau}{2}\left\|\hat{\boldsymbol{R}}_{y}-\boldsymbol{\Phi} \mathrm{T}\left(\boldsymbol{u}_{v}\right) \Phi^{H}\right\|_{F}^{2}-\frac{1}{2 \rho}\|\boldsymbol{\Lambda}\|_{F}^{2} +\frac{\rho}{2}\left\|\boldsymbol{U}-\mathrm{T}\left(\boldsymbol{u}_{v}\right)+\rho^{-1} \boldsymbol{\Lambda}\right\|_{F}^{2} \end{aligned} L(uv,U,Λ)=tr(T(uv))+2τ∥∥∥R^y−ΦT(uv)ΦH∥∥∥F2−2ρ1∥Λ∥F2+2ρ∥∥U−T(uv)+ρ−1Λ∥∥F2 对比后我们不难发现，相比于最初形式，scaled的形式是将后面两项一起写进了一个最小二乘项中。 这一点在对 U U U的求解中非常重要：相当于对 U U U的更新就是一个带约束的最小欧式距离问题。对于这个式子，我们要对 u v \mathbf{u}_v uv求最小值，也即对齐求导令导数为 0 0 0，即: ∂ ∂ u v ∗ L ( u v , U l , Λ l ) ∣ u v = u v l + 1 = 0 \left.\frac{\partial}{\partial \boldsymbol{u}_{v}^{*}} \mathcal{L}\left(\boldsymbol{u}_{v}, \boldsymbol{U}^{l}, \boldsymbol{\Lambda}^{l}\right)\right|_{\boldsymbol{u}_{v}=\boldsymbol{u}_{v}^{l+1}}=0 ∂uv∗∂L(uv,Ul,Λl)∣∣∣∣uv=uvl+1=0 即可得到闭式解。 这其中的推导涉及Toeplitz矩阵相关，比较复杂一些，我们就略过了，感兴趣的读者可以去文中看。 总而言之， 利用ADMM方法， u v \boldsymbol{u}_{v} uv的更新是一个无约束优化问题，可以直接通过导数为0这一一阶条件得到。
接下来就是对 U U U的更新。 注意到，此处我们最终仍是躲不开地终将面对 U ⪰ 0 U\succeq 0 U⪰0这个限制条件了，然而， U U U对应的函数形式却比原函数简单了很多。 参考scaled后的增广拉格朗日函数，与 U U U相关项只有： ρ 2 ∥ U − T ( u v ) + ρ − 1 Λ ∥ F 2 \frac{\rho}{2}\left\|\boldsymbol{U}-\mathrm{T}\left(\boldsymbol{u}_{v}\right)+\rho^{-1} \boldsymbol{\Lambda}\right\|_{F}^{2} 2ρ∥∥U−T(uv)+ρ−1Λ∥∥F2 也即我们要寻找能最小化上式的半正定矩阵。 我们可以令 Ξ l = T ( u v l + 1 ) − ρ − 1 Λ l = E l Σ l E l H \Xi^{l}=\mathrm{T}\left(\boldsymbol{u}_{v}^{l+1}\right)-\rho^{-1} \boldsymbol{\Lambda}^{l}=\boldsymbol{E}^{l} \boldsymbol{\Sigma}^{l} \boldsymbol{E}^{l^{H}} Ξl=T(uvl+1)−ρ−1Λl=ElΣlElH 最右是对该矩阵进行了特征分解。 那么，最优的半正定矩阵解就是 U l + 1 = E l Σ + l E l H \boldsymbol{U}^{l+1}=\boldsymbol{E}^{l} \Sigma_{+}^{l} \boldsymbol{E}^{l^{H}} Ul+1=ElΣ+lElH 其中 Σ + l \Sigma_{+}^{l} Σ+l代表将 Σ l \boldsymbol{\Sigma}^{l} Σl中的所有负数置为0.
我们来总结以下这一步中的经验。 首先，ADMM算法的优势就在于， 尽管对于人工变量的优化中我们还是要面对棘手的限制条件，但此时，目标函数已经是最小二乘项的形式了(无论原函数是什么形式)，非常易于处理。我们也可以理解为， 是在一个可行域中寻找到某一给定点，欧式距离最短的点。 例如本例中，就是寻找在 U ⪰ 0 U\succeq 0 U⪰0上， 距离给定点 Ξ l \Xi^{l} Ξl最近的点。 这实际上对应的物理意义是什么呢？ 就是投影。 而对于半正定矩阵可行域，欧式距离最短的点就是由其所有非负特征值对应的特征向量组合而成的结果。 （严格的推导思路可参考低秩矩阵近似求解)
事实上，在最大化速率的智能反射面波束成形（下）： ADMM 中也是如此， 最终我们是在做点到一个圆周上的投影，大家可以自己进一步体会以下。
至此，ADMM算法就可以成功用于降低SDP算法的复杂度了。 用一句话总结的话就是：对于复杂函数下的棘手约束，利用ADMM，可以将其转化为该约束下的最小化欧式距离问题，从而大幅降低难度。
