Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-23T18:30:04.371Z Has data issue: false hasContentIssue false
  • English
  • Français

Linearized Alternating Direction Method of Multipliers for Constrained Linear Least-Squares Problem

Published online by Cambridge University Press:  28 May 2015

Raymond H. Chan ,
Min Tao  and
Xiaoming Yuan
Raymond H. Chan*
Affiliation:
Department of Mathematics, The Chinese University of Hong Kong, Shatin, NT, Hong Kong, China
Min Tao*
Affiliation:
School of Science, Nanjing University of Posts and Telecommunications, Nanjing, Jiangsu, China
Xiaoming Yuan*
Affiliation:
Department of Mathematics, Hong Kong Baptist University, Hong Kong, China
*
Corresponding author. Email: [email protected]
Corresponding author. Email: [email protected]
Corresponding author. Email: [email protected]
Get access

Abstract.

The alternating direction method of multipliers (ADMM) is applied to a constrained linear least-squares problem, where the objective function is a sum of two least-squares terms and there are box constraints. The original problem is decomposed into two easier least-squares subproblems at each iteration, and to speed up the inner iteration we linearize the relevant subproblem whenever it has no known closed-form solution. We prove the convergence of the resulting algorithm, and apply it to solve some image deblurring problems. Its efficiency is demonstrated, in comparison with Newton-type methods.

Keywords

