nach oben

Journal of Scientific Computing

Erschienen in:

01.02.2013

Accelerated Linearized Bregman Method

verfasst von: Bo Huang, Shiqian Ma, Donald Goldfarb

Erschienen in: Journal of Scientific Computing | Ausgabe 2-3/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we propose and analyze an accelerated linearized Bregman (ALB) method for solving the basis pursuit and related sparse optimization problems. This accelerated algorithm is based on the fact that the linearized Bregman (LB) algorithm first proposed by Stanley Osher and his collaborators is equivalent to a gradient descent method applied to a certain dual formulation. We show that the LB method requires O(1/ϵ) iterations to obtain an ϵ-optimal solution and the ALB algorithm reduces this iteration complexity to \(O(1/\sqrt{\epsilon})\) while requiring almost the same computational effort on each iteration. Numerical results on compressed sensing and matrix completion problems are presented that demonstrate that the ALB method can be significantly faster than the LB method.

Vorheriger Artikel Simulations of Supersonic Astrophysical Jets and Their Environments Using Level Set Methods

Nächster Artikel A Coupled Level Set-Moment of Fluid Method for Incompressible Two-Phase Flows

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Nur mit Berechtigung zugänglich

Barzilai, J., Borwein, J.: Two point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988) MathSciNetMATHCrossRef

Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183–202 (2009) MathSciNetMATHCrossRef

Becker, S., Candès, E.J., Grant, M.: Templates for convex cone problems with applications to sparse signal recovery. Math. Program. Comput. 3, 165–218 (2011) MathSciNetMATHCrossRef

Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Upper Saddle River (1989) MATH

Bregman, L.: The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming. U.S.S.R. Comput. Math. Math. Phys. 7, 200–217 (1967) CrossRef

Cai, J., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20, 1956–1982 (2010) MathSciNetMATHCrossRef

Cai, J.-F., Osher, S., Shen, Z.: Linearized Bregman iterations for compressed sensing. Math. Comput. 78, 1515–1536 (2009) MathSciNetMATHCrossRef

Cai, J.-F., Osher, S., Shen, Z.: Convergence of the linearized Bregman iteration for ℓ ₁-norm minimization. Math. Comput. 78, 2127–2136 (2009) MathSciNetMATHCrossRef

Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9, 717–772 (2009) MathSciNetMATHCrossRef

10.

Candès, E.J., Tao, T.: The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inf. Theory 56, 2053–2080 (2009) CrossRef

11.

Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52, 489–509 (2006) MATHCrossRef

12.

Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory 52, 1289–1306 (2006) MathSciNetCrossRef

13.

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

14.

Goldfarb, D., Ma, S.: Fast multiple splitting algorithms for convex optimization. Tech. report, Department of IEOR, Columbia University (2009). Preprint, available at http://arxiv.org/abs/0912.4570

15.

Goldfarb, D., Ma, S.: Convergence of fixed point continuation algorithms for matrix rank minimization. Found. Comput. Math. 11, 183–210 (2011) MathSciNetMATHCrossRef

16.

Goldfarb, D., Ma, S., Scheinberg, K.: Fast alternating linearization methods for minimizing the sum of two convex functions. Math. Program. Ser. A (2012). doi:10.1007/s10107-012-0530-2

17.

Goldfarb, D., Scheinberg, K.: Fast first-order methods for composite convex optimization with line search. Technical Report, Department of IEOR, Columbia University (2011)

18.

Gross, D.: Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inf. Theory 57, 1548–1566 (2011) CrossRef

19.

Hale, E.T., Yin, W., Zhang, Y.: Fixed-point continuation for ℓ ₁-minimization: methodology and convergence. SIAM J. Optim. 19, 1107–1130 (2008) MathSciNetMATHCrossRef

20.

Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320 (1969) MathSciNetMATHCrossRef

21.

Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Program., Ser. B 45, 503–528 (1989) MathSciNetMATHCrossRef

22.

