Linearized Krylov subspace Bregman iteration with nonnegativity constraint
- PDF / 4,122,040 Bytes
- 24 Pages / 439.642 x 666.49 pts Page_size
- 42 Downloads / 192 Views
Linearized Krylov subspace Bregman iteration with nonnegativity constraint Alessandro Buccini1
· Mirjeta Pasha2 · Lothar Reichel3
Received: 10 March 2020 / Accepted: 17 August 2020 / © The Author(s) 2020
Abstract Bregman-type iterative methods have received considerable attention in recent years due to their ease of implementation and the high quality of the computed solutions they deliver. However, these iterative methods may require a large number of iterations and this reduces their usefulness. This paper develops a computationally attractive linearized Bregman algorithm by projecting the problem to be solved into an appropriately chosen low-dimensional Krylov subspace. The projection reduces the computational effort required for each iteration. A variant of this solution method, in which nonnegativity of each computed iterate is imposed, also is described. Extensive numerical examples illustrate the performance of the proposed methods. Keywords Linearized Bregman iteration · Ill-posed problem · Krylov subspace · Nonnegativity constraint Mathematics Subject Classification (2010) 65F22 · 65K10 · 65R32
Alessandro Buccini
[email protected] Mirjeta Pasha [email protected] Lothar Reichel [email protected] 1
Department of Mathematics and Computer Science, University of Cagliari, Via Ospedale 72, 09124 Cagliari, Italy
2
School of Mathematical and Statistical Sciences, Arizona State University, Tempe, 85281 AZ, USA
3
Department of Mathematical Sciences, Kent State University, 1300 Lefton Esplanade, Kent, 44242 OH, USA
Numerical Algorithms
1 Introduction Many applications in science and engineering require the solution of minimization problems of the form: minn Au − b2 , (1) u∈R
Rm×n
is a matrix, whose singular values gradually decay to zero with no where A ∈ significant gap; the matrix may be rank deficient. Throughout this paper, · 2 stands for the Euclidean vector norm. The vector b ∈ Rm represents data that is corrupted by an unknown error e ∈ Rm , which may stem from measurement or discretization inaccuracies. We will refer to the error e as “noise.” Problems of this kind arise, for instance, from the discretization of Fredholm integral equations of the first kind and are commonly referred to as linear discrete inverse ill-posed problems; see, e.g., [17, 22, 23] for discussions on discrete inverse ill-posed problems. We are primarily interested in the situation when m ≤ n, but the methods described also can be applied when m > n. Let btrue denote the unknown error-free vector associated with b, i.e.: b = btrue + e, and let R(A) denote the range of A. We will assume that btrue ∈ R(A) and that a fairly accurate bound for the error: e2 ≤ ,
(2)
is known. This allows application of the discrepancy principle; see below. Let A† denote the Moore–Penrose pseudo-inverse of A. We would like to determine an accurate approximation of utrue = A† btrue , i.e., of the minimum-norm solution of: minn Au − btrue 2 . u∈R
We remark that the exact solution of (1) can be expressed as A† b. Due to t
Data Loading...
