A cut-and-project perspective for linearized Bregman iterations
Preprint
Abstract
The linearized Bregman iterations (LBreI) and its variants are powerful tools for finding sparse or low-rank solutions to underdetermined linear systems. In this study, we propose a cut-and-project perspective for the linearized Bregman method via a bilevel optimization formulation, along with a new unified algorithmic framework. The new perspective not only encompasses various existing linearized Bregman iteration variants as specific instances, but also allows us to extend the linearized Bregman method to solve more general inverse problems. We provide a completed convergence result of the proposed algorithmic framework, including convergence guarantees to feasible points and optimal solutions, and the sublinear convergence rate. Moreover, we introduce the Bregman distance growth condition to ensure linear convergence. At last, our findings are illustrated via numerical tests.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Revisiting linearized Bregman iterations under Lipschitz-like convexity conditionMathematics of Computation, 2022
- New analysis of linear convergence of gradient-type methods via unifying error bound conditionsMathematical Programming, 2019
- Re-examination of Bregman functions and new properties of their divergencesOptimization, 2018
- Linear convergence of first order methods for non-strongly convex optimizationMathematical Programming, 2018
- Linear convergence of the randomized sparse Kaczmarz methodMathematical Programming, 2018
- A first order method for finding minimal norm-like solutions of convex optimization problemsMathematical Programming, 2013
- Convergence of the linearized Bregman iteration for ℓ₁-norm minimizationMathematics of Computation, 2009
- Linearized Bregman iterations for compressed sensingMathematics of Computation, 2008
- Accelerated Landweber iterations for the solution of ill-posed equationsNumerische Mathematik, 1991
- The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programmingUSSR Computational Mathematics and Mathematical Physics, 1967