Nonnegative ill-conditioned linear systems and GMRES method

In this paper we consider solving ill-conditioned linear systems under nonnegativity constraints with noisy right hand sides. The classical approaches to solve such systems are constrained least square (quadratic programming) and barrier methods. First we present these classical methods. Then a modified version of the GMRES method (NGMRES) is presented. Since we assume that the coefficient matrices are ill-conditioned, then the Tikhonov regularization of the problem is considered. Our computational experiments show that the NGMRES provides us high quality solutions much faster than the other two approaches.     

Perturbation Identities for Regularized Tikhonov Inverses and Weighted Pseudoinverses

We consider the perturbation analysis of two important problems for solving ill-conditioned or rank-deficient linear least squares problems. The Tikhonov regularized problem is a linear least squares problem with a regularization term balancing the size of the residual against the size of the weighted solution. The weight matrix can be a non-square matrix (usually with fewer rows than columns). The minimum-norm problem is the minimization of the size of the weighted solutions given by the set of solutions to the, possibly rank-deficient, linear least squares problem.It is well known that the solution of the Tikhonov problem tends to the minimum-norm solution as the regularization parameter of the Tikhonov problem tends to zero. Using this fact and the generalized singular value decomposition enable us to make a perturbation analysis of the minimum-norm problem with perturbation results for the Tikhonov problem. From the analysis we attain perturbation identities for Tikhonov inverses and weighted pseudoinverses.     

约束Fractional Tikhonov正则化的模迭代方法

反问题是现在数学物理研究中的一个热点问题,而反问题求解面临的一个本质性困难是不适定性。求解不适定问题的普遍方法是:用与原不适定问题相“邻近”的适定问题的解去逼近原问题的解,这种方法称为正则化方法.如何建立有效的正则化方法是反问题领域中不适定问题研究的重要内容.当前,最为流行的正则化方法有基于变分原理的Tikhonov正则化及其改进方法,此类方法是求解不适定问题的较为有效的方法,在各类反问题的研究中被广泛采用,并得到深入研究.     

Robust regression for mixed Poisson–Gaussian model

This paper focuses on efficient computational approaches to compute approximate solutions of a linear inverse problem that is contaminated with mixed Poisson–Gaussian noise, and when there are additional outliers in the measured data. The Poisson–Gaussian noise leads to a weighted minimization problem, with solution-dependent weights. To address outliers, the standard least squares fit-to-data metric is replaced by the Talwar robust regression function. Convexity, regularization parameter selection schemes, and incorporation of non-negative constraints are investigated. A projected Newton algorithm is used to solve the resulting constrained optimization problem, and a preconditioner is proposed to accelerate conjugate gradient Hessian solves. Numerical experiments on problems from image deblurring illustrate the effectiveness of the methods.     

Algorithms for the regularization of ill-conditioned least squares problems

Two regularization methods for ill-conditioned least squares problems are studied from the point of view of numerical efficiency. The regularization methods are formulated as quadratically constrained least squares problems, and it is shown that if they are transformed into a certain standard form, very efficient algorithms can be used for their solution. New algorithms are given, both for the transformation and for the regularization methods in standard form. A comparison to previous algorithms is made and it is shown that the overall efficiency (in terms of the number of arithmetic operations) of the new algorithms is better.     

Robust solutions of quadratic optimization over single quadratic constraint under interval uncertainty

In this paper we examine non-convex quadratic optimization problems over a quadratic constraint under unknown but bounded interval perturbation of problem data in the constraint and develop criteria for characterizing robust (i.e. uncertainty-immunized) global solutions of classes of non-convex quadratic problems. Firstly, we derive robust solvability results for quadratic inequality systems under parameter uncertainty. Consequently, we obtain characterizations of robust solutions for uncertain homogeneous quadratic problems, including uncertain concave quadratic minimization problems and weighted least squares. Using homogenization, we also derive characterizations of robust solutions for non-homogeneous quadratic problems.     

Numerical methods for solving linear least squares problems

A common problem in a Computer Laboratory is that of finding linear least squares solutions. These problems arise in a variety of areas and in a variety of contexts. Linear least squares problems are particularly difficult to solve because they frequently involve large quantities of data, and they are ill-conditioned by their very nature. In this paper, we shall consider stable numerical methods for handling these problems. Our basic tool is a matrix decomposition based on orthogonal Householder transformations.Reproduction in Whole or in Part is permitted for any Purpose of the United States government. This report was supported in part by Office of Naval Research Contract Nonr-225(37) (NR 044-11) at Stanford University.     

Error estimates for the regularization of least squares problems

The a posteriori estimate of the errors in the numerical solution of ill-conditioned linear systems with contaminated data is a complicated problem. Several estimates of the norm of the error have been recently introduced and analyzed, under the assumption that the matrix is square and nonsingular. In this paper we study the same problem in the case of a rectangular and, in general, rank-deficient matrix. As a result, a class of error estimates previously introduced by the authors (Brezinski et al., Numer Algorithms, in press, 2008) are extended to the least squares solution of consistent and inconsistent linear systems. Their application to various direct and iterative regularization methods are also discussed, and the numerical effectiveness of these error estimates is pointed out by the results of an extensive experimentation.     

