8
$\begingroup$

A number of numerical problems are easy to solve when condition number $\kappa$ of the problem is low. For instance, conjugate gradient descent complexity scales as $O(\sqrt{\kappa})$.

However

  1. "condition number" is numerically unstable, becoming meaningless for large problems
  2. a system that's well conditioned for all practical purposes can have an infinite condition number.

Are there alternatives that address these problems? I came across one stable measure which ties performance of gradient descent to the density of eigenvalues around 0.

  1. has it been described in literature?
  2. is there an analogue for conjugate gradient descent or other solvers?

For gradient descent applied to solve $Ax=b$ through least-squares minimization, you can show that if squared singular value density $f(x)$ of $A$ diverges as $\sim x^p$ for $x\to 0$, then residual sum of squares (RSS) for $t\to \infty$ steps decays as $\sim \frac{1}{t^{p+2}}$

For precise meaning of $\sim$, see Theorem 2.3 of Coqueret's "probabilistic Laplace Transforms" paper.

For instance, if $A$ is a product of many matrices with IID random entries, this density diverges as $x^{-1}$, you would expect that RSS $h(t)$ to decay as $O(t^{-1})$, which is confirmed by simulations below on a product of 100 random $1000\times 1000$ matrices

How you could show this theoretically:

  1. Assume step size $\alpha=1$ and $\|A\|=1$ without loss of generality
  2. This gives RSS after $t/2$ steps as $\sum_i h_i(1-h_i)^{t}$ where $h_i$ is $i$th squared singular value of $A$
  3. Use bound techniques like here to replace $(1-h_i)^t$ with $\exp(-t h_i)$
  4. Introduce density $g(x)=x f(x)$ to express RSS as $h(t)=E_g \exp(-t x)$
  5. $h(-t)$ is the moment-generating function of density $g(x)$, use Tauberian theorems to obtain RSS at $t\to \infty$ from density at $0$
$\endgroup$
6
  • $\begingroup$ Related follow-up discussion on mathoverflow specific to Conjugate Gradient $\endgroup$ Aug 20, 2023 at 18:50
  • $\begingroup$ Talking large problems, isn't every technique basically just doomed? It's not like codes even compute the actual condition number in practice (maybe some use an rcond like estimate) and computing the things like the density of eigen values around zero is probably going to be more difficult and expensive than whatever iterative algorithm you otherwise were planning to apply. Unless you can assume a specific underlying structure for $A$ (like your example) where you can derive something analytical. $\endgroup$ Aug 21, 2023 at 0:30
  • $\begingroup$ @MikaelÖhman every technique is probably "doomed" in an adversarial setting, but somehow condition number can be useful. I was wondering if there's something that addresses rcond problems, ie 1) more numerically stable 2) non-vacuous in the case of infinite condition number $\endgroup$ Aug 21, 2023 at 2:19
  • 3
    $\begingroup$ I recently attended a talk that addresses some issues with the condition number. "Towards a more sensible theory of stability in Numerical Linear Algebra" by Carlos Bertran. Of particular interest here is the notion of "condition number of the condition number". This is not a solution to the question but related in that they formalize the idea that condition number is somewhat meaningless when it is ill-conditioned itself. $\endgroup$ Aug 21, 2023 at 7:05
  • $\begingroup$ @ThijsSteel I'm trying to find this talk, which meeting was that? $\endgroup$ Aug 21, 2023 at 7:17

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.