@article{AB-A-Coordinate-Free-Condition-Number-For-Convex-Programming,
Title = {A coordinate-free condition number for convex programming},
Author = {Dennis Amelunxen and Peter Bürgisser},
Pages = {1029-1041},
Year = {2012},
Journal = {SIAM Journal on Optimization},
Volume = {22},
Number = {3},
Abstract = {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\mathbb R^n$. Let $\mathrm\\\{Gr\\\}_{n,m}$ denote the Grassmann manifold of $m$-dimensional linear subspaces of $\mathbb 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 $\mathrm{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} \mid W' \in Sigma_m \}$ the Grassmann condition number of $W$ in $\mathrm{Gr}_{n,m}$, where the set of ill-posed instances $\Sigma_m$ subset $\mathrm{Gr}_{n,m}$ is defined as the set of linear subspaces touching $C$. We show that if $W = \mathrm{im}(A^T)$ for a matrix $A$ in $\mathbb 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 $\mathrm{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.},
Url = {http://arxiv.org/abs/1105.4049},
Url2 = {http://www3.math.tu-berlin.de/algebra/work/a.coordinate-free.condition.number.for.convex.programming.pdf}
}