A coordinate-free condition number for convex programming
From MaRDI portal
Publication:4899023
DOI10.1137/110835177zbMATH Open1266.90139arXiv1105.4049OpenAlexW2078263475MaRDI QIDQ4899023FDOQ4899023
Authors: Dennis Amelunxen, Peter Bürgisser 
Publication date: 4 January 2013
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
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 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 imes 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.
Full work available at URL: https://arxiv.org/abs/1105.4049
Recommendations
Cited In (15)
- Probabilistic analysis of the Grassmann condition number
- On condition number theorems in mathematical programming
- Minimizing Condition Number via Convex Programming
- A geometrical stability condition for compressed sensing
- A Condition Number for Multifold Conic Systems
- The condition number of join decompositions
- New characterizations of Hoffman constants for systems of linear constraints
- A geometric analysis of Renegar's condition number, and its interplay with conic curvature
- A data-independent distance to infeasibility for linear conic systems
- Condition of intersecting a projective variety with a varying linear subspace
- From Steiner formulas for cones to concentration of intrinsic volumes
- Convexity properties of the condition number
- Some preconditioners for systems of linear inequalities
- The condition metric in the space of rectangular full rank matrices
- The Condition Number of Riemannian Approximation Problems
This page was built for publication: A coordinate-free condition number for convex programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899023)
