Probabilistic analysis of the Grassmann condition number
From MaRDI portal
Publication:2340501
Abstract: We analyze the probability that a random m-dimensional linear subspace of R^n both intersects a regular closed convex cone Csubseteq R^n and lies within distance alpha of an m-dimensional subspace not intersecting C (except at the origin). The result is expressed in terms of the spherical intrinsic volumes of the cone C. This allows us to perform an average analysis of the Grassmann condition number C(A) for the homogeneous convex feasibility problem exists xin Csetminus 0 : Ax=0. The Grassmann condition number is a geometric version of Renegar's condition number, that we have introduced recently in [SIOPT 22(3):1029-1041, 2012]. We thus give the first average analysis of convex programming that is not restricted to linear programming. In particular, we prove that if the entries of Ain R^{m imes n} are chosen i.i.d. standard normal, then for any regular cone C, we have E[lnC(A)]<1.5 ln(n)+1.5. The proofs rely on various techniques from Riemannian geometry applied to Grassmann manifolds.
Recommendations
- Probabilistic analyses of condition numbers
- On a probabilistic aspect of the Grünbaum problem
- Probabilistic analysis of condition numbers for linear programming
- scientific article; zbMATH DE number 7139139
- scientific article; zbMATH DE number 2127963
- On some conditioning results in the probabilistic analysis of algorithms
- High probability analysis of the condition number of sparse polynomial systems
Cites work
- A characterization of the distance to infeasibility under block-structured perturbations
- A comprehensive introduction to differential geometry. Vol. 1-5
- A coordinate-free condition number for convex programming
- A geometric analysis of Renegar's condition number, and its interplay with conic curvature
- A new condition measure, preconditioners, and relations between different measures of conditioning for conic linear systems
- A new condition number for linear programming
- A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine
- A primal-dual symmetric relaxation for homogeneous conic systems
- Computing approximate solutions for convex conic systems of constraints
- Condition Numbers of Gaussian Random Matrices
- Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm
- Condition. The geometry of numerical algorithms
- scientific article; zbMATH DE number 5829189 (Why is no real title available?)
- scientific article; zbMATH DE number 3960432 (Why is no real title available?)
- scientific article; zbMATH DE number 3705455 (Why is no real title available?)
- scientific article; zbMATH DE number 47926 (Why is no real title available?)
- scientific article; zbMATH DE number 52737 (Why is no real title available?)
- scientific article; zbMATH DE number 3627912 (Why is no real title available?)
- scientific article; zbMATH DE number 568836 (Why is no real title available?)
- scientific article; zbMATH DE number 1069617 (Why is no real title available?)
- scientific article; zbMATH DE number 1113187 (Why is no real title available?)
- scientific article; zbMATH DE number 3436238 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 768050 (Why is no real title available?)
- scientific article; zbMATH DE number 873911 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 236540 (Why is no real title available?)
- scientific article; zbMATH DE number 3227205 (Why is no real title available?)
- scientific article; zbMATH DE number 3280855 (Why is no real title available?)
- scientific article; zbMATH DE number 3194988 (Why is no real title available?)
- Ill-Posedness and the Complexity of Deciding Existence of Solutions to Linear Programs
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- Intrinsic volumes of symmetric cones and applications in convex programming
- Linear programming, complexity theory and elementary functional analysis
- On an Extension of Condition Number Theory to Nonconic Convex Optimization
- On the complexity of linear programming under finite precision arithmetic
- On the Complexity of Solving Feasible Linear Programs Specified with Approximate Data
- On the Volume of Tubes
- Riemannian geometry. A modern introduction
- Smoothed analysis of condition numbers
- Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
- Some perturbation theory for linear programming
- Stochastic and Integral Geometry
- The kinematic formula in Riemannian homogeneous spaces
- The Probability That a Numerical Analysis Problem is Difficult
- The probability that a slightly perturbed numerical analysis problem is difficult
- Understanding the Geometry of Infeasible Perturbations of a Conic Linear System
Cited in
(10)- Conic intrinsic volumes of Weyl chambers
- On the number of flats tangent to convex hypersurfaces in random position
- Average-case complexity without the black swans
- Intrinsic volumes of symmetric cones and applications in convex programming
- The average condition number of most tensor rank decomposition problems is infinite
- Some preconditioners for systems of linear inequalities
- A coordinate-free condition number for convex programming
- \(p\)-adic integral geometry
- On the volume of tubular neighborhoods of real algebraic varieties
- From Steiner formulas for cones to concentration of intrinsic volumes
This page was built for publication: Probabilistic analysis of the Grassmann condition number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2340501)
