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

Raphael Hauser (hausercomlab.ox.ac.uk)
Tobias Muller (mullerstats.ox.ac.uk)

Abstract: 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.

Keywords: Condition numbers, random matrices, linear programming, probabilistic analysis.

Category 1: Linear, Cone and Semidefinite Programming (Other )

Citation: Numerical Analysis Report NA06/01, Oxford University Computing Laboratory, Parks Road, Oxford OX1 3QD, United Kingdom.

Download: [PDF]

Entry Submitted: 02/10/2006
Entry Accepted: 02/10/2006
Entry Last Modified: 02/10/2006

Modify/Update this entry