Estimation of the L-Curve via Lanczos Bidiagonalization

The L-curve criterion is often applied to determine a suitable value of the regularization parameter when solving ill-conditioned linear systems of equations with a right-hand side contaminated by errors of unknown norm. However, the computation of the L-curve is quite costly for large problems; the determination of a point on the L-curve requires that both the norm of the regularized approximate solution and the norm of the corresponding residual vector be available. Therefore, usually only a few points on the L-curve are computed and these values, rather than the L-curve, are used to determine a value of the regularization parameter. We propose a new approach to determine a value of the regularization parameter based on computing an L-ribbon that contains the L-curve in its interior. An L-ribbon can be computed fairly inexpensively by partial Lanczos bidiagonalization of the matrix of the given linear system of equations. A suitable value of the regularization parameter is then determined from the L-ribbon, and we show that an associated approximate solution of the linear system can be computed with little additional work.     

L-曲线估计确定正则参数的双网格迭代法

本文考虑对不适定问题离散化得到的大规模不适定线性方程组进行Tiknonov正则化,然后用双网格迭代法求解得到的Tikhonov正则化方程组,并用L-曲线估计法来确定正则参数.试验问题的数值结果表明双网格迭代法求解正则化后的对称正定线性方程组效果很好,且L-曲线估计法确定正则参数计算量很小.     

Regularization of Ill-Posed Problems by Envelope Guided Conjugate Gradients

Abstract

We propose a new way to iteratively solve large scale ill-posed problems by exploiting the relation between Tikhonov regularization and multiobjective optimization to obtain, iteratively, approximations to the Tikhonov L-curve and its corner. Monitoring the change of the approximate L-curves allows us to adjust the regularization parameter adaptively during a preconditioned conjugate gradient iteration, so that the desired solution can be reconstructed with a low number of iterations. We apply the technique to an idealized image reconstruction problem in positron emission tomography.     

Limitations of the L-curve method in ill-posed problems

This paper considers the Tikhonov regularization method with the regularization parameter chosen by the so-called L-curve criterion. An infinite dimensional example is constructed for which the selected regularization parameter vanishes too rapidly as the noise to signal ratio in the data goes to zero. As a consequence the computed reconstructions do not converge to the true solution. Numerical examples are given to show that similar phenomena can be observed under more general assumptions in discrete ill-posed problems provided the exact solution of the problem is smooth.This work was partially supported by NATO grant CRG 930044.     

An adaptive pruning algorithm for the discrete L-curve criterion

We describe a robust and adaptive implementation of the L-curve criterion. The algorithm locates the corner of a discrete L-curve which is a log–log plot of corresponding residual norms and solution norms of regularized solutions from a method with a discrete regularization parameter (such as truncated SVD or regularizing CG iterations). Our algorithm needs no predefined parameters, and in order to capture the global features of the curve in an adaptive fashion, we use a sequence of pruned L-curves that correspond to considering the curves at different scales. We compare our new algorithm to existing algorithms and demonstrate its robustness by numerical examples.     

求解病态问题的一种改进的Tikhonov正则化--(1)正则化方法的建立

对于带有右端扰动数据的第一类紧算子方程的病态问题 ,本文应用正则化子建立了一类新的正则化求解方法 ,称之为改进的Tikonov正则化 ;通过适当选取正则参数 ,证明了正则解具有最优的渐近收敛阶 .与通常的Tikhonov正则化相比 ,这种改进的正则化可使正则解取到足够高的最优渐近阶     

Fixed-point iterations in determining a Tikhonov regularization parameter in Kirsch’s factorization method

Kirsch’s factorization method is a fast inversion technique for visualizing the profile of a scatterer from measurements of the far-field pattern. The mathematical basis of this method is given by the far-field equation, which is a Fredholm integral equation of the first kind in which the data function is a known analytic function and the integral kernel is the measured (and therefore noisy) far-field pattern. We present a Tikhonov parameter choice approach based on a fast fixed-point iteration method which constructs a regularization parameter associated with the corner of the L-curve in log-log scale. The performance of the method is evaluated by comparing our reconstructions with those obtained via the L-curve and we conclude that our method yields reliable reconstructions at a lower computational cost.     

