Backward Error Bounds for Constrained Least Squares Problems

We derive an upper bound on the normwise backward error of an approximate solution to the equality constrained least squares problem min _Bx=d b – Ax₂. Instead of minimizing over the four perturbations to A, b, B and d, we fix those to B and d and minimize over the remaining two; we obtain an explicit solution of this simplified minimization problem. Our experiments show that backward error bounds of practical use are obtained when B and d are chosen as the optimal normwise relative backward perturbations to the constraint system, and we find that when the bounds are weak they can be improved by direct search optimization. We also derive upper and lower backward error bounds for the problem of least squares minimization over a sphere: .     

Optimal Backward Perturbation Bounds for the LSS Problem

A computable expression is given for the backward error of an approximate solution to the problem of least squares over a sphere.This revised version was published online in October 2005 with corrections to the Cover Date.     

Implicit Scaling of Linear Least Squares Problems

We consider the solution of weighted linear least squares problems by Householder transformations with implicit scaling, that is, with the weights stored separately. By holding inverse weights, the constrained case can be accommodated. The error analysis of the weighted and unconstrained case is readily extended and we show that iterative refinement may be applied.     

Sparse Linear Least Squares Problems in Optimization

Numerical and computational aspects of direct methods for largeand sparseleast squares problems are considered. After a brief survey of the most oftenused methods, we summarize the important conclusions made from anumerical comparison in matlab. Significantly improved algorithms haveduring the last 10-15 years made sparse QR factorization attractive, andcompetitive to previously recommended alternatives. Of particular importanceis the multifrontal approach, characterized by low fill-in, dense subproblemsand naturally implemented parallelism. We describe a Householder multifrontalscheme and its implementation on sequential and parallel computers. Availablesoftware has in practice a great influence on the choice of numericalalgorithms. Less appropriate algorithms are thus often used solely because ofexisting software packages. We briefly survey softwarepackages for the solution of sparse linear least squares problems. Finally,we focus on various applications from optimization, leading to the solution oflarge and sparse linear least squares problems. In particular, we concentrateon the important case where the coefficient matrix is a fixed general sparsematrix with a variable diagonal matrix below. Inner point methods forconstrained linear least squares problems give, for example, rise to suchsubproblems. Important gains can be made by taking advantage of structure.Closely related is also the choice of numerical method for these subproblems.We discuss why the less accurate normal equations tend to be sufficient inmany applications.     

求解加权线性最小二乘问题的预处理迭代方法

给出了求解一类加权线性最小二乘问题的预处理迭代方法,也就是预处理的广义加速超松弛方法（GAOR）,得到了一些收敛和比较结果．比较结果表明当原来的迭代方法收敛时,预处理迭代方法会比原来的方法具有更好的收敛率．而且,通过数值算例也验证了新预处理迭代方法的有效性．     

On the Convergence of the Generalized Linear Least Squares Algorithm

This paper considers the issue of parameter estimation for biomedical applications using nonuniformly sampled data. The generalized linear least squares (GLLS) algorithm, first introduced by Feng and Ho (1993), is used in the medical imaging community for removal of bias when the data defining the model are correlated. GLLS provides an efficient iterative linear algorithm for the solution of the non linear parameter estimation problem. This paper presents a theoretical discussion of GLLS and introduces use of both Gauss Newton and an alternating Gauss Newton for solution of the parameter estimation problem in nonlinear form. Numerical examples are presented to contrast the algorithms and emphasize aspects of the theoretical discussion. AMS subject classification (2000) 65F10.R. A. Renaut: This work was partially supported by the Arizona Center for Alzheimer’s Disease Research, by NIH grant EB 2553301 and for the second author by NSF CMG-02223.Received December 2003. Revised November 2004. Communicated by Lars Eldén.     

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.     

Linear Least Squares Estimation of Regression Models for Two-Dimensional Random Fields

We consider the problem of estimating regression models of two-dimensional random fields. Asymptotic properties of the least squares estimator of the linear regression coefficients are studied for the case where the disturbance is a homogeneous random field with an absolutely continuous spectral distribution and a positive and piecewise continuous spectral density. We obtain necessary and sufficient conditions on the regression sequences such that a linear estimator of the regression coefficients is asymptotically unbiased and mean square consistent. For such regression sequences the asymptotic covariance matrix of the linear least squares estimator of the regression coefficients is derived.     

Backward perturbation analysis for scaled total least‐squares problems

