5
$\begingroup$

The CHOLMOD library provides a CHOLMOD_rcond function that estimates the reciprocal condition number (in the one norm) of a symmetric positive definite matrix from its cholesky decomposition. This is defined as the ratio between the smallest and largest entries in the diagonal of the L factor. Why is this a true fact?

$\endgroup$
  • 1
    $\begingroup$ Note that the eigenvalues of a triangular matrix are the diagonal entries. In this case the ratio of the min/max diagonal entries should correspond to the reciprocal condition number in the 2-norm - are you sure the routine gives the 1-norm? $\endgroup$ – vibe Jun 5 at 17:25
  • $\begingroup$ @vibe I'm not sure what you mean with "should correspond", but note that the diagonal entries of the Cholesky factor $L$ are equal to neither the square roots of the eigenvalues of $LL^T$, nor $\|L\|$. $\endgroup$ – Federico Poloni Jun 26 at 11:23
1
$\begingroup$

This question is covered in the following paper:


Given:

The condition number of matrix $A\in\mathbb R^{n\times n}$ (wrt to inversion) is defined, as follows:

$$ \kappa(A)=\big\lVert A\big\lVert\big\lVert A^{-1}\big\lVert $$ where $\left\lVert \cdot \right\lVert$ is a matrix norm.

The Cholesky decomposition of $A=LL^T$, where $L\in \mathbb R^{n\times n}$, lower-triangular, with positive diagonal entries.


Let's see what we can say about $L$ just by looking at its entries (in particular, its diagonal entries). First of all, we can relax a more general inequality: $$ \big\lVert L \big\rVert_{1,2,\infty,F}\geq|\ell_{ij}|,\quad i,j=1,\ldots,n \tag{1} \label{eq1} $$

to the following, which looks only on the diagonal $$ \begin{aligned} \big\lVert L \big\rVert_{1,2,\infty,F}&\geq\ell_{ii},\quad i=1,\ldots,n \\ &\geq \max\limits_{1\leq i \leq n} \ell_{ii} \end{aligned} \tag{2} \label{eq2} $$

In $\eqref{eq1}$ and $\eqref{eq2}$, $\ell_{ij}$is the $(i,j)$th entry of the matrix $L$. $1$, $2$, $\infty$, and $F$ denote the 1-norm, 2-norm, infinity-norm, and Frobenius norm, respectively. The absolute value is dropped, since diagonal entries of $L$ arising from Cholesky factorization are positive.

Now, let's think if we can say something about $L^{-1}$. From $\eqref{eq1}$ and the fact that the reciprocals of the diagonal elements of $L$ are themselves elements of $L^{-1}$, we can also say that:

$$ \big\lVert L^{-1} \big\rVert_{1,2,\infty,F}\geq \left( \min\limits_{1\leq i \leq n }\ell_{ii}\right)^{-1} \tag{3} \label{eq3} $$

Equation $\eqref{eq3}$ is denoted as equation (2.1) in Higham's paper.

Since we are dealing with a square matrix $A$ and all the considered norms are sub-multiplicative: $$ \begin{aligned} \big\lVert A\big\rVert_{1,2,\infty,F}&\leq \big\lVert L\big\rVert_{1,2,\infty,F} \big\lVert L^T\big\rVert_{1,2,\infty,F}\\ &\leq \big\lVert L\big\rVert_{1,2,\infty,F} \big\lVert L\big\rVert_{1,2,\infty,F}\\ &\leq \big\lVert L\big\rVert_{1,2,\infty,F}^2 \end{aligned} \tag{4} \label{eq4} $$

From $\eqref{eq4}$, we can say that:

$$ \kappa(A)\leq\big\lVert L\big\rVert_{1,2,\infty,F}^2 \big\lVert L^{-1}\big\rVert_{1,2,\infty,F}^2 $$

therefore, considering also $\eqref{eq2}$ and $\eqref{eq3}$:

$$ \begin{aligned} \frac{1}{\kappa(A)}&\geq \frac{1}{\big\lVert L\big\rVert_{1,2,\infty,F}^2 \big\lVert L^{-1}\big\rVert_{1,2,\infty,F}^2}\\ &\geq \left( \frac{\min\limits_{1\leq i \leq n }\ell_{ii}}{\max\limits_{1\leq i \leq n} \ell_{ii}} \right)^2 \end{aligned} \tag{5} \label{eq5} $$

Equation $\eqref{eq5}$ is exactly what CHOLMOD's function cholmod_rcond() returns.

Is this a good estimate? Not necessarily. You may want to look at better ways (and discussion on the reliability of this particular estimate) to estimate the condition number from the aforementioned paper or newer research. Is it a useful one? Certainly. Because if you already have a Cholesky factorization, it is $\mathcal O(n)$ cheap.

$\endgroup$

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.