Tikhonov Regularization of Large Linear Problems

Many numerical methods for the solution of linear ill-posed problems apply Tikhonov regularization. This paper presents a new numerical method, based on Lanczos bidiagonalization and Gauss quadrature, for Tikhonov regularization of large-scale problems. An estimate of the norm of the error in the data is assumed to be available. This allows the value of the regularization parameter to be determined by the discrepancy principle.     

An L-ribbon for large underdetermined linear discrete ill-posed problems

The L-curve is a popular aid for determining a suitable value of the regularization parameter when solving ill-conditioned linear systems of equations with a right-hand side vector, which is contaminated by errors of unknown size. However, for large problems, the computation of the L-curve can be quite expensive, because the determination of a point on the L-curve requires that both the norm of the regularized approximate solution and the norm of the corresponding residual vector be available. Recently, an approximation of the L-curve, referred to as the L-ribbon, was introduced to address this difficulty. The present paper discusses how to organize the computation of the L-ribbon when the matrix of the linear system of equations has many more columns than rows. Numerical examples include an application to computerized tomography.     

基于奇异值分解建立的一种新的正则化方法

根据紧算子的奇异系统理论，引入一种正则化滤子函数，从而建立一种新的正则化方法来求解右端近似给定的第一类算子方程，并给出了正则解的误差分析。通过正则参数的先验选取，证明了正则解的误差具有渐进最优阶。      

Regularization Using QR Factorization and the Estimation of the Optimal Parameter

In this paper we propose a direct regularization method using QR factorization for solving linear discrete ill-posed problems. The decomposition of the coefficient matrix requires less computational cost than the singular value decomposition which is usually used for Tikhonov regularization. This method requires a parameter which is similar to the regularization parameter of Tikhonov's method. In order to estimate the optimal parameter, we apply three well-known parameter choice methods for Tikhonov regularization.This revised version was published online in October 2005 with corrections to the Cover Date.     

Old and new parameter choice rules for discrete ill-posed problems

Linear discrete ill-posed problems are difficult to solve numerically because their solution is very sensitive to perturbations, which may stem from errors in the data and from round-off errors introduced during the solution process. The computation of a meaningful approximate solution requires that the given problem be replaced by a nearby problem that is less sensitive to disturbances. This replacement is known as regularization. A regularization parameter determines how much the regularized problem differs from the original one. The proper choice of this parameter is important for the quality of the computed solution. This paper studies the performance of known and new approaches to choosing a suitable value of the regularization parameter for the truncated singular value decomposition method and for the LSQR iterative Krylov subspace method in the situation when no accurate estimate of the norm of the error in the data is available. The regularization parameter choice rules considered include several L-curve methods, Regińska’s method and a modification thereof, extrapolation methods, the quasi-optimality criterion, rules designed for use with LSQR, as well as hybrid methods.     

Large-scale Tikhonov regularization via reduction by orthogonal projection

This paper presents a new approach to computing an approximate solution of Tikhonov-regularized large-scale ill-posed least-squares problems with a general regularization matrix. The iterative method applies a sequence of projections onto generalized Krylov subspaces. A suitable value of the regularization parameter is determined by the discrepancy principle.     

A “Nonconvex+Nonconvex” approach for image restoration with impulse noise removal

In this paper, we propose a new method for image restoration problems, which are degraded by impulsive noise, with nonconvex data fitting term and nonconvex regularizer.The proposed method possesses the advantages of nonconvex data fitting and nonconvex regularizer simultaneously, namely, robustness for impulsive noise and efficiency for restoring neat edge images.Further, we propose an efficient algorithm to solve the “Nonconvex+Nonconvex” structure problem via using the alternating direction minimization, and prove that the algorithm is globally convergent when the regularization parameter is known. However, the regularization parameter is unavailable in general. Thereby, we combine the algorithm with the continuation technique and modified Morozov’s discrepancy principle to get an improved algorithm in which a suitable regularization parameter can be chosen automatically. The experiments reveal the superior performances of the proposed algorithm in comparison with some existing methods.     

