David Hartman and Milan Hladík. Tight bounds on the radius of nonsingularity. In Marco Nehmeier et al., editor, Scientific Computing, Computer Arithmetic, and Validated Numerics: 16th International Symposium, SCAN 2014, Würzburg, Germany, September 21-26, LNCS, pp. 109–115, Springer, Cham, 2016.
[PDF] [gzipped postscript] [postscript] [HTML]
Radius of nonsingularity of a square matrix is the minimal distance to a singular matrix in the maximum norm. Computing the radius of nonsingularity is an NP-hard problem. The known estimations are not very tight; one of the best one has the relative error 6n. We propose a randomized approximation method with a constant relative error 0.7834. It is based on a semidefinite relaxation. Semidefinite relaxation gives the best known approximation algorithm for MaxCut problem, and we utilize similar principle to derive tight bounds on the radius of nonsingularity. This gives us rigorous upper and lower bounds despite randomized character of the algorithm.
@inCollection{HarHla2016a,
author = "David Hartman and Milan Hlad\'{\i}k",
title = "Tight bounds on the radius of nonsingularity",
editor = "Nehmeier et al., Marco",
feditor = "Nehmeier, Marco and {Wolff von Gudenberg}, J{\"u}rgen and Tucker, Warwick",
booktitle = "Scientific Computing, Computer Arithmetic, and Validated Numerics: 16th International Symposium, {SCAN} 2014, W{\"u}rzburg, Germany, September 21-26",
publisher = "Springer",
address = "Cham",
volume = "9553",
series = "LNCS",
fseries = "Lecture Notes in Computer Science",
pages = "109-115",
year = "2016",
doi = "10.1007/978-3-319-31769-4_9",
issn = "0302-9743",
isbn = "978-3-319-31769-4",
bib2html_dl_html = "http://dx.doi.org/10.1007/978-3-319-31769-4_9",
abstract = "Radius of nonsingularity of a square matrix is the minimal distance to a singular matrix in the maximum norm. Computing the radius of nonsingularity is an NP-hard problem. The known estimations are not very tight; one of the best one has the relative error 6n. We propose a randomized approximation method with a constant relative error 0.7834. It is based on a semidefinite relaxation. Semidefinite relaxation gives the best known approximation algorithm for MaxCut problem, and we utilize similar principle to derive tight bounds on the radius of nonsingularity. This gives us rigorous upper and lower bounds despite randomized character of the algorithm.",
keywords = "Radius of nonsingularity; Bounds; Semidefinite programming",
}
Generated by bib2html.pl (written by Patrick Riley ) on Mon Apr 15, 2024 08:26:42