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 this https URL
that implements efficient ADMMs for many problems in compressed sensing.

提出了 Gauss-Seidel ADMMs 和 Jacobian ADMMs 框架及其收敛分析。我们展示了这些框架可以通过最小化可分离 majorant 替代加强本来只可以解决可分离问题的 ADMMs。我们还介绍了几种提高 ADMM 效率的技术，特别地，我们提出了 M-ADMM，它通过吸收 Gauss-Seidel ADMMs 的特点来缓解 Jacobian ADMMs 的缓慢收敛问题。在理论保证和数值实验方面，我们的新 ADMMs 表现优越。此外，我们还发布了一个工具箱，其中包含了很多压缩感知问题的高效 ADMMs 的实现。