A Partial Condition Number for Linear Least Squares Problems

• Published in: SIAM journal on matrix analysis and applications 2007-01, Vol.29 (2), p.413-433
• Main Authors: Arioli, Mario, Baboulin, Marc, Gratton, Serge
• Format: Article
• Language: English
• Subjects: Linear algebra; Mathematics; Norms; Parameter estimation; Statistical analysis
• ISSN: 0895-4798; 1095-7162
• DOI: 10.1137/050643088

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$.