New bounds on the condition number of the Hessian of the preconditioned variational data assimilation problem

Data assimilation algorithms combine prior and observational information, weighted by their respective uncertainties, to obtain the most likely posterior of a dynamical system. In variational data assimilation the posterior is computed by solving a nonlinear least squares problem. Many numerical weather prediction (NWP) centers use full observation error covariance (OEC) weighting matrices, which can slow convergence of the data assimilation procedure. Previous work revealed the importance of the minimum eigenvalue of the OEC matrix for conditioning and convergence of the unpreconditioned data assimilation problem. In this article we examine the use of correlated OEC matrices in the preconditioned data assimilation problem for the first time. We consider the case where there are more state variables than observations, which is typical for applications with sparse measurements, for example, NWP and remote sensing. We find that similarly to the unpreconditioned problem, the minimum eigenvalue of the OEC matrix appears in new bounds on the condition number of the Hessian of the preconditioned objective function. Numerical experiments reveal that the condition number of the Hessian is minimized when the background and observation lengthscales are equal. This contrasts with the unpreconditioned case, where decreasing the observation error lengthscale always improves conditioning. Conjugate gradient experiments show that in this framework the condition number of the Hessian is a good proxy for convergence. Eigenvalue clustering explains cases where convergence is faster than expected.     

Computing the conditioning of the components of a linear least‐squares solution

In this paper, we address the accuracy of the results for the overdetermined full rank linear least‐squares problem. We recall theoretical results obtained in (SIAM J. Matrix Anal. Appl. 2007; 29 (2):413–433) on conditioning of the least‐squares solution and the components of the solution when the matrix perturbations are measured in Frobenius or spectral norms. Then we define computable estimates for these condition numbers and we interpret them in terms of statistical quantities when the regression matrix and the right‐hand side are perturbed. In particular, we show that in the classical linear statistical model, the ratio of the variance of one component of the solution by the variance of the right‐hand side is exactly the condition number of this solution component when only perturbations on the right‐hand side are considered. We explain how to compute the variance–covariance matrix and the least‐squares conditioning using the libraries LAPACK (LAPACK Users' Guide (3rd edn). SIAM: Philadelphia, 1999) and ScaLAPACK (ScaLAPACK Users' Guide. SIAM: Philadelphia, 1997) and we give the corresponding computational cost. Finally we present a small historical numerical example that was used by Laplace (Théorie Analytique des Probabilités. Mme Ve Courcier, 1820; 497–530) for computing the mass of Jupiter and a physical application if the area of space geodesy. Copyright © 2008 John Wiley & Sons, Ltd.     

Second-order nonlinear least squares estimation

The ordinary least squares estimation is based on minimization of the squared distance of the response variable to its conditional mean given the predictor variable. We extend this method by including in the criterion function the distance of the squared response variable to its second conditional moment. It is shown that this “second-order” least squares estimator is asymptotically more efficient than the ordinary least squares estimator if the third moment of the random error is nonzero, and both estimators have the same asymptotic covariance matrix if the error distribution is symmetric. Simulation studies show that the variance reduction of the new estimator can be as high as 50% for sample sizes lower than 100. As a by-product, the joint asymptotic covariance matrix of the ordinary least squares estimators for the regression parameter and for the random error variance is also derived, which is only available in the literature for very special cases, e.g. that random error has a normal distribution. The results apply to both linear and nonlinear regression models, where the random error distributions are not necessarily known.     

Geometry of interpolation sets in derivative free optimization

We consider derivative free methods based on sampling approaches for nonlinear optimization problems where derivatives of the objective function are not available and cannot be directly approximated. We show how the bounds on the error between an interpolating polynomial and the true function can be used in the convergence theory of derivative free sampling methods. These bounds involve a constant that reflects the quality of the interpolation set. The main task of such a derivative free algorithm is to maintain an interpolation sampling set so that this constant remains small, and at least uniformly bounded. This constant is often described through the basis of Lagrange polynomials associated with the interpolation set. We provide an alternative, more intuitive, definition for this concept and show how this constant is related to the condition number of a certain matrix. This relation enables us to provide a range of algorithms whilst maintaining the interpolation set so that this condition number or the geometry constant remain uniformly bounded. We also derive bounds on the error between the model and the function and between their derivatives, directly in terms of this condition number and of this geometry constant.     

Quadratic and Superlinear Convergence of the Huschens Method for Nonlinear Least Squares Problems

This paper is concerned with quadratic and superlinear convergence of structured quasi-Newton methods for solving nonlinear least squares problems. These methods make use of a special structure of the Hessian matrix of the objective function. Recently, Huschens proposed a new kind of structured quasi-Newton methods and dealt with the convex class of the structured Broyden family, and showed its quadratic and superlinear convergence properties for zero and nonzero residual problems, respectively. In this paper, we extend the results by Huschens to a wider class of the structured Broyden family. We prove local convergence properties of the method in a way different from the proof by Huschens.     

A Trust Region Method for Optimization Problem with Singular Solutions

