@article{AB-Probabilistic-Analysis-Of-The-Grassmann-Condition-Number,
Title = {Probabilistic analysis of the Grassmann condition number},
Author = {Dennis Amelunxen and Peter Bürgisser},
Pages = {3-51},
Year = {2015},
Journal = {Foundations of Computational Mathematics},
Volume = {15},
Number = {1},
Month = {02},
Abstract = {We analyze the probability that a random $m$-dimensional linear subspace of $IR^n$ both intersects a regular closed convex cone $C\subseteq IR^n$ and lies within distance $\alpha$ of an $m$-dimensional subspace not intersecting $C$ (except at the origin). The result is expressed in terms of the spherical intrinsic volumes of the cone $C$. This allows us to perform an average analysis of the Grassmann condition number $CG(A)$ for the homogeneous convex feasibility problem $\exists x\in C\setminus0:Ax=0$. The Grassmann condition number is a geometric version of Renegar's condition number, that we have introduced recently in [SIOPT~22(3):1029--1041, 2012]. We thus give the first average analysis of convex programming that is not restricted to linear programming. In particular, we prove that if the entries of $A\in IR^{m\times n}$ are chosen i.i.d.~standard normal, then for any regular cone $C$, we have $ IE[\ln CG(A)]<1.5\ln(n)+1.5$. The proofs rely on various techniques from Riemannian geometry applied to Grassmann manifolds.},
Url = {http://arxiv.org/abs/1112.2603},
Url2 = {http://www3.math.tu-berlin.de/algebra/work/pagcn-4.pdf}
}