Ieee Transactions on Pattern Analysis and Machine Intelligence 1 a Unified Alternating Direction Method of Multipliers by Majorization Minimization
Ieee Transactions on Pattern Analysis and Machine Intelligence 1 a Unified Alternating Direction Method of Multipliers by Majorization Minimization
复制标题
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
Canyi Lu;Jiashi Feng;Shuicheng Yan;Zhouchen Lin
中科院分区：
文献类型：
--
作者：
Canyi Lu;Jiashi Feng;Shuicheng Yan;Zhouchen Lin
随着压缩感知的日益普及，交替方向乘法（ADMM）已成为线性约束可分离目标凸问题最广泛使用的求解器。在这项工作中，我们观察到，许多以前的ADMM的变种更新原始变量通过最小化不同的优函数与他们的收敛性证明的情况下。受优化最小化原理的启发，分别给出了Gauss-Seidel ADMM和Jacobian ADMM的统一框架和收敛性分析，这两种ADMM使用不同的历史信息进行当前更新。我们的框架进一步推广以前的ADMMs能够解决问题的不可分离的目标，最大限度地减少其可分离的主要代理。我们还表明，衡量ADMMs的收敛速度的界限取决于所使用的优函数的紧密性。然后介绍了几种技术，以提高ADMM的效率，收紧的优势功能。特别地，我们提出了混合高斯-赛德尔和雅可比ADMM（M-ADMM），它通过吸收高斯-赛德尔ADMM的优点来解决雅可比ADMM收敛速度慢的问题。通过使用回溯、明智的变量划分和充分利用约束的结构，可以进一步改进M-ADMM。除了理论上的保证外，在合成数据和真实数据上的数值实验进一步证明了我们的新ADMM在实践中的优越性。最后，我们在https://github.com/canyilu/LibADMM上发布了一个工具箱，该工具箱针对压缩感知中的许多问题实现了高效的ADMM。
—Accompanied with the rising popularity of compressed sensing, the Alternating Direction Method of Multipliers (ADMM) has become the most widely used solver for linearly constrained convex problems with separable objectives. In this work, we observe that many previous variants of ADMM update the primal variable by minimizing different majorant functions with their convergence proofs given case by case. Inspired by the principle of majorization minimization, we respectively present the unified frameworks and convergence analysis for the Gauss-Seidel ADMMs and Jacobian ADMMs, which use different historical information for the current updating. Our frameworks further generalize previous ADMMs to the ones capable of solving the problems with non-separable objectives by minimizing their separable majorant surrogates. We also show that the bound which measures the convergence speed of ADMMs depends on the tightness of the used majorant function. Then several techniques are introduced to improve the efficiency of ADMMs by tightening the majorant functions. In particular, we propose the Mixed Gauss-Seidel and Jacobian ADMM (M-ADMM) which alleviates the slow convergence issue of Jacobian ADMMs by absorbing merits of the Gauss-Seidel ADMMs. M-ADMM can be further improved by using backtracking, wise variable partition and fully exploiting the structure of the constraint. Beyond the guarantee in theory, numerical experiments on both synthesized and real-world data further demonstrate the superiority of our new ADMMs in practice. Finally, we release a toolbox at https://github.com/canyilu/LibADMM that implements efficient ADMMs for many problems in compressed sensing.