Solving regularized total least squares problems via a sequence of eigenvalue problems

A computational approach for solving regularized total least squares problems via a sequence of eigenvalue problems has recently been introduced by Renaut and Guo. Combining this approach with thick starts using the nonlinear Arnoldi method lead to a very efficient method for large RTLS problems. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

Regularized Total Least Squares Based on Quadratic Eigenvalue Problem Solvers

This paper presents a new computational approach for solving the Regularized Total Least Squares problem. The problem is formulated by adding a quadratic constraint to the Total Least Square minimization problem. Starting from the fact that a quadratically constrained Least Squares problem can be solved via a quadratic eigenvalue problem, an iterative procedure for solving the regularized Total Least Squares problem based on quadratic eigenvalue problems is presented. Discrete ill-posed problems are used as simulation examples in order to numerically validate the method. AMS subject classification (2000) 65F20, 65F30.Received March 2003. Revised November 2003. Accepted January 2004. Communicated by Per Christian Hansen.     

Preconditioner based on the Sherman-Morrison formula for regularized least squares problems

We propose a sparse approximate inverse preconditioner based on the Sherman-Morrison formula for Tikhonov regularized least square problems. Theoretical analysis shows that, the factorization method can take the advantage of the symmetric property of the coefficient matrix and be implemented cheaply. Combined with dropping rules, the incomplete factorization leads to a preconditioner for Krylov iterative methods to solve regularized least squares problems. Numerical experiments show that our preconditioner is competitive compared to existing methods, especially for ill-conditioned and rank deficient least squares problems.     

Generalizations of Tikhonov’s regularized method of least squares to non-Euclidean vector norms

Tikhonov’s regularized method of least squares and its generalizations to non-Euclidean norms, including polyhedral, are considered. The regularized method of least squares is reduced to mathematical programming problems obtained by “instrumental” generalizations of the Tikhonov lemma on the minimal (in a certain norm) solution of a system of linear algebraic equations with respect to an unknown matrix. Further studies are needed for problems concerning the development of methods and algorithms for solving reduced mathematical programming problems in which the objective functions and admissible domains are constructed using polyhedral vector norms.     

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.     

Efficiently solving total least squares with Tikhonov identical regularization

The Tikhonov identical regularized total least squares (TI) is to deal with the ill-conditioned system of linear equations where the data are contaminated by noise. A standard approach for (TI) is to reformulate it as a problem of finding a zero point of some decreasing concave non-smooth univariate function such that the classical bisection search and Dinkelbach’s method can be applied. In this paper, by exploring the hidden convexity of (TI), we reformulate it as a new problem of finding a zero point of a strictly decreasing, smooth and concave univariate function. This allows us to apply the classical Newton’s method to the reformulated problem, which converges globally to the unique root with an asymptotic quadratic convergence rate. Moreover, in every iteration of Newton’s method, no optimization subproblem such as the extended trust-region subproblem is needed to evaluate the new univariate function value as it has an explicit expression. Promising numerical results based on the new algorithm are reported.     

Computation of the eigenvalues of Sturm-Liouville problems with parameter dependent boundary conditions using the regularized sampling method

The purpose in this paper is to compute the eigenvalues of Sturm-Liouville problems with quite general separated boundary conditions nonlinear in the eigenvalue parameter using the regularized sampling method, an improvement on the method based on Shannon sampling theory, which does not involve any multiple integration and provides higher order estimates of the eigenvalues at a very low cost. A few examples shall be presented to illustrate the power of the method and a comparison made with the the exact eigenvalues obtained as squares of the zeros of the exact characteristic functions.

     

Tikhonov regularization for weighted total least squares problems

In this work, we study and analyze the regularized weighted total least squares (RWTLS) formulation. Our regularization of the weighted total least squares problem is based on the Tikhonov regularization. Numerical examples are presented to demonstrate the effectiveness of the RWTLS method.     

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.     

非线性特征值问题的二次近似方法

本文研究求解非线性特征值问题的数值方法.基于矩阵值函数的二次近似,将非线性特征值问题转化为二次特征值问题,提出了求解非线性特征值问题的逐次二次近似方法,分析了该方法的收敛性.结合求解二次特征值问题的Arnoldi方法和Jacobi-Davidson方法,给出求解非线性特征值问题的一些二次近似方法.数值结果表明本文所给算法是有效的.     

图像处理中全变差正则化数据拟合问题算法回顾

全变差正则化数据拟合问题产生于许多图像处理任务,如图像去噪、去模糊、图像修复、磁共振成像、压缩图像感知等.近年来,求解此类问题的快速高效算法发展很快.以最小二乘、最小一乘等为例简要回顾求解此类问题的主要算法,并讨论一个全变差正则化非凸数据拟合模型在脉冲噪声图像去模糊问题中的应用.     

