A coordinate-free condition number for convex programming

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 ⊆ ℝ ⁿ. Let Gr _n,m denote the Grassmann manifold of m-dimensional linear subspaces of ℝ ⁿ, and consider the projection distance d _p(W ₁,W ₂) := ∥ΠW ₁ - ΠW ₂ ∥ (spectral norm) between W ₁,W ₂ ∈ Gr _n,m, where ΠW _i denotes the orthogonal projection onto W _i. We call ℒ (W) := max{d _p(W,W′) ^-1 | W′ ∈ Σ _m} the Grassmann condition number of W ∈ Gr _n,m, where the set of ill-posed instances Σ _m ⊂ 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 ∈ ℝ ^m×n, then ℒ (W) ≤ R(A) ≤ ℒ (W) κ(A), where κ(A) = ∥A∥∥A† ∥ denotes the matrix condition number. This extends work by Belloni and Freund in [Math. Program. Ser. A, 119 (2009), pp. 95-107]. Furthermore, we show that ℒ (W) can also be characterized in terms of the Riemannian distance metric on Gr _n,m. This differential geometric characterization of ℒ (W) is the starting point of the sequel [D. Amelunxen and P. Bürgisser, Probabilistic analysis of the Grassman condition number, preprint, http:arxiv.org/abs/1112.2603, 2011] to this paper, where the first probabilistic analysis of Renegar's condition number for an arbitrary regular cone C is achieved. © 2012 Society for Industrial and Applied Mathematics.