A novel regularization method and application to load identification of composite laminated cylindrical shell

In this paper, a novel regularization method (MRO) is suggested to identify the multi-source dynamic loads on a surface of composite laminated cylindrical shell. Regularization methods can solve the di±culty of the solution of ill-conditioned inverse problems by the approximation of a family of neighbouring well-posed problems. Based on the construction of a new regularization operator, corresponding regularization method is established. We prove the stability of the proposed method according to suitable parameter choice strategy that leads to optimal convergence rate toward the minimalnorm and least square solution of an ill-posed linear operator equation in the presence of noisy data. Furthermore, numerical simulations show that the multi-source dynamic loads on a surface of composite laminated cylindrical shell are successfully identi¯ed, and demonstrate the e®ectiveness and robustness of the present method.     

GCV for Tikhonov regularization via global Golub–Kahan decomposition

Generalized cross validation is a popular approach to determining the regularization parameter in Tikhonov regularization. The regularization parameter is chosen by minimizing an expression, which is easy to evaluate for small‐scale problems, but prohibitively expensive to compute for large‐scale ones. This paper describes a novel method, based on Gauss‐type quadrature, for determining upper and lower bounds for the desired expression. These bounds are used to determine the regularization parameter for large‐scale problems. Computed examples illustrate the performance of the proposed method and demonstrate its competitiveness. Copyright © 2016 John Wiley & Sons, Ltd.     

Choice of Regularization Parameter in Adaptive Filtering Problems

Computational Mathematics and Mathematical Physics - The paper proposes a new method for choosing a regularization parameter when solving an integral equation of convolution type in problems of...     

Two-Dimensional Solution Surface for Weighted Support Vector Machines

The support vector machine (SVM) is a popular learning method for binary classification. Standard SVMs treat all the data points equally, but in some practical problems it is more natural to assign different weights to observations from different classes. This leads to a broader class of learning, the so-called weighted SVMs (WSVMs), and one of their important applications is to estimate class probabilities besides learning the classification boundary. There are two parameters associated with the WSVM optimization problem: one is the regularization parameter and the other is the weight parameter. In this article, we first establish that the WSVM solutions are jointly piecewise-linear with respect to both the regularization and weight parameter. We then develop a state-of-the-art algorithm that can compute the entire trajectory of the WSVM solutions for every pair of the regularization parameter and the weight parameter at a feasible computational cost. The derived two-dimensional solution surface provides theoretical insight on the behavior of the WSVM solutions. Numerically, the algorithm can greatly facilitate the implementation of the WSVM and automate the selection process of the optimal regularization parameter. We illustrate the new algorithm on various examples. This article has online supplementary materials.     

Updating the regularization parameter in the adaptive cubic regularization algorithm

The adaptive cubic regularization method (Cartis et al. in Math. Program. Ser. A 127(2):245?C295, 2011; Math. Program. Ser. A. 130(2):295?C319, 2011) has been recently proposed for solving unconstrained minimization problems. At each iteration of this method, the objective function is replaced by a cubic approximation which comprises an adaptive regularization parameter whose role is related to the local Lipschitz constant of the objective??s Hessian. We present new updating strategies for this parameter based on interpolation techniques, which improve the overall numerical performance of the algorithm. Numerical experiments on large nonlinear least-squares problems are provided.     

解不适定问题的一种多尺度方法

1 前言 数学物理反问题是应用数学领域中成长和发展最快的领域之一.反问题大多是不适定的.对于不适定问题的解法已有不少的学者进行探索和研究,Tikhonov正则化方法是一种理论上最完备而在实践上行之有效的方法(参见[5,6,7,8,13]).