Top

Journal of Scientific Computing

Published in:

09-06-2016

Local Linear Convergence of a Primal-Dual Algorithm for the Augmented Convex Models

Authors: Tao Sun, Roberto Barrio, Hao Jiang, Lizhi Cheng

Published in: Journal of Scientific Computing | Issue 3/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Convex optimization has become an essential technique in many different disciplines. In this paper, we consider the primal-dual algorithm minimizing augmented models with linear constraints, where the objective function consists of two proper closed convex functions; one is the square of a norm and the other one is a gauge function being partly smooth relatively to an active manifold. Examples of this situation can be found in signal processing, optimization, statistics and machine learning literature. We present a unified framework to understand the local convergence behaviour of the primal-dual algorithm for these augmented models. This result explains some numerical results shown in the literature on local linear convergence of the algorithm.

previous article An Adaptive Finite Element Method for the Transmission Eigenvalue Problem

next article A High-Order Level-Set Method with Enhanced Stability for Curvature Driven Flows and Surface Diffusion Motion

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33–61 (1998)MathSciNetCrossRefMATH

Elad, M., Milanfar, P., Rubinstein, R.: Analysis versus synthesis in signal priors. Inverse Probl. 23(3), 947 (2007)MathSciNetCrossRefMATH

Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (2015)MATH

Friedlander, M.P., Tseng, P.: Exact regularization of convex programs. SIAM J. Optim. 18(4), 1326–1350 (2008)MathSciNetCrossRefMATH

Hale, E.T., Yin, W., Zhang, Y.: Fixed-point continuation for \(\ell _1\)-minimization: methodology and convergence. SIAM J. Optim. 19(3), 1107–1130 (2008)MathSciNetCrossRefMATH

Hare, W., Lewis, A.: Identifying active constraints via partial smoothness and prox-regularity. J. Conv. Anal. 11, 251–266 (2004)MathSciNetMATH

Huang, B., Ma, S., Goldfarb, D.: Accelerated linearized Bregman method. J. Sci. Comput. 54(2–3), 428–453 (2013)MathSciNetCrossRefMATH

Lai, M.J., Yin, W.: Augmented \(\ell _1\) and nuclear-norm models with a globally linearly convergent algorithm. SIAM J. Imaging Sci. 6(2), 1059–1091 (2013)MathSciNetCrossRefMATH

Lewis, A.S.: Active sets, nonsmoothness, and sensitivity. SIAM J. Optim. 13(3), 702–725 (2002)MathSciNetCrossRefMATH

10.

Lewis, A.S., Malick, J.: Alternating projections on manifolds. Math. Oper. Res. 33(1), 216–234 (2008)MathSciNetCrossRefMATH

11.

Li, Q., Micchelli, C.A., Shen, L., Xu, Y.: A proximity algorithm accelerated by Gauss–Seidel iterations for L1/TV denoising models. Inverse Probl. 28(9), 095003 (2012)MathSciNetCrossRefMATH

12.

Liang, J., Fadili, J., Peyré, G.: Local linear convergence of forward–backward under partial smoothness. In: Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N., Weinberger, K. (eds.) Advances in Neural Information Processing Systems 27, pp. 1970–1978. Curran Associates Inc, NewYork (2014)

13.

Liang, J., Fadili, J., Peyré, G., Luke, R.: Activity identification and local linear convergence of Douglas–Rachford/ADMM under partial smoothness. In: Aujol, J.F., Nikolova, M., Papadakis, N. (eds.) Scale Space and Variational Methods in Computer Vision. Lecture Notes in Computer Science, vol. 9087, pp. 642–653. Springer, NewYork (2015)

14.

Micchelli, C.A., Shen, L., Xu, Y., Zeng, X.: Proximity algorithms for the L1/TV image denoising model. Adv. Comput. Math. 38(2), 401–426 (2013)MathSciNetCrossRefMATH

15.

Osher, S., Mao, Y., Dong, B., Yin, W.: Fast linearized Bregman iteration for compressive sensing and sparse denoising. Commun. Math. Sci. 8(1), 93–111 (2010)MathSciNetCrossRefMATH

16.

Parikh, N., Boyd, S.: Proximal algorithms. Found. Trends Optim. 1(3), 127–239 (2014)CrossRef

17.

Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (2015)MATH

18.

Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer, Berlin (1998)CrossRefMATH

19.

Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Phys. D Nonlinear Phenom. 60(14), 259–268 (1992)MathSciNetCrossRefMATH

20.

Vaiter, S., Peyré, G., & Fadili, J.: Low complexity regularization of linear inverse problems. In: Pfander G.E. (ed) Sampling Theory, a Renaissance, pp. 103–153. Springer International Publishing (2015)

21.

Yin, W.: Analysis and generalizations of the linearized Bregman method. SIAM J. Imaging Sci. 3(4), 856–877 (2010)MathSciNetCrossRefMATH

22.

Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for \(\ell _1\)-minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1(1), 143–168 (2008)MathSciNetCrossRefMATH

23.

Yuan, M., Lin, Y.: Model selection and estimation in regression with grouped variables. J. R. Stat. Soc. Ser. B (Statistical Methodology) 68(1), 49–67 (2006)MathSciNetCrossRefMATH

24.

Zhang, H., Cheng, L., Yin, W.: A dual algorithm for a class of augmented convex signal recovery models. Commun. Math. Sci. 13(1), 103–112 (2015)MathSciNetCrossRefMATH

Title: Local Linear Convergence of a Primal-Dual Algorithm for the Augmented Convex Models
Authors: Tao Sun
Roberto Barrio
Hao Jiang
Lizhi Cheng
Publication date: 09-06-2016
Publisher: Springer US
Published in: Journal of Scientific Computing / Issue 3/2016
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-016-0235-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2016

A Two-Stage Low Rank Approach for Calibrationless Dynamic Parallel Magnetic Resonance Image Reconstruction

Application of WENO-Positivity-Preserving Schemes to Highly Under-Expanded Jets

Tracing Multiple Solution Branches for Nonlinear Ordinary Differential Equations: Chebyshev and Fourier Spectral Methods and a Degree-Increasing Spectral Homotopy [DISH]

Stabilized Times Schemes for High Accurate Finite Differences Solutions of Nonlinear Parabolic Equations

A Second-Order, Weakly Energy-Stable Pseudo-spectral Scheme for the Cahn–Hilliard Equation and Its Solution by the Homogeneous Linear Iteration Method

A Superconvergent Discontinuous Galerkin Method for Kirchhoff Plates: Error Estimates, Hybridization and Postprocessing

Premium Partner