Home / Curated / Mathematical Methods / Conic Statistical Dimension, Intrinsic Volume Concentration, and Approximate Kinematic Phase Transitions in Random Convex Programs

Conic Statistical Dimension, Intrinsic Volume Concentration, and Approximate Kinematic Phase Transitions in Random Convex Programs

Mathematical Methods AIMech:ConicStatisticalDimensionIntrinsicVolumeConcentrationAndPhaseTransitions DRAFT

Aliases: Amelunxen-Lotz-McCoy-Tropp Conic Statistical Dimension and Phase Transitions, Statistical Dimension of Convex Cones and Approximate Conic Kinematic Formula, Conic Intrinsic Volume Concentration and Random Convex Optimization Phase Transitions, Descent Cone Subdifferential Recipe with Nonasymptotic Variance Error Bound

Conic Statistical Dimension, Intrinsic Volume Concentration, and Approximate Kinematic Phase Transitions in Random Convex Programs is a conic integral geometry and convex optimization framework established by Amelunxen, Lotz, McCoy, and Tropp (2014, Information and Inference: A Journal of the IMA 3(3):224-294, DOI:10.1093/imaiai/iau005, arXiv:1303.6672v2) that defines the statistical dimension $\delta(C) := \sum_{k=0}^d k v_k(C) = \mathbb{E}[\|\Pi_C(g)\|^2] = \mathbb{E}[\operatorname{dist}^2(g, C^\circ)]$ of a closed convex cone $C \subset \mathbb{R}^d$ as the mean of its conic intrinsic volume distribution $(v_0(C), \dots, v_d(C))$ and proves that $v_k(C)$ concentrates exponentially around $\delta(C)$ on scale $\omega(C) := \sqrt{\delta(C) \wedge \delta(C^\circ)}$ via $p_C(\lambda) = 4\exp\!\left(\frac{-\lambda^2/8}{\omega^2(C)+ \lambda}\right)$ (Theorem 6.1). Combining intrinsic-volume concentration with the exact conic kinematic and Crofton formulas $\mathbb{P}\{C \cap Q K \ne \{0\}\} = 2 h_{d+1}(C \times K)$ yields the Approximate Kinematic Formula (Theorem I and Theorem 7.1), which proves sharp two-sided phase transitions of width $O(\omega(C)) \le O(\sqrt{d})$ for regularized linear inverse problems at $m = \delta(\mathcal{D}(f, x_0))$ (Theorem II), convex demixing under a random orthogonal basis $U \in O(d)$ at $\delta(\mathcal{D}(f, x_0)) + \delta(\mathcal{D}(g, y_0)) = d$ (Theorem III), and random cone programs between unboundedness ($m \le \delta(C) - \lambda$) and infeasibility ($m \ge \delta(C) + \lambda$, Theorem 8.1), together with a nonasymptotic error bound $0 \le \inf_{\tau \ge 0} J(\tau; \partial f(x)) - \delta(\mathcal{D}(f, x)) \le \frac{2\sup\{\|s\| : s \in \partial f(x)\}}{f(x/\|x\|)}$ for the subdifferential recipe $J(\tau) = \mathbb{E}[\operatorname{dist}^2(g, \tau \partial f(x))]$ (Theorem 4.3).

Identity Notes & Concept Scope Checked against all 442 pinned AIO concepts and 651 maintained AIMech concepts. Distinct from `AIMech:AtomicNormConvexGeometryAndTangentConeGaussianWidthForLinearInverseProblems` (Chandrasekaran, Recht, Parrilo, & Willsky 2012, FoCM 12(6):805-849), which establishes only a one-sided Gaussian recovery sufficiency bound $m \ge w(\mathcal{T}_{\mathcal{A}}(x^*) \cap \mathbb{S}^{p-1})^2 + O(\sqrt{p})$ via Gordon's escape-through-a-mesh inequality and an upper-bound polarity recipe without a lower-bound tightness guarantee, whereas Amelunxen, Lotz, McCoy, & Tropp (2014) prove via the spherical Steiner formula and Gaussian log-Sobolev inequalities that conic intrinsic volumes concentrate around the statistical dimension $\delta(C)$ (Theorem 6.1), derive two-sided approximate kinematic bounds for Haar-random orthogonal rotations $Q \in O(d)$ (Theorems I and 7.1), establish universal two-sided phase transitions for linear inverse problems (Theorem II), convex demixing (Theorem III), and random cone programs (Theorem 8.1), prove the nonasymptotic error bound for the subdifferential recipe (Theorem 4.3), and compute exact Weyl-chamber harmonic number statistical dimensions $\delta(\mathcal{N}(\mathcal{P}(x), x)) = H_d$ for permutahedra (Propositions 3.5 and 9.1).

