Tight Bounds on the Radius of Nonsingularity
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F16%3A00459146" target="_blank" >RIV/67985807:_____/16:00459146 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-319-31769-4_9" target="_blank" >http://dx.doi.org/10.1007/978-3-319-31769-4_9</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-31769-4_9" target="_blank" >10.1007/978-3-319-31769-4_9</a>
Alternative languages
Result language
angličtina
Original language name
Tight Bounds on the Radius of Nonsingularity
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA13-17187S" target="_blank" >GA13-17187S: Constructing Advanced Comprehensible Classifiers</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Scientific Computing, Computer Arithmetic, and Validated Numerics. Revised Selected Papers
ISBN
978-3-319-31768-7
ISSN
0302-9743
e-ISSN
—
Number of pages
7
Pages from-to
109-115
Publisher name
Springer
Place of publication
Cham
Event location
Würzburg
Event date
Sep 21, 2014
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—