I am working in Matlab trying to solve a wider problem, that led to 2 linear systems \begin{equation} A_1 x = b_1^0 \end{equation} \begin{equation} A_2 x = b_2^0 \end{equation} The matrices and vectors have specific numerical values which I am not giving here since they're very large, with dimensions $A_1,A_2\in\mathbb{R}^{373\times41}, b_1,b_2\in\mathbb{R}^{373}$. The systems have solutions $x_1^0,x_2^0$. Now the right-hand side (RHS) vectors are perturbed to yield $b_1,b_2$ where \begin{equation} \frac{\|b_1-b_1^0\|_2}{\|b_1^0\|_2}=0.0781,\quad \frac{\|b_2-b_2^0\|_2}{\|b_2^0\|_2}=0.0032. \end{equation} When solving the system for these perturbed vectors I get the solutions $x_1,x_2$ that satisfy \begin{equation} \frac{\|x_1-x_1^0\|_2}{\|x_1^0\|_2}=0.0408,\quad \frac{\|x_2-x_2^0\|_2}{\|x_2^0\|_2}=0.0075. \end{equation}
Visually you can notice the conditioning of system 2 is slightly worse than 1. However, when computing the condition numbers of the matrices via the Moore-Penrose pseudoinverse I get \begin{equation} \|A_1\|_2\cdot\|A_1^+\|_2=2.34,\quad \|A_2\|_2\cdot\|A_2^+\|_2=155.4. \end{equation}
So it looks as if system 2 is around 50 times worse conditioned than 1. I know the condition number is just a bound, i.e., \begin{equation} \frac{\|x-x^0\|_2}{\|x^0\|_2}\leq\|A\|_2\cdot\|A^+\|_2\frac{\|b-b^0\|_2}{\|x^0\|_2} \end{equation} but in my case this is an extremely loose bound. I want to get a much tighter bound for the terms above than given by the conditioning, that may be able to help me predict how the solution error changes with the errors in vectors b. Any help or hints are greatly appreciated!
(too long for a comment).
What seems me the most rational approach.
Let us consider a system $Ax=b$, $A \in \mathbb{R}^{373 \times 41}$, $b$ a column vector with entries $b_k$ and $\overline{x}$ the least square solution, its entries being denoted $\overline{x}_k.$
Let $(R_k)^T$ ($k=1 \cdots 373$) be the rows (which are line vectors) of matrix $A$.
Caveat : are these rows more or less normalized (ideally their norms should be all the same) ? If not, it may be a source of problems ; indeed, the more "heavy" the entries of a line are (wrt to others), the more the degree of "attraction" of this line. This should be avoided.
Assuming this normalization done (prior to the determination of lest square solution $\overline{x}$) :
Let $D_k$ be the discrepancy between LHS and RHS at the level of the $k$th row :
$$D_k=\underbrace{(R_k)^T \overline{x}}_{\in \mathbb{R}}-x_k$$
Sort the absolute values of the $|D_k|$s by increasing value and keep track of their resp. index ; keep the first $41$ "winning" equations (i.e., with smallest discrepancies) for building a square system $\tilde{A}x=\tilde{b}$ whose solution $\tilde{x}$ shouldn't be far from the initial least squares solution $\overline{x}$.