In this paper, we propose a trust region method for minimizing a function whose Hessian matrix at the solutions may be singular. The global convergence of the method is obtained under mild conditions. Moreover, we show that if the objective function is LC ² function, the method possesses local superlinear convergence under the local error bound condition without the requirement of isolated nonsingular solution. This is the first regularized Newton method with trust region technique which possesses local superlinear (quadratic) convergence without the assumption that the Hessian of the objective function at the solution is nonsingular. Preliminary numerical experiments show the efficiency of the method. This work is partly supported by the National Natural Science Foundation of China (Grant Nos. 70302003, 10571106, 60503004, 70671100) and Science Foundation of Beijing Jiaotong University (2007RC014).     

纵向数据半参数回归模型的估计方法

本文考虑纵向数据半参数回归模型,通过考虑纵向数据的协方差结构,基于Profile最小二乘法和局部线性拟合的方法建立了模型中参数分量、回归函数和误差方差的估计量,来提高估计的有效性,在适当条件下给出了这些估计量的相合性.并通过模拟研究将该方法与最小二乘局部线性拟合估计方法进行了比较,表明了Profile最小二乘局部线性拟合方法在有限样本情况下具有良好的性质.     

A condition analysis of the weighted linear least squares problem using dual norms

In this paper, based on the theory of adjoint operators and dual norms, we define condition numbers for a linear solution function of the weighted linear least squares problem. The explicit expressions of the normwise and componentwise condition numbers derived in this paper can be computed at low cost when the dimension of the linear function is low due to dual operator theory. Moreover, we use the augmented system to perform a componentwise perturbation analysis of the solution and residual of the weighted linear least squares problems. We also propose two efficient condition number estimators. Our numerical experiments demonstrate that our condition numbers give accurate perturbation bounds and can reveal the conditioning of individual components of the solution. Our condition number estimators are accurate as well as efficient.     

Regularized Newton Methods for Convex Minimization Problems with Singular Solutions

This paper studies convergence properties of regularized Newton methods for minimizing a convex function whose Hessian matrix may be singular everywhere. We show that if the objective function is LC², then the methods possess local quadratic convergence under a local error bound condition without the requirement of isolated nonsingular solutions. By using a backtracking line search, we globalize an inexact regularized Newton method. We show that the unit stepsize is accepted eventually. Limited numerical experiments are presented, which show the practical advantage of the method.     

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.

     

非线性最小二乘问题收敛性的证明

主要讨论了无约束最优化中非线性最小二乘问题的收敛性.侧重于收敛的速率和整体、局部分析.改变了Gauss—Newton方法收敛性定理的条件,分两种情况证明了:(1)目标函数的海赛矩阵正定(函数严格凸)时为强整体二阶收敛;(2)目标函数不保证严格凸性,但海赛矩阵的逆存在时为局部收敛,敛速仍为二阶,同时给出了J(X)~(-1)和Q(X)~(-1)之间存在、有界性的等价条件.     

The use of forecast gradients in 3DVar data assimilation

In this paper, we propose an optimization approach for data assimilation by the use of forecast gradients. The proposed objective function consists of two data-fitting terms. The first term is based on the difference between the gradients of the forecast and the analysis, and the second term is based on the difference between the observations and the analysis in observation space. The motivation for using forecast gradients is that the forecast values provide an estimation of the system state, but they may not be accurate enough. We therefore propose to construct analysis gradients driven by the forecast gradients, instead of the forecast values. The associated data-fitting term can be interpreted by using the second-order finite difference matrix as the inverse of the background error covariance matrix in the 3DVar setting. In the proposed approach, it is not necessary to estimate the background covariance matrix and to deal with its inverse in the 3DVar algorithm. The existence and uniqueness of the analysis solution of the proposed objective function are established in this paper. The solution can be calculated by using the conjugate gradient method iteratively. Experimental results based on Community Multiscale Air Quality (CMAQ) and Weather Research and Forecasting (WRF) simulations are presented. We show in our air quality data assimilation experiment that the performance of the proposed method is better than that of the 3DVar method and the En3DVar method. The average improvements over the CMAQ simulation results for single-species NO₂, O₃, SO₂, NO, and CO are 18.9%, 34.0%, 22.2%, 4.3%, and 91.9%, respectively; and for the multiple-species PM2.5 and PM10, the improvements are 61.2% and 70.1%, respectively. In addition, the performance of the proposed method in temperature data assimilation is improved by 45.1% compared with the 3DVar method.     

Improving estimated sufficient summary plots in dimension reduction using minimization criteria based on initial estimates

In this paper we show that estimated sufficient summary plots can be greatly improved when the dimension reduction estimates are adjusted according to minimization of an objective function. The dimension reduction methods primarily considered are ordinary least squares, sliced inverse regression, sliced average variance Estimates and principal Hessian directions. Some consideration to minimum average variance estimation is also given. Simulations support the usefulness of the approach and three data sets are considered with an emphasis on two- and three-dimensional estimated sufficient summary plots.     

A CLASS OF FACTORIZED QUASI-NEWTON METHODS FOR NONLINEAR LEAST SQUARES PROBLEMS

