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.

$\endgroup$
  • 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 May 31 '18 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 May 31 '18 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 Jun 1 '18 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 Jun 1 '18 at 17:27
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).

$\endgroup$
  • 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 Jun 1 '18 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 Jun 2 '18 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 Jun 4 '18 at 16:38
0
$\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.

$\endgroup$
  • 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 May 31 '18 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 Jun 1 '18 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 Jun 1 '18 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 Jun 1 '18 at 19:01
  • 1
    $\begingroup$ @HBR you can address Richard Zhang's comment by restricting your answer to just normal matrices. $\endgroup$ – GoHokies Jun 1 '18 at 20:12

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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