Abstract. We consider here the linear least squares problem min y∈R n Ay − b 2 where b ∈ R m and A ∈ R m×n is a matrix of full column rank n and we denote x its solution. We assume that both A and b can be perturbed and that these perturbations are measured using the Frobenius or the spectral norm for A and the Euclidean norm for b. In this paper, we are concerned with the condition number of a linear function of x (L T x where L ∈ R n×k ) for which we provide a sharp estimate that lies within a factor √ 3 of the true condition number. Provided the triangular R factor of A from A T A = R T R is available, this estimate can be computed in 2kn 2 flops. We also propose a statistical method that estimates the partial condition number by using the exact condition numbers in random orthogonal directions. If R is available, this statistical approach enables to obtain a condition estimate at a lower computational cost. In the case of the Frobenius norm, we derive a closed formula for the partial condition number that is based on the singular values and the right singular vectors of the matrix A. Keywords: Linear least squares, normwise condition number, statistical condition estimate, parameter estimation 1. Introduction. Perturbation theory has been applied to many problems of linear algebra such as linear systems, linear least squares, or eigenvalue problems [1, 4, 11, 18] . In this paper we consider the problem of calculating the quantity L T x, where x is the solution of the linear least squares problem (LLSP) min x∈R n Ax − b 2 where b ∈ R m and A ∈ R m×n is a matrix of full column rank n. This estimation is a fundamental problem of parameter estimation in the framework of the p. 137]. More precisely, we focus here on the evaluation of the sensitivity of L T x to small perturbations of the matrix A and/or the right-hand side b, where L ∈ R n×k and x is the solution of the LLSP. The interest for this question stems for instance from parameter estimation where the parameters of the model can often be divided into two parts : the variables of physical significance and a set of ancillary variables involved in the models. For example, this situation occurs in the determination of positions using the GPS system, where the 3-D coordinates are the quantities of interest but the statistical model involves other parameters such as clock drift and GPS ambiguities [12] that are generally estimated during the solution process. It is then crucial to ensure that the solution components of interest can be computed with satisfactory accuracy. The main goal of this paper is to formalize this problem in terms of a condition number and to describe practical methods to compute or estimate this quantity. Note that as far as the sensitivity of a subset of the solution components is concerned, the matrix L is a projection whose columns consist of vectors of the canonical basis of R n .
REF considered perturbations that are measured in different norms (Frobenius or the spectral norm for A and the Euclidean norm for b ), and derived the condition number for x expressed in the weighted product norms.
A partial condition number for linear least squares problems
SIAM Journal on Matrix Analysis and Applications
Mathematics Computer Science