Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputing the Conditioning of the Components of a Linear Least Squares Solution
113
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 Arioli, Baboulin and Gratton, SIMAX 29(2):413--433, 2007, 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. 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 perturbations on the right-hand side are considered. We also provide fragment codes using LAPACK routines to compute the variance-covariance matrix and the least squares conditioning and we give the corresponding computational cost. Finally we present a small historical numerical example that was used by Laplace in Theorie Analytique des Probabilites, 1820, for computing the mass of Jupiter and experiments from the space industry with real physical data.
rate research
Read More
This paper proposes the capped least squares regression with an adaptive resistance parameter, hence the name, adaptive capped least squares regression. The key observation is, by taking the resistant parameter to be data dependent, the proposed estimator achieves full asymptotic efficiency without losing the resistance property: it achieves the maximum breakdown point asymptotically. Computationally, we formulate the proposed regression problem as a quadratic mixed integer programming problem, which becomes computationally expensive when the sample size gets large. The data-dependent resistant parameter, however, makes the loss function more convex-like for larger-scale problems. This makes a fast randomly initialized gradient descent algorithm possible for global optimization. Numerical examples indicate the superiority of the proposed estimator compared with classical methods. Three data applications to cancer cell lines, stationary background recovery in video surveillance, and blind image inpainting showcase its broad applicability.
We derive closed formulas for the condition number of a linear function of the total least squares solution. Given an over determined linear system Ax=b, we show that this condition number can be computed using the singular values and the right singular vectors of [A,b] and A. We also provide an upper bound that requires the computation of the largest and the smallest singular value of [A,b] and the smallest singular value of A. In numerical examples, we compare these values and the resulting forward error bounds with existing error estimates.
We consider the problem of efficiently solving large-scale linear least squares problems that have one or more linear constraints that must be satisfied exactly. Whilst some classical approaches are theoretically well founded, they can face difficulties when the matrix of constraints contains dense rows or if an algorithmic transformation used in the solution process results in a modified problem that is much denser than the original one. To address this, we propose modifications and new ideas, with an emphasis on requiring the constraints are satisfied with a small residual. We examine combining the null-space method with our recently developed algorithm for computing a null space basis matrix for a ``wide matrix. We further show that a direct elimination approach enhanced by careful pivoting can be effective in transforming the problem to an unconstrained sparse-dense least squares problem that can be solved with existing direct or iterative methods. We also present a number of solution variants that employ an augmented system formulation, which can be attractive when solving a sequence of related problems. Numerical experiments using problems coming from practical applications are used throughout to demonstrate the effectiveness of the different approaches.
This paper is devoted to condition numbers of the total least squares problem with linear equality constraint (TLSE). With novel limit techniques, closed formulae for normwise, mixed and componentwise condition numbers of the TLSE problem are derived. Compact expressions and upper bounds for these condition numbers are also given to avoid the costly Kronecker product-based operations. The results unify the ones for the TLS problem. For TLSE problems with equilibratory input data, numerical experiments illustrate that normwise condition number-based estimate is sharp to evaluate the forward error of the solution, while for sparse and badly scaled matrices, mixed and componentwise condition numbers-based estimations are much tighter.
This paper is devoted to condition numbers of the multidimensional total least squares problem with linear equality constraint (TLSE). Based on the perturbation theory of invariant subspace, the TLSE problem is proved to be equivalent to a multidimensional unconstrained weighed total least squares problem in the limit sense. With a limit technique, Kronecker-product-based formulae for normwise, mixed and componentwise condition numbers of the minimum Frobenius norm TLSE solution are given. Compact upper bounds of these condition numbers are provided to reduce the storage and computation cost. All expressions and upper bounds of these condition numbers unify the ones for the single-dimensional TLSE problem and multidimensional total least squares problem. Some numerical experiments are performed to illustrate our results.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
