Probabilistic analysis of the Grassmann condition number

Details Probabilistic analysis of the Grassmann condition number Probabilistic analysis of the Grassmann condition number

2011-12-12

arxiv.org/abs/1112.2603v1

Mathematics

Optimization and Control

47 pages

Scientific paper

We perform an average analysis of the Grassmann condition number \CG(A) for the homogeneous convex feasibility problem \exists x \in C \setminus 0 : Ax=0, where C \subset R^n may be any regular cone. This in particular includes the cases of linear programming, second-order programming, and semidefinite programming. We thus give the first average analysis of convex programming, which is not restricted to linear programming. The Grassmann condition number is a geometric version of Renegar's condition number, which we have introduced recently in [arXiv:1105.4049v1]. In this work we use techniques from spherical convex geometry and differential geometry. Among other things, we will show that if the entries of A \in R^{m\times n} are chosen i.i.d. standard normal, then for any regular cone C we have E[ln \CG(A)] < 1.5 ln(n)+1.5.

Affiliated with

Also associated with

No associations

Rating

Probabilistic analysis of the Grassmann condition number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Probabilistic analysis of the Grassmann condition number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic analysis of the Grassmann condition number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-709329