We introduce and analyze a natural geometric version of Renegar's condition number R for the homogeneous convex feasibility problem associated with a regular cone C subseteq R^n. Let Gr_{ n,m} denote the Grassmann manifold of m-dimensional linear subspaces of R^n and consider the projection distance d_p(W_1,W_2) := ||Pi_{ W_1} - Pi_{ W_2}|| (spectral norm) between W_1 and W_2 in Gr_{ n,m}, where Pi_{ W_i} denotes the orthogonal projection onto W_i. We call C_G(W) := max { d_p(W,W')^{ -1} | W' \in Sigma_m} the Grassmann condition number of W in Gr_{ n,m}, where the set of ill-posed instances Sigma_m subset Gr_{ n,m} is defined as the set of linear subspaces touching C. We show that if W = im(A^T) for a matrix A in R^{ m\times n}, then C_G(W) \le R(A) \le C_G(W) kappa(A), where kappa(A) =||A|| ||A^\dagger|| denotes the matrix condition number. This extends work by Belloni and Freund in Math. Program. 119:95-107 (2009). Furthermore, we show that C_G(W) can as well be characterized in terms of the Riemannian distance metric on Gr_{ n,m}. This differential geometric characterization of C_G(W) is the starting point of the sequel [arXiv:1112.2603] to this paper, where the first probabilistic analysis of Renegar's condition number for an arbitrary regular cone C is achieved.
Categories: math.OC