Claims & Grounded Evidence

3 Claims

Mechanism #canonical-statistical-dimension-equivalent-characterizations-and-intrinsic-volume-concentration

For any closed convex cone $C \subset \mathbb{R}^d$ with conic intrinsic volumes $v_k(C)$ ($k = 0, \dots, d$ satisfying $\sum_{k=0}^d v_k(C) = 1$, polarity reversal $v_k(C) = v_{d-k}(C^\circ)$, and Gauss-Bonnet $\sum_{k\text{ even}} v_k(C) = \sum_{k\text{ odd}} v_k(C) = 1/2$ when $C$ is not a subspace, Fact 5.5, Eqs. 5.1-5.3), the spherical Steiner formula $\mathbb{P}\{\|\Pi_C(\theta)\|^2 \ge \varepsilon\} = \sum_{k=0}^d v_k(C) I_k^d(\varepsilon)$ (Fact 5.7, Eq. 5.6) implies that the intrinsic definition $\delta(C) := \sum_{k=0}^d k v_k(C)$ coincides with the Gaussian metric projection $\mathbb{E}[\|\Pi_C(g)\|^2] = d\mathbb{E}[\|\Pi_C(\theta)\|^2] = \mathbb{E}[\operatorname{dist}^2(g, C^\circ)] = \mathbb{E}[(\sup_{y \in C \cap \mathbb{B}^d} \langle y, g\rangle)^2]$ (Propositions 2.4, 3.1, and 5.12), satisfies complementarity $\delta(C) + \delta(C^\circ) = d$ (Eq. 3.7), direct-product additivity $\delta(C \times K) = \delta(C) + \delta(K)$ (Eq. 3.8), Gaussian-width sandwiching $w^2(C) \le \delta(C) \le w^2(C) + 1$ (Proposition 10.2, Eq. 10.1), and is the unique continuous, rotation-invariant, localizable valuation on closed convex cones extending $\delta(L) = \operatorname{dim}(L)$ (Section 5.6, p. 23). Moreover, with transition width $\omega(C) := \sqrt{\delta(C) \wedge \delta(C^\circ)}$ and $p_C(\lambda) := 4\exp\!\left(\frac{-\lambda^2/8}{\omega^2(C) + \lambda}\right)$, the tail functional $t_k(C) = \sum_{j=k}^d v_j(C)$ satisfies $t_{k_-}(C) \ge 1 - p_C(\lambda)$ for $k_- \le \delta(C) - \lambda + 1$ and $t_{k_+}(C) \le p_C(\lambda)$ for $k_+ \ge \delta(C) + \lambda$ (Theorem 6.1, Eqs. 6.1-6.3, Lemmas 6.2-6.3, Sublemma E.3).

supports Source: Living on the edge: phase transitions in convex programs with random data · Locator: Section 2.2, pp. 4-6, Definition 2.2, Proposition 2.4; Section 3.1, p. 13, Proposition 3.1; Section 5, pp. 19-23, Fact 5.5, Fact 5.7, Proposition 5.12, Section 5.6; Section 6, pp. 24-25, Theorem 6.1, Lemmas 6.2-6.3; Section 10.3.1, p. 33, Proposition 10.2; Appendices E-F, pp. 46-49

Mechanism #approximate-conic-kinematic-formula-and-universal-phase-transitions-in-random-convex-programs

