Given $m \geq n$, a matrix $A \in {\Bbb R}^{m \times n}$ and its SVD, and vector $x \in {\Bbb R}^n$, is there a computationally efficient way to accurately estimate the condition number of the matrix $B$ constructed by appending $x$ as an additional row to $A$, e.g., without computing the SVD of $B$, etc.? For example, projecting $x$ into the effective right null space of $A$?
This is needed in an application where a list of several vectors $x_i$ are given as candidates to extend the matrix $A$ in such a way that the condition number of $B$ is smaller than the condition number of $A$.
My question is related, but not equivalent, to the inverse of the Subset Selection problem (See Golub & Van Loan, Matrix Computations, 3rd ed., pp 590-595). In other words, I would like to take an existing matrix and candidate rows, and constructively build the "best" well-conditioned (albeit over-determined) matrix from these rows, rather than remove them.
For a simple example, consider the matrix
$A=\left(\begin{array}{ccc} 1 & 0 & 0\\ 0 & 0.5 & 0\\ 0 & 0 & 0.01 \end{array}\right)$
(with condition number $\kappa \left(A\right)=100$) and the candidate vectors
$x_{1}=\left(\begin{array}{ccc} 0 & 1 & 0.1\end{array}\right)$,
$x_{2}=\left(\begin{array}{ccc}0 & 0.1 & 0.05\end{array}\right)$
Extending $A$ by adding $x_1$ as an extra row produces a matrix, $B_1$, with condition number $\kappa \left(B_1\right)\approx 24.55$, whereas extending $A$ by $x_2$ produces a matrix, $B_2$, with condition number $\kappa \left(B_2\right)\approx 19.99$. Is there a computationally inexpensive way to determine $x_2$ is the better choice?
