A Partial Condition Number for Linear Least Squares Problems
Mario Arioli, Marc Baboulin, Serge Gratton · SIAM Journal on Matrix Analysis and Applications · 2007
We consider here the linear least squares problem $\min_{y \in \mathbb{R}^n}\|Ay-b\|_2$, where $b \in \mathbb{R}^m$ and $A \in \mathbb{R}^{m\times 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^Tx$, where $L \in \mathbb{R}^{n\times k}$) for which we provide a sharp estimate that lies within a factor $\sqrt{3}$ of the true condition number. Provided the triangular R factor of A from $A^TA=R^TR$ 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 us 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.