Criterion of removal of equations from overdetermined system

[lena]

Consider the problem of solving overdetermined system
Ax = b;

In the problem I am trying to solve (from the field of spectral unmixing) number of unknowns usually varies between N = 2 and 5 and the matrix A is typically 10 by N. However, now the choice of matrix A is fully user-dependent. (For information, it is a so called molar absorption matrix, which is populated with the absorption spectra with N columns corresponding to individual
absorbers and M rows corresponding to the optical wavelengths. Typical example of such matrix would be hemoglobin absorption spectra http://www.surgicalneurologyint.com/viewimage.asp?img=SurgNeurolInt_2010_1_1_75_73316_u2.jpg )

I envision some algorithm where I could decide which row of this matrix can be excluded and the system can still be solved.

Do you know if there is any criterion which tells me that removal of one row is less critical than removal of another for accuracy of solution?

Thank you!
Elena

 

[Greg Bernhardt]

I'm sorry you are not generating any responses at the moment. Is there any additional information you can share with us? Any new findings?

 

[Mark44]

The only thing that comes to my mind is Gauss-Jordan elimination. If you have a 10 X 5 matrix, and use G-J to put the matrix in echelon form, if there are 5 nonzero rows, you will have a unique solution.

 

[lena]

Thanks for response, Mark44.
I hope it is applicable to the matrix A only, not augmented with the right-hand side A|b, because the ultimate goal of what I am trying to do is to avoid acquiring additional/excessive measurements in b.

What I recently read is that the minimal singular value of matrix A can be used as "indicator of stability" and when the smallest singular value is close to zero, matrix A becomes "unstable" and can loose rank. So the row whose removal results in the largest singular value (compared to removal of others) is the least-critical row and can be excluded.

Can anybody explain this criterion? why there is this interdependence between singular value and relevance of a particular row? and back to my initial post-perhaps there exist other mathematical criteria that have the same purpose?
Thanks!

 

[Mark44]

Yes, the vector b plays a role in whether there are solutions or not. Here's a simple example.
x + y = 2
x - y = 0
2x = 2

In augmented matrix form this would be
$$\begin{bmatrix} 1 & 1 & | & 2 \\ 1 & -1 & | & 0 \\ 2 & 0 & | & 2 \end{bmatrix} $$

After row reduction, this becomes
$$\begin{bmatrix} 1 & 1 & | & 2 \\ 0 & 1 & | & 1 \\ 0 & 0 & | & 0 \end{bmatrix} $$

The unique solution is x = 1, y = 1

The situation is different if we change one number in the last equation like so:
x + y = 2
x - y = 0
2x = 3

After row reduction, the reduced augmented matrix is:
$$\begin{bmatrix} 1 & 1 & | & 2 \\ 0 & 1 & | & 1 \\ 0 & 0 & | & -1/2 \end{bmatrix} $$
and there is no solution.

My knowledge of matrix condition numbers is pretty scant, so other than the simple examples I provided, I can't offer much more help than this.

 

[Borek]

From what you wrote sounds like your matrix contains experimental data. Are you sure elimination of rows is the best approach? And not some application of the least squares method?