direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Ehemalige Mitarbeiter

Dr. Dennis Amelunxen

Lupe [1]

City University of Hong Kong
Department of Mathematics
G6613 (Green Zone), 6/F Academic 1
Tat Chee Avenue, Kowloon Tong, Hong Kong
Persönliche Homepage
sites.google.com/site/dennisamelunxen/home [2]

Publikationen in der Arbeitsgruppe

Probabilistic analysis of the Grassmann condition number
Zitatschlüssel AB-Probabilistic-Analysis-Of-The-Grassmann-Condition-Number
Autor Dennis Amelunxen and Peter Bürgisser
Seiten 3-51
Jahr 2015
Journal Foundations of Computational Mathematics
Jahrgang 15
Nummer 1
Monat 02
Zusammenfassung We analyze the probability that a random $m$-dimensional linear subspace of $IR^n$ both intersects a regular closed convex cone $Csubseteq IR^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 $CG(A)$ for the homogeneous convex feasibility problem $exists xin Csetminus0: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 IR^m× n$ are chosen i.i.d. standard normal, then for any regular cone $C$, we have $ IE[łn CG(A)]<1.5łn(n)+1.5$. The proofs rely on various techniques from Riemannian geometry applied to Grassmann manifolds.
Link zur Publikation [3] Link zur Originalpublikation [4] Download Bibtex Eintrag [5]
------ Links: ------

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe

Copyright TU Berlin 2008