Constrained numerical optimization methods for blind deconvolution

This paper describes a nonlinear least squares framework to solve a separable nonlinear ill-posed inverse problem that arises in blind deconvolution. It is shown that with proper constraints and well chosen regularization parameters, it is possible to obtain an objective function that is fairly well behaved and the nonlinear minimization problem can be effectively solved by a Gauss–Newton method. Although uncertainties in the data and inaccuracies of linear solvers make it unlikely to obtain a smooth and convex objective function, it is shown that implicit filtering optimization methods can be used to avoid becoming trapped in local minima. Computational considerations, such as computing the Jacobian, are discussed, and numerical experiments are used to illustrate the behavior of the algorithms. Although the focus of the paper is on blind deconvolution, the general mathematical model addressed in this paper, and the approaches discussed to solve it, arise in many other applications.     

Regularization using a parameterized trust region subproblem

We present a new method for regularization of ill-conditioned problems, such as those that arise in image restoration or mathematical processing of medical data. The method extends the traditional trust-region subproblem, TRS, approach that makes use of the L-curve maximum curvature criterion, a strategy recently proposed to find a good regularization parameter. We apply a parameterized trust region approach to estimate the region of maximum curvature of the L-curve and find the regularized solution. This exploits the close connections between various parameters used to solve TRS. A MATLAB code for the algorithm is tested and a comparison to the conjugate gradient least squares, CGLS, approach is given and analysed.     

Rank-k modification methods for recursive least squares problems

In least squares problems, it is often desired to solve the same problem repeatedly but with several rows of the data either added, deleted, or both. Methods for quickly solving a problem after adding or deleting one row of data at a time are known. In this paper we introduce fundamental rank-k updating and downdating methods and show how extensions of rank-1 downdating methods based on LINPACK, Corrected Semi-Normal Equations (CSNE), and Gram-Schmidt factorizations, as well as new rank-k downdating methods, can all be derived from these fundamental results. We then analyze the cost of each new algorithm and make comparisons tok applications of the corresponding rank-1 algorithms. We provide experimental results comparing the numerical accuracy of the various algorithms, paying particular attention to the downdating methods, due to their potential numerical difficulties for ill-conditioned problems. We then discuss the computation involved for each downdating method, measured in terms of operation counts and BLAS calls. Finally, we provide serial execution timing results for these algorithms, noting preferable points for improvement and optimization. From our experiments we conclude that the Gram-Schmidt methods perform best in terms of numerical accuracy, but may be too costly for serial execution for large problems.Research supported in part by the Joint Services Electronics Program, contract no. F49620-90-C-0039.     

ROBUST INEXACT ALTERNATING OPTIMIZATION FOR MATRIX COMPLETION WITH OUTLIERS

We investigate the problem of robust matrix completion with a fraction of observation corrupted by sparsity outlier noise. We propose an algorithmic framework based on the ADMM algorithm for a non-convex optimization, whose objective function consists of an $\ell_1$ norm data fidelity and a rank constraint. To reduce the computational cost per iteration, two inexact schemes are developed to replace the most time-consuming step in the generic ADMM algorithm. The resulting algorithms remarkably outperform the existing solvers for robust matrix completion with outlier noise. When the noise is severe and the underlying matrix is ill-conditioned, the proposed algorithms are faster and give more accurate solutions than state-of-the-art robust matrix completion approaches.     

Robust least squares solution of linear inequalities

Least squares solution of linear inequalities appears in many disciplines such as linear separability problems and inconsistency correction. In this paper we consider this problem with uncertainty in its data. Then we prove that its robust counterpart is equivalent to a second order conic linear optimization problem, which can be efficiently solved using interior point methods.     

An iterative penalty method for the least squares solution of boundary value problems

This article is concerned with iterative techniques for linear systems of equations arising from a least squares formulation of boundary value problems. In its classical form, the solution of the least squares method is obtained by solving the traditional normal equation. However, for nonsmooth boundary conditions or in the case of refinement at a selected set of interior points, the matrix associated with the normal equation tends to be ill-conditioned. In this case, the least squares method may be formulated as a Powell multiplier method and the equations solved iteratively. Therein we use and compare two different iterative algorithms. The first algorithm is the preconditioned conjugate gradient method applied to the normal equation, while the second is a new algorithm based on the Powell method and formulated on the stabilized dual problem. The two algorithms are first compared on a one-dimensional problem with poorly conditioned matrices. Results show that, for such problems, the new algorithm gives more accurate results. The new algorithm is then applied to a two-dimensional steady state diffusion problem and a boundary layer problem. A comparison between the least squares method of Bramble and Schatz and the new algorithm demonstrates the ability of the new method to give highly accurate results on the boundary, or at a set of given interior collocation points without the deterioration of the condition number of the matrix. Conditions for convergence of the proposed algorithm are discussed. © 1997 John Wiley & Sons, Inc.     

