skip to main content
10.1145/2487575.2487586acmconferencesArticle/Chapter ViewAbstractPublication PageskddConference Proceedingsconference-collections
poster

An efficient ADMM algorithm for multidimensional anisotropic total variation regularization problems

Authors Info & Claims
Published:11 August 2013Publication History

ABSTRACT

Total variation (TV) regularization has important applications in signal processing including image denoising, image deblurring, and image reconstruction. A significant challenge in the practical use of TV regularization lies in the nondifferentiable convex optimization, which is difficult to solve especially for large-scale problems. In this paper, we propose an efficient alternating augmented Lagrangian method (ADMM) to solve total variation regularization problems. The proposed algorithm is applicable for tensors, thus it can solve multidimensional total variation regularization problems. One appealing feature of the proposed algorithm is that it does not need to solve a linear system of equations, which is often the most expensive part in previous ADMM-based methods. In addition, each step of the proposed algorithm involves a set of independent and smaller problems, which can be solved in parallel. Thus, the proposed algorithm scales to large size problems. Furthermore, the global convergence of the proposed algorithm is guaranteed, and the time complexity of the proposed algorithm is O(dN/ε) on a d-mode tensor with N entries for achieving an ε-optimal solution. Extensive experimental results demonstrate the superior performance of the proposed algorithm in comparison with current state-of-the-art methods.

References

  1. A. Barbero and S. Sra. Fast newton-type methods for total variation regularization. In ICML, 2011.Google ScholarGoogle Scholar
  2. A. Beck and M. Teboulle. Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. Image Processing, IEEE Transactions on, 18(11):2419--2434, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. A. Beck and M. Teboulle. A fast iterative shrinkage thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183--202, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine Learning, 3(1):1--122, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. S. Boyd and L. Vandenberghe. Convex optimation, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. A. Chambolle. An algorithm for total variation minimization and applications. Journal of Mathematical imaging and vision, 20(1):89--97, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. P. Combettes and J. Pesquet. Proximal splitting methods in signal processing. Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pages 185--212, 2011.Google ScholarGoogle ScholarCross RefCross Ref
  8. L. Condat. A direct algorithm for 1d total variation denoising. 2012.Google ScholarGoogle Scholar
  9. A. Dhara and J. Dutta. Optimality Conditions in Convex Optimization, A finite-dimensional view. CRC Press, 2012.Google ScholarGoogle Scholar
  10. J. Eckstein and D. Bertsekas. On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55(1):293--318, 1992. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. J. Friedman, T. Hastie, H. Höfling, and R. Tibshirani. Pathwise coordinate optimization. The Annals of Applied Statistics, 1(2):302--332, 2007.Google ScholarGoogle ScholarCross RefCross Ref
  12. T. Goldstein and S. Osher. The split Bregman method for l1-regularized problems. SIAM Journal on Imaging Sciences, 2(2):323--343, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. B. He and X. Yuan. On the o(1/n) convergence rate of the Douglas-Rachford alternating direction method. SIAM Journal on Numerical Analysis, 50(2):700--709, 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. J. Huang, S. Zhang, and D. Metaxas. Efficient MR image reconstruction for compressed mr imaging. Medical Image Analysis, 15(5):670--679, 2011.Google ScholarGoogle ScholarCross RefCross Ref
  15. C. Li, W. Yin, and Y. Zhang. Tval3: Tv minimization by augmented lagrangian and alternating direction algorithms, 2009.Google ScholarGoogle Scholar
  16. J. Liu, L. Yuan, and J. Ye. An efficient algorithm for a class of fused lasso problems. In KDD, pages 323--332, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. S. Ma, W. Yin, Y. Zhang, and A. Chakraborty. An efficient algorithm for compressed MR imaging using total variation and wavelets. In CVPR, pages 1--8, 2008.Google ScholarGoogle Scholar
  18. Z. Qin, D. Goldfarb, and S. Ma. An alternating direction method for total variation denoising. arXiv preprint arXiv:1108.1587, 2011.Google ScholarGoogle Scholar
  19. L. Rudin, S. Osher, and E. Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena, 60(1):259--268, 1992. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. M. Schmidt, N. Roux, and F. Bach. Convergence rates of inexact proximal-gradient methods for convex optimization. NIPS, 2011.Google ScholarGoogle Scholar
  21. M. Sion. On general minimax theorems. Pacific J. Math, 8(1):171--176, 1958.Google ScholarGoogle ScholarCross RefCross Ref
  22. C. Vogel and M. Oman. Fast, robust total variation-based reconstruction of noisy, blurred images. Image Processing, IEEE Transactions on, 7(6):813--824, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. B. Wahlberg, S. Boyd, M. Annergren, and Y. Wang. An admm algorithm for a class of total variation regularized estimation problems. IFAC, 2012.Google ScholarGoogle ScholarCross RefCross Ref
  24. J. Yang, Y. Zhang, and W. Yin. An efficient TVL1 algorithm for deblurring multichannel images corrupted by impulsive noise. SIAM Journal on Scientific Computing, 31(4):2842--2865, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. An efficient ADMM algorithm for multidimensional anisotropic total variation regularization problems

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      KDD '13: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining
      August 2013
      1534 pages
      ISBN:9781450321747
      DOI:10.1145/2487575

      Copyright © 2013 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 11 August 2013

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • poster

      Acceptance Rates

      KDD '13 Paper Acceptance Rate125of726submissions,17%Overall Acceptance Rate1,133of8,635submissions,13%

      Upcoming Conference

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader