I stumbled upon the following remarkable fact when experimenting with the Gauss-Seidel iterative solver: First I construct a low-rank symmetric positive semi-definite matrix $A = M^TM$ with M a random (randn) matrix of size (k x n) with k << n (e.g. k = 100, n = 1000). Secondly I estimate the Gauss-Seidel convergence rate as follows:

  • Let $M = D + L$ and $K = U$ ($A = D + L + U$)

  • Consider the eigenvalues $\lambda$ of $M^{-1}K$. All will be $<= 1$ in absolute value (Householder-John theorem that proves GS convergence on SPD matrices). The eigenvalues of value $1$ correspond to the kernel of A, and can I ignore these (assuming I am not interested in the minimum norm solution, but any solution. Inspired by https://mathoverflow.net/questions/80793/is-gauss-seidel-guaranteed-to-converge-on-semi-positive-definite-matrices)

  • So finally let's call the convergence rate the largest eigenvalue below 1. For large matrices with k near n, this is typically very close to 1, which explains the slow convergence of GS. However, when k << n, I find that the convergence rate is <<1, more like 0.01, thus yielding very fast GS convergence.

Execute the code below in matlab to see for yourself


n = 1000
k = 100

C = randn(k, n);
A = C'*C;

L = tril(A, -1); U = triu(A, 1); D = diag(diag(A)); %A = D + L + U

M = D + L;
K = U;
R = M\K;
e = abs(eig(R));
rho = max(e( abs(1-e) > 1e-10))

Does anyone have an idea why this occurs?


So I believe I'm progressing towards the answer.

  • A first observation I find is that for k << n, the condition number of M (and thus A) is very low, even for big matrices. For k == n, the condition number seems bad for big matrices. For formal theory one would have to revert to Random Matrix Theory but I'm far from an expert on that.

  • Secondly, there seems to be a correlation between the condition number of M and A, and the spectral radius of $-K^{-1}M$. Ill-conditioning means slower convergence. I have found independent empirical evidence on this (http://fedcsis.eucip.pl/proceedings/pliks/65.pdf) but that paper is quite poor. Formal theory I do not know of. I'm going to try to relate the eigenvalues of A to those of $-K^{-1}M$.

Feel free to complete and correct!

  • $\begingroup$ Did you try something more like conjugate gradients or Chebyshev method? Their convergence can be somewhat better be described in terms of the condition number. IMHO the condition number of the low rank matrix is connected to the fact that (although $C^TC$ is a large matrix) the effective condition number is equal to that of $CC^T$ which is a small matrix. It's not surprising if one accepts that small random matrices are better conditioned than the large ones. It is also interesting that although the Gauss-Seidel looks fine, Jacobi fails. $\endgroup$ – Algebraic Pavel Jan 30 '14 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.