7
$\begingroup$

I am new to numerical linear algebra, so i came to know that condition number in 2-norm case will be ratio of largest to smallest singular value.

Another concept "Nearness To Singularity" is measured using this number being large.

But consider the case where singular values are close to 0 but smallest and largest singular values are also close to each other. In this case condition number will not be large enough to indicate that matrix is very near to being singular.

So is it reliable always to use condition number's magnitude as a measure of nearness to singularity.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ ask yourself this: is the matrix $A = \left[ \begin{array}{cc} \epsilon & 0 \\ 0 & \epsilon \end{array} \right]$ with $\epsilon = 10^{-16}$ nearly singular? in other words, what is its (minimum) distance to the nearest singular matrix? (hint: it is $1/{\rm cond}(A)$) $\endgroup$
    – GoHokies
    Commented May 31, 2018 at 20:10
  • 2
    $\begingroup$ There is an important difference between the absolute distance to the nearest singular matrix and the relative distance to the nearest singular matrix. $\endgroup$
    – Brian Borchers
    Commented May 31, 2018 at 20:58
  • 3
    $\begingroup$ Re/@GoHokies comment. The matrix $B=[\epsilon \; 0; 0 \; 0]$ is singular and very close to $A$ in absolute terms (the Frobenius norm of the difference is $\epsilon$), but very far away in relative terms. $\endgroup$
    – Brian Borchers
    Commented Jun 1, 2018 at 3:09
  • 1
    $\begingroup$ @BrianBorchers yes, i should have made it clear that I meant the relative distance to singularity. the absolute distance is, of course, $\| A^{-1} \|^{-1} = \| A\| / {\rm cond}(A)$. $\endgroup$
    – GoHokies
    Commented Jun 1, 2018 at 17:27

2 Answers 2

Reset to default
6
$\begingroup$

The condition number measures the relative distance from singularity of a matrix $A$: that is, $$ \min_{\text{$X$ is singular}} \frac{\|A-X\|}{\|A\|} = \frac{1}{\kappa(A)} $$ (the norm here is the Euclidean / induced / spectral norm --- i.e., $\|A\|=\sigma_1(A)$). This property follows from the Eckart-Young theorem.

Your example with a small $\|A\|$ highlights the fact that relative and absolute distance aren't the same thing. Often, measuring relative errors and distances makes more sense in numerical analysis, because it fits better with how errors appear in the data (due to inexact arithmetic, but not only).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Shouldn't the norms here be induced 2-norms (i.e. spectral), and not the matrix Euclidean (i.e. Frobenius)? The expression for the Euclidean norm is $\sigma_{\min}/(\sum_{i}\sigma_{i}^{2})^{1/2}\le\sigma_{\min}/\sigma_{\max}\equiv 1/\kappa$ $\endgroup$
    – Richard Zhang
    Commented Jun 1, 2018 at 19:08
  • $\begingroup$ @RichardZhang I call "Euclidean norm" the induced 2-norm. I didn't know the other convention was in use, too. $\endgroup$
    – Federico Poloni
    Commented Jun 2, 2018 at 6:00
  • $\begingroup$ Hey thanks for this explanation, can you point me to any reference where i can learn about why relative error fits better with how errors appear in the data ? $\endgroup$
    – Siddharth Shakya
    Commented Jun 4, 2018 at 16:38
1
$\begingroup$

For a normal matrix $A$, the value of the smallest eigenvalue tells us whether $A$ is singular or not: Imagine that the eigenvectors of $A$ can form a complete set that span the space of the columns of $A$, it can be decomposed: $$A=S^{-1}\Lambda S$$ Where $S$ are the eigenvectors gathered in a matrix and $\Lambda=\textrm{diag}(\lambda_1,\lambda_2,...,\lambda_n)$ their corresponding eigenvalues with $\lambda_1\leq \lambda_2\leq...\leq\lambda_n$ The smaller $\lambda_1$ the more singular $A$, because $A^{-1}=S^{-1}\Lambda^{-1}S$ with $\Lambda^{-1}=\textrm{diag}(\lambda_1^{-1},\lambda_2^{-1},...,\lambda_n^{-1})$.

Regarding the accuracy when solving a system of equations, for example: $Ax=f$, the condition number of the matrix $\kappa(A)$ measures the error in the solution $x$ when $f$ is perturbed: $$\delta x=A^{-1}\delta f$$ whose upper threshold coincides when $\delta f$ is in the direction of the eigenvector whose eigenvalue is the largest: $$|\delta x|=|A^{-1}\delta f|\leq \frac{1}{\lambda_1}|\delta f|$$

If now we divide the last equation by $|x| $ to obtain the relative error we find: $$\frac{|\delta x|}{| x|}\leq\frac{1}{\lambda_1}\frac{|\delta f|}{|x|}$$ and the lower threshold for $|x|$ is obtained from: $|f|=|Ax|\leq \lambda_n|x|$. Introduced in the last equation: $$\frac{|\delta x|}{| x|}\leq\kappa(A)\frac{|\delta f|}{|f|}$$ Where $\kappa(A) = \lambda_n/\lambda_1$, tells us the upper threshold of the error in $x$ when $f$ is perturbed.

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ there are two problems with this answer: (1) it applies only to the subset of diagonalizable matrices with real eigenvalues, and (more importantly) (2) it does not directly address the OP's question, i.e. the case where singular values are close to 0 but smallest and largest singular values are also close to each other. $\endgroup$
    – GoHokies
    Commented May 31, 2018 at 20:20
  • 1
    $\begingroup$ This is also valid for complex eigenvalues (considering its magnitude). On the other hand, I will not have a PhD in CS as you clearly have, but I think that the right person that have to judge if this helps or not is the OP, not you. In my opinion, he is in an introductory level and I consider ok to provide him with an illustrative example (I obviously know that is not as general as I wanted, but who cares! he is asking why and not how). Maybe next time you should make suggestions instead of rejections. Here people seem to enjoy a lot with downvotes. What a pitty! $\endgroup$
    – HBR
    Commented Jun 1, 2018 at 6:09
  • 2
    $\begingroup$ my comment was not meant as a personal attack (apologies if it came across that way) also, I did not downvote your answer. I merely pointed out a couple of ways your answer could be improved - that is, by generalizing the discussion to singular values and considering explicitly what happens in the special case OP asks about. $\endgroup$
    – GoHokies
    Commented Jun 1, 2018 at 8:39
  • 3
    $\begingroup$ @HBR -- It is the singular values that control issues associated with conditioning, and not eigenvalues. The matrices $\begin{bmatrix}1 & 0\\ 0 & 1 \end{bmatrix}$ and $\begin{bmatrix}1 & 0\\ 10^{12} & 1 \end{bmatrix}$ both have eigenvalues of 1, but only the latter is ill-conditioned with a condition number of around $10^{12}$. $\endgroup$
    – Richard Zhang
    Commented Jun 1, 2018 at 19:01
  • 1
    $\begingroup$ @HBR you can address Richard Zhang's comment by restricting your answer to just normal matrices. $\endgroup$
    – GoHokies
    Commented Jun 1, 2018 at 20:12

Your Answer

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

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