From Steiner Formulas for Cones to Concentration of Intrinsic Volumes

The intrinsic volumes of a convex cone are geometric functionals that return basic structural information about the cone. Recent research has demonstrated that conic intrinsic volumes are valuable for understanding the behavior of random convex optimization problems. This paper develops a systematic technique for studying conic intrinsic volumes using methods from probability. At the heart of this approach is a general Steiner formula for cones. This result converts questions about the intrinsic volumes into questions about the projection of a Gaussian random vector onto the cone, which can then be resolved using tools from Gaussian analysis. The approach leads to new identities and bounds for the intrinsic volumes of a cone, including a near-optimal concentration inequality.

• Publication year

  2013

• Venue

  Discrete & Computational Geometry

• Publication date

  2013-08-24

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00454-014-9595-4arXiv 1308.5265
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Intrinsic volumes of symmetric cones and applications in convex programming

  2015cited by this paper
• A geometric analysis of convex demixing

  2013cited by this paper
• Concentration Inequalities: A Nonasymptotic Theory of Independence

  2013cited by this paper
• Living on the edge: A geometric theory of phase transitions in convex optimization

  2013cited by this paper
• Sharp recovery bounds for convex deconvolution, with applications

  2012cited by this paper
• Sharp Recovery Bounds for Convex Demixing, with Applications

  2012cited by this paper
• Wiley Series in Probability and Statistics

  2012cited by this paper
• Probabilistic Analysis of the Grassmann Condition Number

  2011cited by this paper
• A Coordinate-Free Condition Number for Convex Programming

  2011cited by this paper
• Geometric analysis of the condition of the convex feasibility problem

  2011cited by this paper
• Real and Complex Analysis

  2011cited by this paper
• Spectral Analysis of Large Dimensional Random Matrices

  2009cited by this paper
• Notes on the integral geometry in the hyperbolic plane

  2009cited by this paper
• Stochastic and Integral Geometry

  2008cited by this paper
• Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications

  2008cited by this paper
• Coverage processes on spheres and condition numbers for linear programming

  2007cited by this paper
• High-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to Dimension

  2006cited by this paper
• A gaussian kinematic formula

  2006cited by this paper
• Constrained Statistical Inference: Inequality, Order and Shape Restrictions by M. J. Silvapulle and P. K. Sen

  2006cited by this paper
• The probability that a slightly perturbed numerical analysis problem is difficult

  2006cited by this paper
• Wiley Series in Probability and Mathematical Statistics

  2005cited by this paper
• A course in convexity

  2002cited by this paper
• Proportional concentration phenomena on the sphere

  2002influential reference
• Concentration Inequalities Using the Entropy Method

  2002cited by this paper
• A course in approximation theory

  1999cited by this paper
• Appendix: probability and measure

  1997cited by this paper
• CONVEX BODIES: THE BRUNN–MINKOWSKI THEORY

  1994cited by this paper
• Convex analysis and minimization algorithms

  1993cited by this paper
• Convex Bodies: The Brunn–Minkowski Theory: Minkowski addition

  1993cited by this paper
• An asymptotic estimate of the average number of steps of the parametric simplex method

  1987cited by this paper
• Real and complex analysis, 3rd ed.

  1987cited by this paper
• Matrix analysis

  1985cited by this paper
• Real Analysis: Modern Techniques and Their Applications

  1984cited by this paper
• ON THE VOLUME OF TUBES

  1983cited by this paper
• Graduate Texts in Mathematics

  1982cited by this paper
• Encyclopedia of Mathematics and its Applications.

  1982cited by this paper
• Introductory Functional Analysis With Applications

  1978cited by this paper
• Non-linear angle-sum relations for polyhedral cones and polytopes

  1975influential reference
• Probability and its applications

  1975cited by this paper
• Das Will'sche Funktional

  1975cited by this paper
• Real Analysis

  1972cited by this paper
• On parallel hypersurfaces in the elliptic and hyperbolic n-dimensional space

  1950cited by this paper
• Steiner's formulae on a general $S^{n + 1}$

  1948cited by this paper
• Über die steinersche formel für parallelflächen

  1943cited by this paper
• Tubes and Spheres in n-Spaces, and a Class of Statistical Problems

  1939cited by this paper
• Gaussian Measures on a

  year unknowncited by this paper

• On Convex Functions of Gaussian Variables

  2025cites this paper
