I am working with classical multidimensional scaling and the configuration matrix for start the iterative process is ill-conditioned. For that reasen I am looking for methods to transform this matrix and obtain a better condition number
Good evening. The possible way, I think, is to add to initial matrix an identity one multiplied with some small constant (this will be diagonal matrix with small nonzero numbers on main diagonal). For some good constant's value, this changes the trace of the matrix and makes it less ill-conditioned. This is a kind of regularization that can increase the methodical error (we change the initial data and solve new problem that is very similar to initial but not identical to it) but significantly decrease the error from problem's being ill-conditioned. Maybe I am wrong and there is better way.
In fact you need to use a preconditioner which could be your diagonal elements. See some good books on iteration methods.
Thank you very much for everyone. I consult this papers and books.
The old trick, good for matrices making left hand side of the set of linear equation is to multiply each row (don't forget to do the same with right hand side(s)!) by qk. The number qk is the inverse of geometric mean of absolute values of all non-zero matrix elements in row k.
Scaling is not useful for a matrix that is ill-conditioned. You might try to compare the "shift" method suggested by Konstantin Semenov with another one where you replace the ill-conditioned matrix with a "better" (in the sense of condition number) approximation, of a lower rank.
Dear Luca Dimiccoli, your suggestion is very important to me. Can you give me papers and books where I could read about this method?
You can find it in the section "Rank deficient and ill-conditioned problems", in Ake Björck - Numerical Methods for Least Squares Problems.
One of the methods used to reduce the conditional number of a matrix in optimization, is duagonal scaling. You might want to take a look at.
- Badges
- Science topic
- Similar topics
- Mathematics
- Algebra
- Matrix