CHOLMOD condition number estimate

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?

• 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?
– vibe
Jun 5, 2019 at 17:25
• @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\|$. Jun 26, 2019 at 11:23

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.

I belive there is an error in the answer above. As per equations (2) and (3) in Anton's answer

$$$$\|L\|\|L^{-1}\| \geq \frac{\max_{i\in\{1,\ldots,n\}} \ell_{ii}}{\min_{i\in\{1,\ldots,n\}} \ell_{ii}} \tag{1}$$$$

is a lower bound whereas

$$\kappa(A) \leq \|L\|^2\|L^{-1}\|^2$$ is an upper bound. Thus in fact we have

$$\kappa(A)\leq \|L\|^2\|L^{-1}\|^2 \geq \left (\frac{\max_{i\in\{1,\ldots,n\}} \ell_{ii}}{\min_{i\in\{1,\ldots,n\}} \ell_{ii}}\right )^{\!\!2},$$ which is not very helpful. This cannot be resolved by simply taking the reciprocals because that just flips both inequalities.

However, if we restrict our derivations only to the $$2$$-norm we have [1]

$$\kappa_2(A)\triangleq \|A\|_2\|A^{-1}\|_2 = \kappa_2(L)^2 = (\|L\|_2\|L^{-1}\|_2)^2.$$ Using the inequality (1) we now obtain

$$\kappa_2(A) \geq \left (\frac{\max_{i\in\{1,\ldots,n\}} \ell_{ii}}{\min_{i\in\{1,\ldots,n\}} \ell_{ii}}\right )^{\!\!2}.$$

[1] N. J. Higham, "A survey of condition number estimation for triangular matrices," SIAM Review, vol. 29, no. 4, pp. 575–596, Dec. 1987.