Combining the exact conic kinematic and Crofton formulas $\mathbb{P}\{C \cap Q K \ne \{0\}\} = 2 h_{d+1}(C \times K)$ and $\mathbb{P}\{C \cap Q L_{d-m} \ne \{0\}\} = 2 h_{m+1}(C)$ (Facts 2.1 and 5.10, Eqs. 5.9-5.10) with half-tail interlacing $2 h_k(C) \ge t_k(C) \ge 2 h_{k+1}(C)$ (Proposition 5.9, p. 22) and intrinsic-volume concentration yields the Approximate Kinematic Formula (Theorem 7.1, Eqs. 7.1-7.2; Theorem I, p. 5): for uniformly random $Q \in O(d)$ and $\lambda \ge 0$, $m \ge \delta(C) + \lambda \Rightarrow \mathbb{P}\{C \cap Q L_{d-m} \ne \{0\}\} \le p_C(\lambda)$, $m \le \delta(C) - \lambda \Rightarrow \mathbb{P}\{C \cap Q L_{d-m} \ne \{0\}\} \ge 1 - p_C(\lambda)$, and for any convex cone $K \subset \mathbb{R}^d$, $\delta(C) + \delta(K) \le d - 2\lambda \Rightarrow \mathbb{P}\{C \cap Q K \ne \{0\}\} \le p_C(\lambda) + p_K(\lambda)$ while $\delta(C) + \delta(K) \ge d + 2\lambda \Rightarrow \mathbb{P}\{C \cap Q K \ne \{0\}\} \ge 1 - (p_C(\lambda) + p_K(\lambda))$. This immediately proves sharp two-sided phase transitions with $a_\eta = \sqrt{8\log(4/\eta)}$ for: (1) regularized linear inverse problems $\min f(x) \text{ s.t. } A x = A x_0$ at $m = \delta(\mathcal{D}(f, x_0)) \pm a_\eta\sqrt{d}$ (Theorem II, p. 8); (2) convex demixing $\min f(x) \text{ s.t. } g(y) \le g(y_0),\, x + U y = x_0 + U y_0$ at $\delta(\mathcal{D}(f, x_0)) + \delta(\mathcal{D}(g, y_0)) = d \pm a_\eta\sqrt{d}$ (Theorem III, p. 11); and (3) random cone programs $\min \langle u, x\rangle \text{ s.t. } A x = b,\, x \in C$ between unboundedness ($m \le \delta(C) - \lambda$) and infeasibility ($m \ge \delta(C) + \lambda$) each with probability $\ge 1 - p_C(\lambda)$ (Theorem 8.1, p. 27).

supports Source: Living on the edge: phase transitions in convex programs with random data · Locator: Section 2.3, p. 5, Theorem I; Section 2.5, pp. 6-9, Fact 2.8, Theorem II; Section 2.6, pp. 9-11, Fact 2.12, Theorem III; Section 5.4, p. 22, Proposition 5.9, Fact 5.10; Section 7, pp. 25-27, Theorem 7.1, Lemma 7.2; Section 8, pp. 27-29, Theorem 8.1
supports Source: Living on the edge: phase transitions in convex programs with random data · Locator: Abstract

Scope #subdifferential-descent-cone-recipe-nonasymptotic-error-bound-and-exact-cone-dimensions

For any proper convex function $f: \mathbb{R}^d \to \overline{\mathbb{R}}$ whose subdifferential $\partial f(x)$ is nonempty, compact, and does not contain $0$, the expected squared distance $J(\tau; \partial f(x)) := \mathbb{E}[\operatorname{dist}^2(g, \tau \partial f(x))]$ is strictly convex and differentiable on $\tau \ge 0$ with unique minimizer $\tau_*$ satisfying $\delta(\mathcal{D}(f, x)) \le \inf_{\tau \ge 0} J(\tau; \partial f(x))$ (Proposition 4.1, Recipe 4.1, Lemmas C.1-C.2, pp. 16-17, 37-40), and when $f$ is a norm on $\mathbb{R}^d$, the Gaussian Poincaré inequality yields the nonasymptotic reverse error bound $0 \le \left(\inf_{\tau \ge 0} J(\tau; \partial f(x))\right) - \delta(\mathcal{D}(f, x)) \le \frac{2\sup\{\|s\| : s \in \partial f(x)\}}{f(x/\|x\|)}$ (Theorem 4.3, Eq. 4.3, p. 17; Appendix C.2, pp. 40-41). Specializing yields the two-sided $\ell_1$ descent-cone bound $\psi(s/d) - \frac{2}{\sqrt{sd}} \le \frac{\delta(\mathcal{D}(\|\cdot\|_1, x))}{d} \le \psi(s/d)$ (Proposition 4.5, Eqs. 4.4-4.6), the Marčenko-Pastur Schatten 1-norm limit $\frac{\delta(\mathcal{D}(\|\cdot\|_{S_1}, X(r,m,n)))}{mn} \to \psi(\rho, \nu)$ (Proposition 4.7, Eqs. 4.7-4.9), and closed-form statistical dimensions for self-dual cones ($\delta(C) = d/2$, Proposition 3.2), $s$-saturated $\ell_\infty$ descent cones ($d - s/2$, Proposition 3.3), circular cones ($d\sin^2\alpha + O(1)$, Proposition 3.4), and Weyl-chamber permutahedron normal and descent cones $\delta(\mathcal{N}(\mathcal{P}(x), x)) = H_d = \sum_{i=1}^d i^{-1}$ and $\delta(\mathcal{D}(\|\cdot\|_{\mathcal{P}(y_0)}, x_0)) = d - H_d$ (Propositions 3.5 and 9.1, Appendix D.4).