An interior point Newton‐like method for non‐negative least‐squares problems with degenerate solution

An interior point approach for medium and large non‐negative linear least‐squares problems is proposed. Global and locally quadratic convergence is shown even if a degenerate solution is approached. Viable approaches for implementation are discussed and numerical results are provided. Copyright © 2006 John Wiley & Sons, Ltd.     

Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization

This paper is concerned with the squared F(robenius)-norm regularized factorization form for noisy low-rank matrix recovery problems. Under a suitable assumption on the restricted condition number of the Hessian matrix of the loss function, we establish an error bound to the true matrix for the non-strict critical points with rank not more than that of the true matrix. Then, for the squared F-norm regularized factorized least squares loss function, we establish its KL property of exponent 1/2 on the global optimal solution set under the noisy and full sample setting, and achieve this property at its certain class of critical points under the noisy and partial sample setting. These theoretical findings are also confirmed by solving the squared F-norm regularized factorization problem with an accelerated alternating minimization method.

     

非线性不等式组的光滑近似方法及其收敛性

将非线性不等式组的求解转化成非线性最小二乘问题,利用引入的光滑辅助函数,构造新的极小化问题来逐次逼近最小二乘问题.在一定的条件下,文中所提出的光滑高斯-牛顿算法的全局收敛性得到保证.适当条件下,算法的局部二阶收敛性得到了证明.文后的数值试验表明本文算法有效.     

Determining surface temperature and heat flux by a wavelet dual least squares method

We apply a wavelet dual least squares method to a general sideways parabolic equation for determining surface temperature and surface heat flux. Connecting Meyer wavelet bases with a special project method dual least squares method, we can obtain a regularized solution. Meanwhile, order optimal error estimates between the approximate solution and exact solution are proved.     

Proximal methods for the latent group lasso penalty

We consider a regularized least squares problem, with regularization by structured sparsity-inducing norms, which extend the usual ? ₁ and the group lasso penalty, by allowing the subsets to overlap. Such regularizations lead to nonsmooth problems that are difficult to optimize, and we propose in this paper a suitable version of an accelerated proximal method to solve them. We prove convergence of a nested procedure, obtained composing an accelerated proximal method with an inner algorithm for computing the proximity operator. By exploiting the geometrical properties of the penalty, we devise a new active set strategy, thanks to which the inner iteration is relatively fast, thus guaranteeing good computational performances of the overall algorithm. Our approach allows to deal with high dimensional problems without pre-processing for dimensionality reduction, leading to better computational and prediction performances with respect to the state-of-the art methods, as shown empirically both on toy and real data.     

On the quadratic two-parameter eigenvalue problem and its linearization

We introduce the quadratic two-parameter eigenvalue problem and linearize it as a singular two-parameter eigenvalue problem. This, together with an example from model updating, shows the need for numerical methods for singular two-parameter eigenvalue problems and for a better understanding of such problems.There are various numerical methods for two-parameter eigenvalue problems, but only few for nonsingular ones. We present a method that can be applied to singular two-parameter eigenvalue problems including the linearization of the quadratic two-parameter eigenvalue problem. It is based on the staircase algorithm for the extraction of the common regular part of two singular matrix pencils.     

Regularized Lagrangian duality for linearly constrained quadratic optimization and trust-region problems

In this paper we first establish a Lagrange multiplier condition characterizing a regularized Lagrangian duality for quadratic minimization problems with finitely many linear equality and quadratic inequality constraints, where the linear constraints are not relaxed in the regularized Lagrangian dual. In particular, in the case of a quadratic optimization problem with a single quadratic inequality constraint such as the linearly constrained trust-region problems, we show that the Slater constraint qualification (SCQ) is necessary and sufficient for the regularized Lagrangian duality in the sense that the regularized duality holds for each quadratic objective function over the constraints if and only if (SCQ) holds. A new theorem of the alternative for systems involving both equality constraints and two quadratic inequality constraints plays a key role. We also provide classes of quadratic programs, including a class of CDT-subproblems with linear equality constraints, where (SCQ) ensures regularized Lagrangian duality.     

Truncated regularized Newton method for convex minimizations

Recently, Li et al. (Comput. Optim. Appl. 26:131–147, 2004) proposed a regularized Newton method for convex minimization problems. The method retains local quadratic convergence property without requirement of the singularity of the Hessian. In this paper, we develop a truncated regularized Newton method and show its global convergence. We also establish a local quadratic convergence theorem for the truncated method under the same conditions as those in Li et al. (Comput. Optim. Appl. 26:131–147, 2004). At last, we test the proposed method through numerical experiments and compare its performance with the regularized Newton method. The results show that the truncated method outperforms the regularized Newton method. The work was supported by the 973 project granted 2004CB719402 and the NSF project of China granted 10471036.