Probabilistic Analysis of the Grassmann Condition Number
Probabilistic Analysis of the Grassmann Condition Number
复制标题
格拉斯曼条件数的概率分析
DOI：
10.1007/s10208-013-9178-4
复制
发表时间：
2015
影响因子：
3
通讯作者：
P. Bürgisser
中科院分区：
文献类型：
--
作者：
D. Amelunxen;P. Bürgisser
我们分析了R^n的一个随机m维线性子空间既与一个正则闭凸锥C <$R^n相交，又位于一个不与C相交的m维子空间（除了在原点处）的距离α之内的概率。结果用圆锥C的球面内禀体积表示。这允许我们对齐次凸可行性问题<$x∈ C <$0：Ax= 0的格拉斯曼条件数进行平均分析。Grassmann条件数是Renegar条件数的几何版本，我们最近在Amelunxen和Bürgisser（SIAM J. Optim. 22（3）：1029-1041（2012））。因此，我们给出了凸规划的第一平均分析，而不限于线性规划。特别地，我们证明了如果A∈R^m*n的项被选择为标准正态，那么对于任何正则锥C，我们有。证明依赖于各种技术从黎曼几何适用于格拉斯曼流形。
We analyze the probability that a random m-dimensional linear subspace of R^n both intersects a regular closed convex cone C⊆R^n and lies within distance α 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 for the homogeneous convex feasibility problem∃ x∈ C∖ 0: Ax= 0. The Grassmann condition number is a geometric version of Renegar’s condition number, which we have introduced recently in Amelunxen and Bürgisser (SIAM J. Optim. 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 A∈R^m*n are chosen iid standard normal, then for any regular cone C, we have. The proofs rely on various techniques from Riemannian geometry applied to Grassmann manifolds.
登录
查看更多内容
块结构扰动下不可行距离的表征
DOI：
--
发表时间：
2003
期刊：
影响因子：
--
作者：
Javier F. Pena
通讯作者：
Javier F. Pena
DOI：
10.1007/978-3-642-38896-5
发表时间：
2013-08
期刊：
--
影响因子：
--
作者：
Peter Bürgisser;F. Cucker
通讯作者：
Peter Bürgisser;F. Cucker
关于条件数论到非圆锥凸优化的扩展的工作论文
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Fernando Ord
通讯作者：
Fernando Ord
椭圆和双曲 n 维空间中的平行超曲面
DOI：
--
发表时间：
1950
期刊：
影响因子：
--
作者：
L. Santaló
通讯作者：
L. Santaló
判定线性规划解存在性的不适定性和复杂性
影响因子：
3.1
作者：
Jorge R. Vera
通讯作者：
Jorge R. Vera