  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.
