Conditioning of random conic systems under a general family of input distributions

R. Hauser, T. Müller

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

4 Citaten (Scopus)

Samenvatting

We consider the conic feasibility problem associated with the linear homogeneous system Ax=0, x¿0. The complexity of iterative algorithms for solving this problem depends on a condition number C(A). When studying the typical behavior of algorithms under stochastic input, one is therefore naturally led to investigate the fatness of the tails of the distribution of C(A). Introducing the very general class of uniformly absolutely continuous probability models for the random matrix A, we show that the distribution tails of C(A) decrease at algebraic rates, both for the Goffin–Cheung–Cucker number C G and the Renegar number C R . The exponent that drives the decay arises naturally in the theory of uniform absolute continuity, which we also develop in this paper. In the case of C G , we also discuss lower bounds on the tail probabilities and show that there exist absolutely continuous input models for which the tail decay is subalgebraic.
Originele taal-2Engels
Pagina's (van-tot)335-358
TijdschriftFoundations of Computational Mathematics
Volume9
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 2009

Vingerafdruk

Duik in de onderzoeksthema's van 'Conditioning of random conic systems under a general family of input distributions'. Samen vormen ze een unieke vingerafdruk.

Citeer dit