Convexity properties of the condition number II
Provides theoretical foundations for analyzing the complexity of path-following algorithms in numerical linear algebra and polynomial system solving.
This paper extends previous work on the condition metric in matrix spaces, proving that the inverse of the smallest singular value is log-convex along geodesics in a Lipschitz-Riemann structure, with implications for the complexity of path-following algorithms for polynomial systems.
In our previous paper [SIMAX 31 n.3 1491-1506(2010)], we studied the condition metric in the space of maximal rank matrices. Here, we show that this condition metric induces a Lipschitz-Riemann structure on that space. After investigating geodesics in such a nonsmooth structure, we show that the inverse of the smallest singular value of a matrix is a log-convex function along geodesics (Theorem 1). We also show that a similar result holds for the solution variety of linear systems (Theorem 31). Some of our intermediate results, such as Theorem 12, on the second covariant derivative or Hessian of a function with symmetries on a manifold, and Theorem 29 on piecewise self-convex functions, are of independent interest. Those results were motivated by our investigations on the com- plexity of path-following algorithms for solving polynomial systems.