On Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2003
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915560196931584 |
|---|---|
| author | Cheung, Dennis Cucker, Felipe Hauser, Raphael |
| author_facet | Cheung, Dennis Cucker, Felipe Hauser, Raphael |
| contents | In this paper we study the distribution tails and the moments of a condition number which arises in the study of homogeneous systems of linear inequalities. We consider the case where this system is defined by a Gaussian random matrix and characterise the exact decay rates of the distribution tails, improve the existing moment estimates, and prove various limit theorems for large scale systems. Our results are of complexity theoretic interest, because interior-point methods and relaxation methods for the solution of systems of linear inequalities have running times that are bounded in terms of the logarithm and the square of the condition number respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_math_0309278 |
| institution | arXiv |
| publishDate | 2003 |
| record_format | arxiv |
| spellingShingle | On Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems Cheung, Dennis Cucker, Felipe Hauser, Raphael Numerical Analysis Optimization and Control 90C31,15A52 (Primary); 90C05,90C60,62H10 (Secondary) In this paper we study the distribution tails and the moments of a condition number which arises in the study of homogeneous systems of linear inequalities. We consider the case where this system is defined by a Gaussian random matrix and characterise the exact decay rates of the distribution tails, improve the existing moment estimates, and prove various limit theorems for large scale systems. Our results are of complexity theoretic interest, because interior-point methods and relaxation methods for the solution of systems of linear inequalities have running times that are bounded in terms of the logarithm and the square of the condition number respectively. |
| title | On Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems |
| topic | Numerical Analysis Optimization and Control 90C31,15A52 (Primary); 90C05,90C60,62H10 (Secondary) |
| url | https://arxiv.org/abs/math/0309278 |