supports Source: Living on the edge: phase transitions in convex programs with random data · Locator: Section 3.2-3.5, pp. 14-16, Table 3.1, Propositions 3.2-3.5; Section 4, pp. 16-19, Proposition 4.1, Recipe 4.1, Theorem 4.3, Propositions 4.5 & 4.7; Section 9, pp. 29-30, Proposition 9.1; Appendices C-D, pp. 37-45

⚠️ Curated Limitations & Negative Results

The exact conic kinematic formula and Theorem I/II/III/8.1 phase transition bounds require rotational invariance (Haar distribution on $O(d)$ or i.i.d. standard Gaussian matrices $A \in \mathbb{R}^{m \times d}$) and noiseless affine constraints $z_0 = A x_0$ or $z_0 = x_0 + U y_0$.
For the $\ell_1$ descent cone at an $s$-sparse vector in $\mathbb{R}^d$, the Theorem 4.3 / Proposition 4.5 error estimate $\frac{2}{\sqrt{sd}}$ for the normalized statistical dimension $\delta(\mathcal{D}(\|\cdot\|_1, x))/d$ is tight when $s \ge \sqrt{d} + 1$ but becomes loose in the ultrasparse regime $s \le \sqrt{d}$ (Section 4.3, p. 18; Section 10.1.2, p. 32).
Primary-source typographical audit of `arXiv:1303.6672v2`: (1) Proposition 3.3 (p. 14) writes $\mathcal{D}(\|\cdot\|_\infty, x) = d - \frac{1}{2}s$ in the theorem display, omitting the statistical dimension symbol $\delta(\cdot)$ on the left-hand side (which is written as $\delta(\mathcal{D}(\|\cdot\|_\infty, x)) = d - \frac{1}{2}s$ in the proof sketch five lines below); (2) Figure 5.1 caption (p. 20, line 3) writes 'projection $\Pi_C(g)$ of a standard normal vector $g$ onto $K$' instead of 'onto $C$'; (3) Appendix D.4 Equation (D.12) text (p. 45) writes $\mathrm{H}_d := \sum_{k=1}^d i^{-1}$ with summation index $k$ and summand $i^{-1}$; and (4) Appendix F Proof of Proposition 10.2 (p. 49) writes $\mathbb{S}^d$ instead of $\mathbb{S}^{d-1}$ in line 3, $\mathbb{B}^{d-1}$ instead of $\mathbb{B}^d$ in the final three displays, and cites (3.3) instead of (3.5) in the concluding line.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:LassoRegression` Lasso Regression	related_match	Characterizes the exact two-sided phase transition threshold m = delta(D(\|\|.\|\|_1, x_0)) and O(sqrt(d)) transition width of l_1-regularized sparse linear recovery.
`AIO:DimensionalityReduction` Dimensionality Reduction	broad_match	Establishes a conic integral-geometry framework for phase transitions across regularized low-dimensional linear inverse problems, convex demixing programs, and conic linear programs.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`almt2014-living-edge-pdf`	Living on the edge: phase transitions in convex programs with random data Dennis Amelunxen, Martin Lotz, Michael B. McCoy, Joel A. Tropp	primary paper full_text	ID: https://doi.org/10.1093/imaiai/iau005 sha256:ae1904fa8ac1…
`almt2014-living-edge-abs`	Living on the edge: phase transitions in convex programs with random data Dennis Amelunxen, Martin Lotz, Michael B. McCoy, Joel A. Tropp	primary paper abstract_only	ID: https://arxiv.org/abs/1303.6672 sha256:9ee1099daf1b…
`almt2014-living-edge-crossref`	Living on the edge: phase transitions in convex programs with random data Dennis Amelunxen, Martin Lotz, Michael B. McCoy, Joel A. Tropp	primary paper abstract_only	ID: https://doi.org/10.1093/imaiai/iau005 sha256:320d3c44e886…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T02:02:00Z

Updated: 2026-10-19T02:02:00Z

Source File: data/curated/ConicStatisticalDimensionIntrinsicVolumeConcentrationAndPhaseTransitions.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories