Preprint D20/2006
Algebraic Tail Decay of Condition Numbers for Random Conic Systems under a General Family of Input Distributions

Tobias Muller | Hauser, Raphael

**Keywords: **
Condition numbers | random matrices | linear programming | probabilistic analysis

We consider the conic feasibility problem associated with
linear homogeneous systems of inequalities. The complexity
of iterative algorithms for solving this problem depends on a
condition number. When studying the typical behaviour of
algorithms under stochastic input one is therefore naturally led
to investigate the fatness of the distribution tails of the random
condition number that ensues. We study an unprecedently general
class of probability models for the random input matrix and
show that the tails decay at algebraic rates with an exponent that
naturally emerges when applying a theory of uniform absolute
continuity which is also developed in this paper.