The scaled total least‐squares (STLS) method unifies the ordinary least‐squares (OLS), the total least‐squares (TLS), and the data least‐squares (DLS) methods. In this paper we perform a backward perturbation analysis of the STLS problem. This also unifies the backward perturbation analyses of the OLS, TLS and DLS problems. We derive an expression for an extended minimal backward error of the STLS problem. This is an asymptotically tight lower bound on the true minimal backward error. If the given approximate solution is close enough to the true STLS solution (as is the goal in practice), then the extended minimal backward error is in fact the minimal backward error. Since the extended minimal backward error is expensive to compute directly, we present a lower bound on it as well as an asymptotic estimate for it, both of which can be computed or estimated more efficiently. Our numerical examples suggest that the lower bound gives good order of magnitude approximations, while the asymptotic estimate is an excellent estimate. We show how to use our results to easily obtain the corresponding results for the OLS and DLS problems in the literature. Copyright © 2009 John Wiley & Sons, Ltd.     

对部分线性模型用惩罚最小二乘估计时最优光滑化的注记

部分线性模型也就是响应变量关于一个或者多个协变量是线性的, 但对于其他的协变量是非线性的关系\bd 对于部分线性模型中的参数和非参数部分的估计方法, 惩罚最小二乘估计是重要的估计方法之一\bd 对于这种估计方法, 广义交叉验证法提供了一种确定光滑参数的方法\bd 但是, 在部分线性模型中, 用广义交叉验证法确定光滑参数的最优性还没有被证明\bd 本文证明了利用惩罚最小二乘估计对于部分线性模型估计时, 用广义交叉验证法选择光滑参数的最优性\bd 通过模拟验证了本文中所提出的用广义交叉验证法选择光滑参数具有很好的效果, 同时, 本文在模拟部分比较了广义交叉验证和最小二乘交叉验证的优劣.     

Perturbation Analysis of Structured Least Squares Problems and Its Application in Calibration of Interest Rate Term Structure

A structured perturbation analysis of the least squares problem is considered in this paper.The new error bound proves to be sharper than that for general perturbations. We apply the new error bound to study sensitivity of changing the knots for curve fitting of interest rate term structure by cubic spline.Numerical experiments are given to illustrate the sharpness of this bound.     

Ill-Conditionedness Need not be Componentwise Near to Ill-Posedness for Least Squares Problems

The condition number of a problem measures the sensitivity of the answer to small changes in the input, where small refers to some distance measure. A problem is called ill-conditioned if the condition number is large, and it is called ill-posed if the condition number is infinity. It is known that for many problems the (normwise) distance to the nearest ill-posed problem is proportional to the reciprocal of the condition number. Recently it has been shown that for linear systems and matrix inversion this is also true for componentwise distances. In this note we show that this is no longer true for least squares problems and other problems involving rectangular matrices. Problems are identified which are arbitrarily ill-conditioned (in a componentwise sense) whereas any componentwise relative perturbation less than 1 cannot produce an ill-posed problem. Bounds are given using additional information on the matrix.     

Perturbation theory for generalized and constrained linear least squares

The perturbation analysis of weighted and constrained rank‐deficient linear least squares is difficult without the use of the augmented system of equations. In this paper a general form of the augmented system is used to get simple perturbation identities and perturbation bounds for the general linear least squares problem both for the full‐rank and rank‐deficient problem. Perturbation identities for the rank‐deficient weighted and constrained case are found as a special case. Interesting perturbation bounds and condition numbers are derived that may be useful when considering the stability of a solution of the rank‐deficient general least squares problem. Copyright © 2000 John Wiley & Sons, Ltd.     

Analysis of the Structured Total Least Squares Problem for Hankel/Toeplitz Matrices

The Structured Total Least Squares (STLS) problem is a natural extension of the Total Least Squares (TLS) approach when structured matrices are involved and a similarly structured rank deficient approximation of that matrix is desired. In many of those cases the STLS approach yields a Maximum Likelihood (ML) estimate as opposed to, e.g., TLS.In this paper we analyze the STLS problem for Hankel matrices (the theory can be extended in a straightforward way to Toeplitz matrices, block Hankel and block Toeplitz matrices). Using a particular parametrisation of rank-deficient Hankel matrices, we show that this STLS problem suffers from multiple local minima, the properties of which depend on the parameters of the new parametrisation. The latter observation makes initial estimates an important issue in STLS problems and a new initialization method is proposed. The new initialization method is applied to a speech compression example and the results confirm the improved performance compared to other previously proposed initialization methods.     

