Options
Bounds for the componentwise distance to the nearest singular matrix
Publikationstyp
Journal Article
Date Issued
1997-01-01
Sprache
English
Author(s)
Institut
TORE-URI
Volume
18
Issue
1
Start Page
83
End Page
103
Citation
SIAM Journal on Matrix Analysis and Applications 18 (1): 83-103 (1997-01-01)
Publisher DOI
Scopus ID
Publisher
Soc.
The normwise distance of a matrix A to the nearest singular matrix is well known to be equal to ∥A∥/cond(A) for norms subordinate to a vector norm. However, there is no hope for finding a similar formula or even a simple algorithm for computing the componentwise distance to the nearest singular matrix for general matrices. This is because Poljak and Rohn [Math. Control Signals Systems, 6 (1993), pp. 1-9] showed that this is an NP-hard problem. Denote the minimum Bauer-Skeel condition number achievable by column scaling by K. Demmel [SIAM J. Matrix Anal. Appl., 13 (1992), pp. 10-19] showed that K is a lower bound for the componentwise distance to the nearest singular matrix. In our paper we prove that 2.4 · n ·K is an upper bound. This extends and proves a conjecture by Demmel and Higham (in the cited paper by Demmel). We give an explicit set of examples showing that such an upper bound cannot be better than n · K . Asymptotically, we show that n1+ln 2+∈ · K is a valid upper bound. -1 1.7 -1 -1 -1
Subjects
Componentwise distance
NP-hardness
Optimal Bauer-Skeel condition number
Singular matrix
DDC Class
004: Informatik
510: Mathematik