1.IntroductionThispaPerdealswiththeproblemofndniedingasumofsquaresofnonlinearfuntions-mwhereri(x),i==1,2,',maretwicecontinuouslyfferentiable,m2n'r(x)=(rl(x),rz(x),'jbe(x))"and"T"denotestranspose.NoIilinearleastSquaresproblemisakindofAnportan0ptiedationprobletnsandisaPpearedinmanyfield8suchasscientilicexperiments,mbomumlikelihoodestimation,solutionofnonlinearequaions'patternrecoghtionandetc.ThederiVativesofthefUnctionj(x)aregivenbywhereAEppxnistheJacobianmatrisofr(x)anditselementsare~=f…     

Inexact proximal Newton methods for self-concordant functions

We analyze the proximal Newton method for minimizing a sum of a self-concordant function and a convex function with an inexpensive proximal operator. We present new results on the global and local convergence of the method when inexact search directions are used. The method is illustrated with an application to L1-regularized covariance selection, in which prior constraints on the sparsity pattern of the inverse covariance matrix are imposed. In the numerical experiments the proximal Newton steps are computed by an accelerated proximal gradient method, and multifrontal algorithms for positive definite matrices with chordal sparsity patterns are used to evaluate gradients and matrix-vector products with the Hessian of the smooth component of the objective.     

A Generalization of Rao's Covariance Structure with Applications to Several Linear Models

This paper presents a generalization of Rao's covariance structure. In a general linear regression model, we classify the error covariance structure into several categories and investigate the efficiency of the ordinary least squares estimator (OLSE) relative to the Gauss–Markov estimator (GME). The classification criterion considered here is the rank of the covariance matrix of the difference between the OLSE and the GME. Hence our classification includes Rao's covariance structure. The results are applied to models with special structures: a general multivariate analysis of variance model, a seemingly unrelated regression model, and a serial correlation model.     

On condition numbers for Moore–Penrose inverse and linear least squares problem involving Kronecker products

In this paper, we investigate the normwise, mixed, and componentwise condition numbers and their upper bounds for the Moore–Penrose inverse of the Kronecker product and more general matrix function compositions involving Kronecker products. We also present the condition numbers and their upper bounds for the associated Kronecker product linear least squares solution with full column rank. In practice, the derived upper bounds for the mixed and componentwise condition numbers for Kronecker product linear least squares solution can be efficiently estimated using the Hager–Higham Algorithm. Copyright © 2012 John Wiley & Sons, Ltd.     

Nonlinear conjugate gradient methods with structured secant condition for nonlinear least squares problems

In this paper, we deal with conjugate gradient methods for solving nonlinear least squares problems. Several Newton-like methods have been studied for solving nonlinear least squares problems, which include the Gauss-Newton method, the Levenberg-Marquardt method and the structured quasi-Newton methods. On the other hand, conjugate gradient methods are appealing for general large-scale nonlinear optimization problems. By combining the structured secant condition and the idea of Dai and Liao (2001) [20], the present paper proposes conjugate gradient methods that make use of the structure of the Hessian of the objective function of nonlinear least squares problems. The proposed methods are shown to be globally convergent under some assumptions. Finally, some numerical results are given.     

Iterative refinement for constrained and weighted linear least squares

We present an algorithm for mixed precision iterative refinement on the constrained and weighted linear least squares problem, the CWLSQ problem. The approximate solution is obtained by solving the CWLSQ problem with the weightedQR factorization [6]. With backward errors for the weightedQR decomposition together with perturbation bounds for the CWLSQ problem we analyze the convergence behaviour of the iterative refinement procedure.In the unweighted case the initial convergence rate of the error of the iteratively refined solution is determined essentially by the condition number. For the CWLSQ problem the initial convergence behaviour is more complicated. The analysis shows that the initial convergence is dependent both on the condition of the problem related to the solution,x, and the vector =Wr, whereW is the weight matrix andr is the residual.We test our algorithm on two examples where the solution is known and the condition number of the problem can be varied. The computational test confirms the theoretical results and verifies that mixed precision iterative refinement, using the system matrix and the weightedQR decomposition, is an effective way of improving an approximate solution to the CWLSQ problem.     

An Inversion-Free Estimating Equations Approach for Gaussian Process Models

One of the scalability bottlenecks for the large-scale usage of Gaussian processes is the computation of the maximum likelihood estimates of the parameters of the covariance matrix. The classical approach requires a Cholesky factorization of the dense covariance matrix for each optimization iteration. In this work, we present an estimating equations approach for the parameters of zero-mean Gaussian processes. The distinguishing feature of this approach is that no linear system needs to be solved with the covariance matrix. Our approach requires solving an optimization problem for which the main computational expense for the calculation of its objective and gradient is the evaluation of traces of products of the covariance matrix with itself and with its derivatives. For many problems, this is an O(nlog?n) effort, and it is always no larger than O(n²). We prove that when the covariance matrix has a bounded condition number, our approach has the same convergence rate as does maximum likelihood in that the Godambe information matrix of the resulting estimator is at least as large as a fixed fraction of the Fisher information matrix. We demonstrate the effectiveness of the proposed approach on two synthetic examples, one of which involves more than 1 million data points.