A Hybrid Method for Nonlinear Least Squares Problems

A negative curvature method is applied to nonlinear least squares problems with indefinite Hessian approximation matrices. With the special structure of the method, a new switch is proposed to form a hybrid method. Numerical experiments show that this method is feasible and effective for zero-residual, small-residual and large-residual problems.     

Required Number of Iterations for Sparse Signal Recovery via Orthogonal Least Squares

In countless applications, we need to reconstruct a $K$-sparse signal $\mathbf{x}\in\mathbb{R}^n$ from noisy measurements $\mathbf{y}=\mathbf{\Phi}\mathbf{x}+\mathbf{v}$, where $\mathbf{\Phi}\in\mathbb{R}^{m\times n}$ is a sensing matrix and $\mathbf{v}\in\mathbb{R}^m$ is a noise vector. Orthogonal least squares (OLS), which selects at each step the column that results in the most significant decrease in the residual power, is one of the most popular sparse recovery algorithms. In this paper, we investigate the number of iterations required for recovering $\mathbf{x}$ with the OLS algorithm. We show that OLS provides a stable reconstruction of all $K$-sparse signals $\mathbf{x}$ in $\lceil2.8K\rceil$ iterations provided that $\mathbf{\Phi}$ satisfies the restricted isometry property (RIP). Our result provides a better recovery bound and fewer number of required iterations than those proposed by Foucart in 2013.     

线性流形上矩阵方程B^TXB=D的加权最小二乘对称解和解的最佳逼近

本文利用矩阵的奇异值分解（SVD）,给出了在一流形上矩阵方程B^TXB=D的加权最小二乘对称解的通解表达式,并解决了加权最小二乘对称解的最佳逼近问题。     

矩阵方程ATXA=D的条件数与向后扰动分析

讨论矩阵方程ATXA=D,该方程源于振动反问题和结构模型修正.本文利用Moore-Penrose广义逆的性质,给出该方程解的条件数的上、下界估计.同时,利用Schauder不动点理论给出该方程的向后扰动界,这些结果可用于该矩阵方程的数值计算.     

Iterative Weighted Semiparametric Least Squares Estimation in Repeated Measurement Partially Linear Regression Models

Consider a repeated measurement partially linear regression model with an unknown vector parameter β, an unknown function g(.), and unknown heteroscedastic error variances. In order to improve the semiparametric generalized least squares estimator (SGLSE) of β, we propose an iterative weighted semiparametric least squares estimator (IWSLSE) and show that it improves upon the SGLSE in terms of asymptotic covariance matrix. An adaptive procedure is given to determine the number of iterations. We also show that when the number of replicates is less than or equal to two, the IWSLSE can not improve upon the SGLSE. These results are generalizations of those in [2] to the case of semiparametric regressions.     

Harmonic and Refined Extraction Methods for the Singular Value Problem,with Applications in Least Squares Problems

For the accurate approximation of the minimal singular triple (singular value and left and right singular vector) of a large sparse matrix, we may use two separate search spaces, one for the left, and one for the right singular vector. In Lanczos bidiagonalization, for example, such search spaces are constructed. In SIAM J. Sci. Comput., 23(2) (2002), pp. 606–628, the author proposes a Jacobi–Davidson type method for the singular value problem, where solutions to certain correction equations are used to expand the search spaces. As noted in the mentioned paper, the standard Galerkin subspace extraction works well for the computation of large singular triples, but may lead to unsatisfactory approximations to small and interior triples. To overcome this problem for the smallest triples, we propose three harmonic and a refined approach. All methods are derived in a number of different ways. Some of these methods can also be applied when we are interested in the largest or interior singular triples. Theoretical results as well as numerical experiments indicate that the results of the alternative extraction processes are often better than the standard approach. We show that when Lanczos bidiagonalization is used for the subspace expansion, the standard, harmonic, and refined extraction methods are all essentially equivalent. This gives more insight in the success of Lanczos bidiagonalization to find the smallest singular triples. Finally, we show that the extraction processes for the smallest singular values may give an approximation to a least squares problem at low additional costs. The truncated SVD is also discussed in this context. AMS subject classification (2000) 65F15, 65F50, (65F35, 93E24).Submitted December 2002. Accepted October 2004. Communicated by Haesun Park.M. E. Hochstenbach: The research of this author was supported in part by NSF grant DMS-0405387. Part of this work was done when the author was at Utrecht University.