68U1065J2265K1065T5090C25Linear least-squares problemsalternating direction method of multiplierslinearizationimage processing
Type
Research Article
Information
East Asian Journal on Applied Mathematics , Volume 2 , Issue 4 , November 2012 , pp. 326 - 341
Copyright
Copyright © Global-Science Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Barzilai, J. and Borwein, J. M., Two point step size gradient methods, IMA J. Numer. Anal., 8, pp. 141–148, 1988.Google Scholar
[2]Beck, A. and Teboulle, M., A fast iterative shrinkage-Thresholding algorithms for inner inverse problems, SIAM J. Imag. Sci., 2, pp. 183–202, 2009.CrossRefGoogle Scholar
[3]Bellavia, S., Macconi, M. and Morini, B., An interior Newton-like method for nonnegative least-squares problems with degenerate solution, Numer Linear Algebra Appl., 13, pp. 825–846, 2006.CrossRefGoogle Scholar
[4]Björck, A., Numerical Methods for Least Squares Problems, SIAM, 1996.Google Scholar
[5]Calvetti, D., Landi, G., Reichel, L. and Sgallari, F., Nonnegativity and iterative methods for ill-posed problems, Inverse Probl., 20, pp. 1747–1758, 2004.CrossRefGoogle Scholar
[6]Chan, R. H. and Ng, M. K., Conjugate gradient method for Toeplitz systems, SIAM Review, 38, pp. 427–482, 1996.Google Scholar
[7]Chan, R. H., Morini, B. and Porcelli, M., Affine scaling methods for image deblurring problems, American Institute of Physics Conference Proceedings, 1281 (2), pp. 1043–1046, 2010.Google Scholar
[8]Chan, R. H., Yang, J. F. and Yuan, X. M., Alternating direction method for image inpainting in wavelet domain, SIAM J. Imag. Sci., 4, pp. 807–826, 2011.CrossRefGoogle Scholar
[9]Coleman, T. and Li, Y., An interior trust-region approach for nonlinear minimization subject to bounds, SIAM J. Optim., 6, pp. 418–445, 1996.Google Scholar
[10]Ehrgott, M. and Winz, I., Interactive decision support in radiation therapy treatment planning, OR Spectrum, 30, pp. 311–329, 2008.Google Scholar
[11]Esser, E., Applications of Lagrangian-Based alternating direction methods and connections to split Bregman, UCLA CAM Report 09-31, 2009.Google Scholar
[12]Fukushima, M., Application of the alternating direction method of multipliers to separable convex programming problems, Comput. Optim. Appl., 1, pp. 93–111, 1992.CrossRefGoogle Scholar
[13]Gabay, D. and Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Comput. Math. Appl., 2, pp. 17–40, 1976.CrossRefGoogle Scholar
[14]Gabay, D., Applications of the method of multipliers to variational inequalities, in Augmented Lagrange Methods: Applications to the Solution of Boundary-valued Problems, M. Fortin and R. Glowinski, North Holland, Amsterdam, Holland, pp. 299–331, 1983.Google Scholar
[15]Glowinski, R. and Marrocco, A., Sur lapproximation par elements finis dordre un, et la resolution par penalisation-dualite dune classe de problemes de Dirichlet nonlineaires, Rev. Francaise dAut. Inf. Rech. Oper., 2, pp. 41–76, 1975.Google Scholar
[16]Glowinski, R. and Le Tallec, P., Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM Studies in Applied Mathematics, Philadelphia, PA, 1989.Google Scholar
[17]Goldstein, T. and Osher, S., The split Bregman method for L1 -Regularized Prolbems, SIAM J. Imag. Sci., 2, pp. 323–343, 2009.CrossRefGoogle Scholar
[18]Gonzalez, R. and Woods, R., Digital Image Processing, 3rd ed., Prentice Hall, NJ, 2008.Google Scholar
[19]He, B. S., Liao, L. Z., Han, D. and Yang, H., A new inexact alternating directions method for monotone variational inequalities, Math. Program., 92, pp. 103–118, 2002.Google Scholar
[20]He, B. S., Yang, H. and Wang, S. L., Alternating direction method with self-adaptive penalty parameters for monotone variational inequality, J. Optim. Theory Appl., 106, pp. 337–356, 2000.Google Scholar
[21]Hestenes, M. R., Multiplier and gradient methods, J. Optim. Theory Appl., 4, pp. 303–320, 1969.Google Scholar
[22]Huang, Y. M., Ng, M. K. and Wen, Y. W., A fast total variational minimization method for image restoration, SIAM Multi. Modeling Simul., 7, pp. 774–795, 2008.Google Scholar
[23]Lawson, C. L. and Hanson, R. J., Solving Least Squares Problems, Prentice-Hall, Englewood Cliffs, NJ, 1974.Google Scholar
[24]Morini, B., Porcelli, M. and Chan, R. H., A reduced Newton method for constrained linear least-squares problems, J. Comput. Appl. Math., 233, pp. 2200–2212, 2010.Google Scholar
[25]Morigi, S., Reichel, L., Sgallari, F. and Zama, F., An iterative method for linear discrete ill-posed problems with boxconstrints, J. Comput. Appl. Math., 198, pp. 505–520, 2007.Google Scholar
[26]Ng, M. K., Chan, R. H. and Tang, W.-C., A fast algorithm for deblurring models with Neumann boundaryconditions, SIAM J. Sci. Comput., 21, pp. 851–866, 1999.CrossRefGoogle Scholar
[27]Ng, M. K., Wang, F. and Yuan, X. M., Fast minimization methods for solving constrained totalvariation superresolution image reconstruction, Multi. Syst. Signal Proces., 22, pp. 259–286, 2011.Google Scholar
[28]Ng, M. K., Weiss, P. A. and Yuan, X. M., Solving constrained total-variation problems via alternating direction methods, SIAM J. Sci. Comput., 32(5), pp. 2710–2736, 2010.CrossRefGoogle Scholar
[29]Portugal, L. F., Joaquim, J. J. and Vicente, L. N., A comparison of block pivoting and interior-point algorithms for linear least squares problems with nonnegative variables, Math. Comp., 63, pp. 625–643, 1994.Google Scholar
[30]Powell, M. J. D., A method for nonlinear constraints in minimization problems, in Optimization, Fletcher, R. (Ed.), Academic Press, New York, pp. 283–298, 1969.Google Scholar
[31]Rojas, M. and Steihaug, T., An interior-point trust-region-based method for large-scale nonnegative regularization, Inverse Probl., 18, pp. 1291–1307, 2002.Google Scholar
[32]Rudin, L. I., Osher, S. and Fatemi, E., Nonlinear total variation based noise removal algorithms, Physica D, 60, pp. 259–268, 1992.Google Scholar
[33]Setzer, S., Split Bregman algorithm, Douglas-Rachford splitting, and frame shrinkage, Lect. Notes Comput. Sci., 5567, pp. 464–476, 2009.Google Scholar
[34]Setzer, S., Steidl, G. and Tebuber, T., Deblurring Poissonian images bysplit Bregman techniques, J. Vis. Commun. Image Repres., 21, pp. 193–199, 2010.Google Scholar
[35]Stoer, J. and Bulirsch, R., Introduction to Numerical Analysis, Texts in Applied Mathematics, No. 12, Springer, 2007.Google Scholar
[36]Tao, M. and Yuan, X. M., Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim., 21(1), pp. 57–81, 2011.Google Scholar
[37]Tikhonov, A. and Arsenin, V., Solution of Ill-Posed Problems, Winston, Washington, DC, 1977.Google Scholar
[38]Tseng, P., Applications of splitting algorithm to decomposition in convex programming and vartiational inequalities, SIAM J. Control Optim., 29, pp. 119–138, 1991.CrossRefGoogle Scholar