Sparse Linear Algebra and Geophysical Migration: A Review of Direct and Iterative Methods

The pre-stack depth migration of reflection seismic data can be expressed, in the framework of waveform inversion, as a linear least squares problem. Together with the precise definition of this operator, we detail additional main characteristics of the forward model, like its huge size, its sparsity and the composition with convolution. It ends up with a so-called discrete ill-posed problem, whose acceptable solutions have to undergo a regularization procedure. Both direct and iterative methods have been implemented with specific attention to the convolution, and then applied to a given data set: a synthetic 2-dimensional profile of revealing size with some added noise. The efficiency with regard to computational effort and storage requirements is evaluated. The needed regularization of the solution is thoroughly studied in both cases. From the point of the global inverse problem, the extra feature of providing a solution that can be differentiated with respect to a parameter such as background velocity is also discussed.     

Convergence of a Scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization

We consider general nonlinear programming problems with cardinality constraints. By relaxing the binary variables which appear in the natural mixed-integer programming formulation, we obtain an almost equivalent nonlinear programming problem, which is thus still difficult to solve. Therefore, we apply a Scholtes-type regularization method to obtain a sequence of easier to solve problems and investigate the convergence of the obtained KKT points. We show that such a sequence converges to an S-stationary point, which corresponds to a local minimizer of the original problem under the assumption of convexity. Additionally, we consider portfolio optimization problems where we minimize a risk measure under a cardinality constraint on the portfolio. Various risk measures are considered, in particular Value-at-Risk and Conditional Value-at-Risk under normal distribution of returns and their robust counterparts under moment conditions. For these investment problems formulated as nonlinear programming problems with cardinality constraints we perform a numerical study on a large number of simulated instances taken from the literature and illuminate the computational performance of the Scholtes-type regularization method in comparison to other considered solution approaches: a mixed-integer solver, a direct continuous reformulation solver and the Kanzow–Schwartz regularization method, which has already been applied to Markowitz portfolio problems.     

Least squares problems with inequality constraints as quadratic constraints

Linear least squares problems with box constraints are commonly solved to find model parameters within bounds based on physical considerations. Common algorithms include Bounded Variable Least Squares (BVLS) and the Matlab function lsqlin. Here, the goal is to find solutions to ill-posed inverse problems that lie within box constraints. To do this, we formulate the box constraints as quadratic constraints, and solve the corresponding unconstrained regularized least squares problem. Using box constraints as quadratic constraints is an efficient approach because the optimization problem has a closed form solution. The effectiveness of the proposed algorithm is investigated through solving three benchmark problems and one from a hydrological application. Results are compared with solutions found by lsqlin, and the quadratically constrained formulation is solved using the L-curve, maximum a posteriori estimation (MAP), and the χ² regularization method. The χ² regularization method with quadratic constraints is the most effective method for solving least squares problems with box constraints.     

A regularized limited memory BFGS method for nonconvex unconstrained minimization

The limited memory BFGS method (L-BFGS) is an adaptation of the BFGS method for large-scale unconstrained optimization. However, The L-BFGS method need not converge for nonconvex objective functions and it is inefficient on highly ill-conditioned problems. In this paper, we proposed a regularization strategy on the L-BFGS method, where the used regularization parameter may play a compensation role in some sense when the condition number of Hessian approximation tends to become ill-conditioned. Then we proposed a regularized L-BFGS method and established its global convergence even when the objective function is nonconvex. Numerical results show that the proposed method is efficient.     

A conjugate subgradient algorithm with adaptive preconditioning for the least absolute shrinkage and selection operator minimization

This paper describes a new efficient conjugate subgradient algorithm which minimizes a convex function containing a least squares fidelity term and an absolute value regularization term. This method is successfully applied to the inversion of ill-conditioned linear problems, in particular for computed tomography with the dictionary learning method. A comparison with other state-of-art methods shows a significant reduction of the number of iterations, which makes this algorithm appealing for practical use.     

Total variation-penalized Poisson likelihood estimation for ill-posed problems

The noise contained in data measured by imaging instruments is often primarily of Poisson type. This motivates, in many cases, the use of the Poisson negative-log likelihood function in place of the ubiquitous least squares data fidelity when solving image deblurring problems. We assume that the underlying blurring operator is compact, so that, as in the least squares case, the resulting minimization problem is ill-posed and must be regularized. In this paper, we focus on total variation regularization and show that the problem of computing the minimizer of the resulting total variation-penalized Poisson likelihood functional is well-posed. We then prove that, as the errors in the data and in the blurring operator tend to zero, the resulting minimizers converge to the minimizer of the exact likelihood function. Finally, the practical effectiveness of the approach is demonstrated on synthetically generated data, and a nonnegatively constrained, projected quasi-Newton method is introduced.