Jean-Pierre Dedieu

Carlos Beltrán, Jean-Pierre Dedieu, Gregorio Malajovich et al.

We define in the space of n by m matrices of rank n, n less or equal than m, the condition Riemannian structure as follows: For a given matrix A the tangent space of A is equipped with the Hermitian inner product obtained by multiplying the usual Frobenius inner product by the inverse of the square of the smallest singular value of A denoted sigma_n(A). When this smallest singular value has multiplicity 1, the function A -> log (sigma_n(A)^(-2)) is a convex function with respect to the condition Riemannian structure that is t -> log (sigma_n(A(t))^(-2)) is convex, in the usual sense for any geodesic A(t). In a more abstract setting, a function alpha defined on a Riemannian manifold (M,<,>) is said to be self-convex when log alpha (gamma(t)) is convex for any geodesic in (M,<,>). Necessary and sufficient conditions for self-convexity are given when alpha is C^2. When alpha(x) = d(x,N)^(-2) where d(x,N) is the distance from x to a C^2 submanifold N of R^j we prove that alpha is self-convex when restricted to the largest open set of points x where there is a unique closest point in N to x. We also show, using this more general notion, that the square of the condition number ||A|||_F / sigma_n(A) is self-convex in projective space and the solution variety.

Carlos Beltrán, Jean-Pierre Dedieu, Gregorio Malajovich et al.

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.

Jean-Pierre Dedieu, Gregorio Malajovich

We give an upper bound in O(d ^((n+1)/2)) for the number of critical points of a normal random polynomial with degree d and at most n variables. Using the large deviation principle for the spectral value of large random matrices we obtain the bound O(exp(-beta n^2 + (n/2) log (d-1))) (beta is a positive constant independent on n and d) for the number of minima of such a polynomial. This proves that most normal random polynomials of fixed degree have only saddle points. Finally, we give a closed form expression for the number of maxima (resp. minima) of a random univariate polynomial, in terms of hypergeometric functions.