In linear inverse problems, we have data derived from a noisy linear transformation of some unknown parameters, and we wish to estimate these unknowns from the data. Separable inverse problems are a powerful generalization in which the transformation itself depends on additional unknown parameters and we wish to determine both sets of parameters simultaneously. When separable problems are solved by optimization, convergence can often be accelerated by elimination of the linear variables, a strategy which appears most prominently in the variable projection methods due to Golub and Pereyra. Existing variable elimination methods require an explicit formula for the optimal value of the linear variables, so they cannot be used in problems with Poisson likelihoods, bound constraints, or other important departures from least squares. To address this limitation, we propose a generalization of variable elimination in which standard optimization methods are modified to behave as though a variable has been eliminated. We verify that this approach is a proper generalization by using it to re-derive several existing variable elimination techniques. We then extend the approach to bound-constrained and Poissonian problems, showing in the process that many of the best features of variable elimination methods can be duplicated in our framework. Tests on difficult exponential sum fitting and blind deconvolution problems indicate that the proposed approach can have significant speed and robustness advantages over standard methods.
While the relationship between full and reduced update methods has been explored several times, the relationship established here is a major extension of previous work. In @cite_9 Ruhe and Wedin developed the connection between full and reduced update Newton and Gauss-Newton methods, and semi-reduced methods are described by Smyth as or methods in @cite_51 . Our work extends theirs in that we consider general Newton-type methods, nonquadratic likelihoods, and the effect of globalization strategies, such as line search or trust regions, which ensure convergence to a stationary point from arbitrary initialization. A very general theoretical analysis of the relationship between the full and reduced problems is given in @cite_25 , but there is little discussion of practical algorithms and no mention of semi-reduced methods.
@cite_9 @cite_51 @cite_25
2040763577 2017638737 2587432537
Iterative algorithms of Gauss–Newton type for the solution of nonlinear least squares problems are considered. They separate the variables into two sets in such a way that in each iteration, optimization with respect to the first set is performed first, and corrections to those of the second after that. The linear-nonlinear case, where the first set consists of variables that occur linearly, is given special attention, and a new algorithm is derived which is simpler to apply than the variable projection algorithm as described by Golub and Pereyra, and can be performed with no more arithmetical operations than the unseparated Gauss–Newton algorithm. A detailed analysis of the asymptotical convergence properties of both separated and unseparated algorithms is performed. It is found that they have comparable rates of convergence, and all converge almost quadratically for almost compatible problems. Simpler separation schemes, on the other hand, converge only linearly. An efficient and simple computer impleme... There are a variety of methods in the literature which seek to make iterative estimation algorithms more manageable by breaking the iterations into a greater number of simpler or faster steps. Those algorithms which deal at each step with a proper subset of the parameters are called in this paper partitioned algorithms. Partitioned algorithms in effect replace the original estimation problem with a series of problems of lower dimension. The purpose of the paper is to characterize some of the circumstances under which this process of dimension reduction leads to significant benefits.