• A review of exact results for fluctuation formulas in random matrix theory

  2022cites this paper
• Gaussian random projections of convex cones: approximate kinematic formulae and applications

  2022cites this paper
• Convex Cones

  2022cites this paper
• Sharp phase transitions in Euclidean integral geometry

  2022cites this paper
• HIGH DIMENSIONAL ASYMPTOTICS OF LIKELIHOOD RATIO TESTS IN THE GAUSSIAN SEQUENCE MODEL UNDER CONVEX CONSTRAINTS

  2021cites this paper
• Global optimization using random embeddings

  2021cites this paper
• A new approach to weak convergence of random cones and polytopes

  2020cites this paper
• Localization technique in the discrete setting with applications

  2020cites this paper
• Faces in random great hypersphere tessellations

  2020cites this paper
• High-dimensional asymptotics of likelihood ratio tests in the Gaussian sequence model under convex constraints

  2020cites this paper
• Geometric and Functional Inequalities for Log-Concave Probability Sequences

  2020cites this paper
• Random cones in high dimensions I: Donoho-Tanner and Cover-Efron cones.

  2020cites this paper
• Randomized numerical linear algebra: Foundations and algorithms

  2020cites this paper
• Grassmann Angles and Absorption Probabilities of Gaussian Convex Hulls

  2019cites this paper
• Phase transitions in generalized compressed sensing

  2019cites this paper
• Intersection probabilities and kinematic formulas for polyhedral cones

  2018cites this paper
• P R ] 30 A pr 2 01 6 Random conical tessellations

  2018cites this paper
• Splitting tessellations in spherical spaces

  2018cites this paper
• Conic support measures

  2018influential citation
• Concentration of the Intrinsic Volumes of a Convex Body

  2018cites this paper
• Effective Condition Number Bounds for Convex Regularization

  2017cites this paper
• Intersection probabilities and kinematic formulas for polyhedral cones

  2017cites this paper
• The geometry of hypothesis testing over convex cones: Generalized likelihood tests and minimax radii

  2017cites this paper
• Convex hulls of random walks, hyperplane arrangements, and Weyl chambers

  2017cites this paper
• Sharp oracle inequalities in aggregation and shape restricted regression

  2016cites this paper
• Random Conical Tessellations

  2016cites this paper
• THÈSE DE DOCTORAT ÈS MATHÉMATIQUES

  2016cites this paper
• Behavior of the maximum likelihood in quantum state tomography

  2016cites this paper
• Adaptive confidence sets in shape restricted regression

  2016cites this paper
• New Berry-Esseen and Wasserstein bounds in the CLT for non-randomly centered random sums by probabilistic methods

  2015cites this paper
• Recovering Structured Signals in Noise : Precise Error Bounds 3 1 . 2 Structured Signals and Noisy Compressed Sensing

  2015cites this paper
• On measures of size for convex cones

  2015cites this paper
• Universality laws for randomized dimension reduction, with applications

  2015cites this paper
• Intrinsic Volumes of Polyhedral Cones: A Combinatorial Perspective

  2015influential citation
• Random Conical Tessellations

  2015cites this paper
• Convex hulls of random walks, hyperplane arrangements, and Weyl chambers

  2015cites this paper
• Convex hulls of multidimensional random walks

  2015cites this paper
• New Berry-Esseen and Wasserstein bounds in the CLT for non-randomly centered random sums by probabilistic methods

  2015cites this paper
• High dimensional regression and matrix estimation without tuning parameters

  2015cites this paper
• Recovering Structured Signals in Noise: Least-Squares Meets Compressed Sensing

  2015cites this paper
• Upper bounds for the relative entropy of the squared norm of a Gaussian projection onto a convex cone

  2014cites this paper
• Gordon's inequality and condition numbers in conic optimization

  2014influential citation
• A new perspective on least squares under convex constraint

  2014influential citation
• Gaussian Phase Transitions and Conic Intrinsic Volumes: Steining the Steiner Formula

  2014influential citation
• Measures on polyhedral cones: characterizations and kinematic formulas

  2014cites this paper
• Living on the edge: phase transitions in convex programs with random data

  2013cites this paper
• Technical Report No . 201 702 February 201 7 THE ACHIEVABLE PERFORMANCE OF CONVEX DEMIXING

  2013cites this paper
• The achievable performance of convex demixing

  2013cites this paper