Liu, Y., Sun, D., Toh, K.-C.: An implementable proximal point algorithmic framework for nuclear norm minimization. Math. Program. (2011). doi:10.1007/s10107-010-0437-8

23.

Ma, S., Goldfarb, D., Chen, L.: Fixed point and Bregman iterative methods for matrix rank minimization. Math. Program., Ser. A 128, 321–353 (2011) MathSciNetMATHCrossRef

24.

Mangasarian, O.L., Meyer, R.R.: Nonlinear perturbation of linear programs. SIAM J. Control Optim. 17, 745–752 (1979) MathSciNetMATHCrossRef

25.

Natarajan, B.K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 24, 227–234 (1995) MathSciNetMATHCrossRef

26.

Nemirovski, A.: Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15, 229–251 (2005) MathSciNetCrossRef

27.

Nesterov, Y.E.: A method for unconstrained convex minimization problem with the rate of convergence \(\mathcal{O}(1/k^{2})\). Dokl. Akad. Nauk SSSR 269, 543–547 (1983) MathSciNet

28.

Nesterov, Y.E.: In: Introductory Lectures on Convex Optimization, vol. 87, p. xviii+236 (2004). A basic course

29.

Nesterov, Y.E.: Smooth minimization for non-smooth functions. Math. Program., Ser. A 103, 127–152 (2005) MathSciNetMATHCrossRef

30.

Nesterov, Y.E.: Gradient methods for minimizing composite objective function. CORE Discussion Paper 2007/76 (2007)

31.

Osher, S., Burger, M., Goldfarb, D., Xu, J., Yin, W.: An iterative regularization method for total variation-based image restoration. Multiscale Model. Simul. 4, 460–489 (2005) MathSciNetMATHCrossRef

32.

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

33.

Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Fletcher, R. (ed.) Optimization, pp. 283–298. Academic Press, New York (1972)

34.

Recht, B.: A simpler approach to matrix completion. J. Mach. Learn. Res. 12, 3413–3430 (2011) MathSciNet

35.

Recht, B., Fazel, M., Parrilo, P.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52, 471–501 (2010) MathSciNetMATHCrossRef

36.

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

37.

Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1, 97–116 (1976) MathSciNetMATHCrossRef

38.

ACM SIGKDD and Netflix: In: Proceedings of kdd Cup and Workshop, Proceedings available online at http://www.cs.uic.edu/~liub/KDD-cup-2007/proceedings.html (2012)

39.

Srebro, N.: Learning with matrix factorizations. PhD thesis, Massachusetts Institute of Technology (2004)

40.

Srebro, N., Jaakkola, T.: Weighted low-rank approximations. In: Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003) (2003)

41.

Toh, K.-C., Yun, S.: An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pac. J. Optim. 6, 615–640 (2010) MathSciNetMATH

42.

Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization. SIAM J. Optim. (2008, submitted)

43.

van den Berg, E., Friedlander, M.P.: Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31, 890–912 (2008) MathSciNetMATHCrossRef

44.

Wen, Z., Yin, W., Zhang, Y.: Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Technical Report, Department of CAAM, Rice University (2010)

45.

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

46.

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

Titel: Accelerated Linearized Bregman Method
verfasst von: Bo Huang
Shiqian Ma
Donald Goldfarb
Publikationsdatum: 01.02.2013
Verlag: Springer US
Erschienen in: Journal of Scientific Computing / Ausgabe 2-3/2013
Print ISSN: 0885-7474
Elektronische ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-012-9592-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2-3/2013

A New Nonsymmetric Discontinuous Galerkin Method for Time Dependent Convection Diffusion Equations

Efficient Rearrangement Algorithms for Shape Optimization on Elliptic Eigenvalue Problems

Higher-Order TV Methods—Enhancement via Bregman Iteration

An Efficient Algorithm for ℓ 0 Minimization in Wavelet Frame Based Image Restoration

Optimal Trajectories of Curvature Constrained Motion in the Hamilton–Jacobi Formulation

Negative-Order Norm Estimates for Nonlinear Hyperbolic Conservation Laws