Living on the edge: Phase transitions in convex programs with random data

Motivation

A phase transition is a sharp change in the character of a computational problem as its parameters vary. Recent research suggests that phase transitions emerge in many random convex optimization problems from mathematical signal processing and computational statistics; for example, see [DT09b, Sto09, OH10, CSPW11, DGM13, MT14b]. This paper proves that the locations of these phase transitions are determined by geometric invariants associated with the mathematical programs. Our analysis provides the first complete account of transition phenomena in random linear inverse problems, random demixing problems, and random cone programs.

This serves as a model for data acquisition: we interpret $\bm{z}_{0}$ as a collection of $m$ independent linear measurements of the unknown $\bm{x}_{0}$. The compressed sensing problem requires us to identify $\bm{x}_{0}$ given only the measurement vector $\bm{z}_{0}$ and the realization of the measurement matrix $\bm{A}$. When the number $m$ of measurements is smaller than the ambient dimension $d$, we cannot solve this inverse problem unless we take advantage of the prior knowledge that $\bm{x}_{0}$ is sparse.

What is the probability of success? For a given pair $(s,m)$ of parameters, can we estimate the probability that (1.2) succeeds or fails?

Does a phase transition exist? Is there a simple curve $m=\psi(s)$ that separates the parameter space into regions where (1.2) is very likely to succeed or to fail?

Where is the edge of the phase transition? Can we find a formula for the location of this threshold between success and failure?

How wide is the transition region? For a given sparsity level $s$ and ambient dimension $d$, how big is the range of $m$ where the probability of success and failure are comparable?

Why does the transition exist? Is there a geometric explanation for the phase transition in compressed sensing? Can we export this reasoning to understand other problems?

There is an extensive body of work dedicated to these questions and their relatives. See the books [EK12, FR13] for background on compressed sensing in general. Section 10 outlines the current state of knowledge about phase transitions in convex optimization methods for signal processing. In spite of all this research, a complete explanation of these phenomena is lacking. The goal of this paper is to answer the questions we have posed.

2. Notation

The polar cone $C^{\circ}$ is always closed and convex.

Conic geometry and phase transitions

In the theory of convex analysis, convex cones take over the central role that subspaces perform in linear algebra [HUL93, p. 90]. In particular, we can use convex cones to express the optimality conditions for a convex program [HUL93, Part VII]. When a convex optimization problem includes random data, the optimality conditions may involve random convex cones. Therefore, the study of random convex optimization problems leads directly to questions about the stochastic geometry of cones.

In sympathy with these prior works, we study random convex optimization problems by considering the conic formulation of the optimality conditions. In contrast, we have developed a new technical argument to study the probability that the conic optimality conditions hold. Our approach depends on exact formulas from the field of conic integral geometry [SW08, Chap. 6.5]. In this context, the general idea of using integral geometry is due to Donoho [Don06b] and Donoho & Tanner [DT09a]. The specific method in this paper was proposed in [MT14b], but we need to install additional machinery to prove that phase transitions occur.

Sections 2.1–2.4 outline the results we need from conic integral geometry, along with our contributions to this subject. We apply this theory in Sections 2.5 and 2.6 to study some random optimization problems. We conclude with a summary of our main results in Section 2.7.

Let us begin with a beautiful and classical problem from the field of conic integral geometry:

What is the probability that a randomly rotated convex cone shares a ray with a fixed convex cone?

As we will discuss, this is the key question we must answer to understand phase transition phenomena in convex optimization problems with random data.

It turns out that there is an exact formula for the probability that a randomly rotated convex cone shares a ray with a fixed convex cone. Moreover, in $d$ dimensions, we only need $d+1$ numbers to summarize each cone. This wonderful result is called the conic kinematic formula [SW08, Thm. 6.5.6]. We record the statement here, but you should not focus on the details at this stage; Section 5 contains a more thorough presentation.

For each $k=0,1,2,\dots,d$, the geometric functional $v_{k}$ maps a closed convex cone to a nonnegative number, called the $k$th intrinsic volume of the cone.

The papers [AB12, MT14b] have recognized that the conic kinematic formula is tailor-made for studying random instances of convex optimization problems. Unfortunately, this approach suffers a serious weakness: We do not have workable expressions for the intrinsic volumes of a cone, except in the simplest cases. This paper provides a way to make the kinematic formula effective. To explain, we need to have a closer look at the conic intrinsic volumes.

2. Concentration of intrinsic volumes and the statistical dimension

The conic intrinsic volumes, introduced in Fact 2.1, are the fundamental geometric invariants of a closed convex cone. They do not depend on the dimension of the space in which the cone is embedded, nor on the orientation of the cone within that space. For an analogy in Euclidean geometry, you may consider similar quantities defined for compact convex sets, such as the usual volume, the surface area, the mean width, and the Euler characteristic [Sch93].

Figure 2.2 displays the distribution of intrinsic volumes for a particular cone; you can see that the sequence has a sharp peak at its mean value. Our work establishes a remarkable new fact about conic geometry:

For every closed convex cone, the distribution of conic intrinsic volumes concentrates sharply around its mean value.

This result is our main technical achievement; Theorem 6.1 contains a precise statement.

Because of the concentration phenomenon, the mean value of the distribution of conic intrinsic volumes serves as a summary for the entire distribution. This insight leads to the central definition of the paper.

The statistical dimension of a general convex cone is the statistical dimension of its closure.

In fact, the statistical dimension is a canonical extension of the dimension of a linear subspace to the class of convex cones! Section 5.6 provides technical justification for the latter point, while Sections 3, 4, and 5 establish various properties of the statistical dimension.

3. The approximate kinematic formula

We can simplify the conic kinematic formula, Fact 2.1, by exploiting the concentration of intrinsic volumes.

The quantity $a_{\eta}:=\sqrt{8\log(4/\eta)}$. For example, $a_{0.01}<7$ and $a_{0.001}<9$.

In Section 7, we derive Theorem I along with some more precise results.

Theorem I says that two randomly rotated cones are likely to share a ray if and only if the total statistical dimension of the two cones exceeds the ambient dimension. This statement is in perfect sympathy with the analogous result for random subspaces. We extract the following lesson:

We can assign a dimension $\delta(C)$ to each convex cone $C$. For problems in conic integral geometry, the cone behaves much like a subspace with approximate dimension $\delta(C)$.

In Sections 2.5 and 2.6, we use Theorem I to prove that a large class of random convex optimization problems always exhibits a phase transition, and we demonstrate that the statistical dimension describes the location of the phase transition.

4. Calculating the statistical dimension

The statistical dimension arises from deep considerations in conic integral geometry, and we rely on this connection to prove that phase transitions occur in random convex optimization problems. There is an alternative formulation that is often useful for calculating the statistical dimension of specific cones.

The proof of Proposition 2.4 appears in Section 5.5. The argument requires a classical result called the spherical Steiner formula [SW08, Thm. 6.5.1].

The metric characterization of the statistical dimension provides a surprising link between two perspectives on random convex optimization problems: our approach based on integral geometry and the alternative approach based on Gaussian process theory. Indeed, the formula (2.2) is closely related to the definition of another summary parameter for convex cones called the Gaussian width; see Section 10.3 for more information. This connection allows us to perform statistical dimension calculations by adapting methods [RV08, Sto09, OH10, CRPW12] developed for the Gaussian width.

We undertake this program in Sections 3 and 4 to estimate the statistical dimension for several important families of convex cones. Although the resulting formulas are not substantially novel, we prove for the first time that the error in these calculations is negligible. Our contribution to this analysis forms a critical part of the rigorous computation of phase transitions.

5. Regularized linear inverse problems with a random model

The function $f$ is called a regularizer, and the formulation (2.4) is called a regularized linear inverse problem. To illustrate the kinds of regularizers that arise in practice, we highlight two familiar examples.

This approach was proposed by Chen et al. [CDS01], motivated by work in geophysics [CM73, SS86].

Suppose that $\bm{X}_{0}$ is a low-rank matrix, and we have acquired a vector of measurements of the form $\bm{z}_{0}=\mathscr{A}(\bm{X}_{0})$, where $\mathscr{A}$ is a linear operator. This process is equivalent with (2.3). We can look for low-rank solutions to the linear inverse problem by minimizing the Schatten 1-norm:

This method was proposed in [RFP10], based on ideas from control [MP97] and optimization [Faz02].

We say that the regularized linear inverse problem (2.4) succeeds at solving (2.3) when the convex program has a unique minimizer $\widehat{\bm{x}}$ that coincides with the true unknown; that is, $\widehat{\bm{x}}=\bm{x}_{0}$. To develop conditions for success, we introduce a convex cone associated with the regularizer $f$ and the unknown $\bm{x}_{0}$.

The descent cones of a proper convex function are always convex, but they may not be closed. The descent cones of a smooth convex function are always halfspaces, so this concept inspires the most interest when the function is nonsmooth.

To characterize when the optimization problem (2.4) succeeds, we write the primal optimality condition in terms of the descent cone; cf. [RV08, Sec. 4] and [CRPW12, Prop. 2.1].

Let $f$ be a proper convex function. The vector $\bm{x}_{0}$ is the unique optimal point of the convex program (2.4) if and only if $\mathcal{D}(f,\bm{x}_{0})\cap\operatorname{null}(\bm{A})=\{\bm{0}\}.$

Figure 2.3 illustrates the geometry of this optimality condition. Despite its simplicity, this result forges a crucial link between the convex optimization problem (2.4) and the theory of conic integral geometry.

5.2. Linear inverse problems with random data

The kinematic formula, Fact 2.1, gives an exact expression for the probability that (2.4) succeeds under the random model for $\bm{A}$. By invoking the approximate kinematic formula, Theorem I, we reach a simpler result that allows us to identify a sharp transition in performance as the number $m$ of measurements varies.

The quantity $a_{\eta}:=\sqrt{8\log(4/\eta)}$.

Under minimal assumptions, Theorem II proves that we always encounter a phase transition when we use the regularized formulation (2.4) to solve the linear inverse problem with random measurements. The transition occurs where the number of measurements equals the statistical dimension of the descent cone: m=\delta\big{(}\mathcal{D}(f,\bm{x}_{0})\big{)}. The shift from failure to success takes place over a range of about $O(\sqrt{d})$ measurements.

There are several reasons that the conclusions of Theorem II are significant. The first implication provides evidence about the minimum amount of information we need before we can use the convex method (2.4) to solve the linear inverse problem. The second implication tells us that we can solve the inverse problem reliably once we have acquired this quantum of information. Furthermore, Theorem II allows us to compare the performance of different regularizers because we know exactly how many measurements each one requires.

Nevertheless, the prior literature offers no hint that the statistical dimension determines the location of the phase transition for every convex regularizer. In fact, we can derive a variant of the failure condition from Theorem II by supplementing Rudelson & Vershynin’s approach with a polarity argument. A similar observation appeared in Stojnic’s paper [Sto13] after our work was released.

5.3. Computer experiments

In both examples, the theoretical prediction of Theorem II coincides almost perfectly with the 50% success isocline. Furthermore, the phase transition takes place over a range of $O(\sqrt{d})$ values of $m$, as promised. Although Theorem II does not explain why the transition region tapers at the bottom-left and top-right corners of each plot, we have established a more detailed version of Theorem I that allows us to predict this phenomenon as well; see Section 7.1.

6. Demixing problems with a random model

In other words, we seek structured vectors $\bm{x}$ and $\bm{y}$ that are consistent with the observation $\bm{z}_{0}$. This approach requires the side information $g(\bm{y}_{0})$, so a Lagrangian formulation is sometimes more natural in practice [MT14b, Sec. 1.2.4]. Here are two concrete examples of the demixing program (2.8) that are adapted from the literature.

This approach for demixing sparse signals is sometimes called morphological component analysis [SDC03, SED05, ESQD05, BMS06].

This demixing problem is called the rank–sparsity decomposition [CSPW11].

We say that the convex program (2.8) for demixing succeeds when it has a unique solution $(\widehat{\bm{x}},\widehat{\bm{y}})$ that coincides with the vectors that generate the observation: $(\widehat{\bm{x}},\widehat{\bm{y}})=(\bm{x}_{0},\bm{y}_{0})$. As in the case of a linear inverse problem, we can express the primal optimality condition in terms of descent cones; cf. [MT14b, Lem. 2.4].

Let $f$ and $g$ be proper convex functions. The pair $(\bm{x}_{0},\bm{y}_{0})$ is the unique optimal point of the convex program (2.8) if and only if $\mathcal{D}(f,\bm{x}_{0})\cap(-\bm{U}\mathcal{D}(g,\bm{y}_{0}))=\{\bm{0}\}$.

Figure 2.5 depicts the geometry of this optimality condition. The parallel with Fact 2.8, the optimality condition for a regularized linear inverse problem, is striking. Indeed, the two conditions coalesce when the function $g$ in (2.8) is the indicator of an appropriate affine space. This observation shows that the regularized linear inverse problem (2.4) is a special case of the convex demixing problem (2.8).

6.2. Demixing with a random model for coherence

Our goal is to understand the prospects for solving the demixing problem with a convex program of the form (2.8). To that end, we use randomness to model the favorable case where the two structures do not interact with each other. More precisely, we choose the matrix $\bm{U}$ to be a random orthogonal basis. Under this assumption, Theorem I delivers a sharp transition in the performance of the optimization problem (2.8).

The quantity $a_{\eta}:=\sqrt{8\log(4/\eta)}$.

This theorem follows immediately when we combine the optimality condition, Fact 2.12, with the kinematic bound, Theorem I. To simplify the formulas, we invoke the rotational invariance of the statistical dimension, which follows from either Definition 2.2 or Proposition 2.4. ∎

Under minimal assumptions, Theorem III establishes that there is always a phase transition when we use the convex program (2.8) to solve the demixing problem under the random model for $\bm{U}$. The optimization is effective if and only if the total statistical dimension of the two descent cones is smaller than the ambient dimension $d$.

6.3. Computer experiments

Once again, we see that the theoretical curve of Theorem III coincides almost perfectly with the empirical 50% success isocline. The width of the transition region is $O(\sqrt{d})$. Although Theorem III does not predict the tapering of the transition in the top-left and bottom-right corners, the discussion in Section 7.1 exposes the underlying reason for this phenomenon.

7. Contributions

It takes a substantial amount of argument to establish the existence of phase transitions and to calculate their location for specific problems. Some parts of our paper depend on prior work, but much of the research is new. We conclude this section with a summary of our contributions. Section 10 contains a detailed discussion of the literature; additional citations appear throughout the presentation.

This paper contains foundational research in conic integral geometry:

We define the statistical dimension as the mean value of the distribution of intrinsic volumes, and we argue that the statistical dimension canonically extends the linear dimension of a subspace to the class of convex cones. (Definition 2.2 and Section 5.6)

We demonstrate that the metric characterization of the statistical dimension coincides with the intrinsic characterization, and we use this connection to establish some properties of the statistical dimension. The statistical dimension is also related to the Gaussian width. (Definition 2.2, Proposition 2.4, Proposition 3.1, Proposition 5.12, and Proposition 10.2)

We prove that the distribution of intrinsic volumes of a convex cone concentrates sharply about the statistical dimension of the cone. (Theorem 6.1)

The concentration of intrinsic volumes leads to an approximate version of the kinematic formula for cones. This result uses the statistical dimension to bound the probability that a randomly rotated cone shares a ray with a fixed cone. (Theorem I and Theorem 7.1)

Building on this foundation, we establish a number of applied results concerning phase transition phenomena in convex optimization problems with random data:

We prove that a regularized linear inverse problem with random measurements must exhibit a phase transition as the number of random measurements increases. The location and width of the transition are controlled by the statistical dimension of a descent cone. Our work confirms and extends the earlier analyses based on polytope angles [Don06a, DT09a, KXAH11, XH12] and those based on Gaussian process theory [RV08, Sto09, OH10, CRPW12]. (Theorem II, Theorem 7.1, and Proposition 9.1)

The paper [MT14b] proposes convex programming methods for decomposing a superposition of two structured, randomly oriented vectors into its constituents. We prove that these methods exhibit a phase transition whose properties depend on the total statistical dimension of two descent cones. This work confirms a conjecture [MT14b, Sec. 4.2.2] about the existence of phase transitions in these problems. (Theorem III and Theorem 7.1)

The work [AB12] studies cone programs with random affine constraints. Building on this analysis, we show that a cone program with random affine constraints displays a phase transition as the number of constraints increases. We can predict the transition using the statistical dimension of the cone. (Theorem 8.1)

Section 4 contains a recipe for estimating the statistical dimension of a descent cone. The approach is based on ideas from [CRPW12, App. C], but we provide the first proof that it delivers accurate estimates. This result rigorously explains why the bounds computed in [Sto09, OH10] closely match observed phase transitions. (Theorem 4.3 and Propositions 4.5 and 4.7)

The approximate kinematic formula also delivers information about the probability that a face of a polytope maintains its dimension under a random projection. This argument clarifies the connection between the polytope-angle approach to random linear inverse problems and the approach based on Gaussian process theory. (Section 10.1.1)

As an added bonus, we provide the final ingredient needed to resolve a series of conjectures [DMM09a, DJM13, DGM13] about the coincidence between the minimax risk of denoising and the location of phase transitions in linear inverse problems. Indeed, Oymak & Hassibi [OH13] have recently shown that the minimax risk is equivalent with the statistical dimension of an appropriate cone, and our results prove that the phase transition occurs at precisely this spot. See Section 10.4 for further details.

Calculating the statistical dimension

Section 2 demonstrates that the statistical dimension is a fundamental quantity in conic integral geometry. Through the approximate kinematic formula, Theorem I, the statistical dimension drives phase transitions in random linear problems and random demixing problems. A natural question, then, is how we can determine the value of the statistical dimension for a specific cone.

This section explains how to compute the statistical dimension directly for a few basic cones. In Section 3.1, we present some useful properties of the statistical dimension. Sections 3.2–3.5 contain some example calculations, in increasing order of difficulty. See Table 3.1 for a summary. We discuss general descent cones later, in Section 4.

The statistical dimension has a number of valuable properties. These facts provide useful tools for making computations, and they strengthen the analogy between the statistical dimension of a cone and the linear dimension of a subspace.

Intrinsic formulation. The statistical dimension is defined as

where $v_{0},\dots,v_{d}$ denote the conic intrinsic volumes. (See Section 5.1.)

Gaussian formulation. The statistical dimension satisfies

Spherical formulation. An equivalent expression is

Polar formulation. The statistical dimension can be expressed in terms of the polar cone:

Mean-squared-width formulation. Another alternative formulation reads

Rotational invariance. The statistical dimension does not depend on the orientation of the cone:

Subspaces. For each subspace $L$, the statistical dimension satisfies $\delta(L)=\dim(L)$.

Complementarity. The sum of the statistical dimension of a cone and that of its polar equals the ambient dimension:

In particular, the statistical dimension is invariant under embedding:

The relation (3.8) generalizes the rule $\dim(L\times M)=\dim(L)+\dim(M)$ for linear subspaces $L$ and $M$.

We verify the equivalence of the intrinsic volume formulation (3.1) and the metric formulation (3.2) below in Proposition 5.12. It is possible to establish the remaining facts on the basis of either (3.1) or (3.2). In Appendix B.4, we use the metric characterization (3.2) to prove the rest of the proposition. Many of these elementary results have appeared in [Sto09, CRPW12] in a slightly different form.

2. Self-dual cones

We say that a cone $C$ is self-dual when $C^{\circ}=-C$. Self-dual cones are ubiquitous in the theory and practice of convex optimization. Here are three important examples:

For a self-dual cone, the computation of the statistical dimension is particularly simple; cf. [CRPW12, Cor. 3.8]. The first three entries in Table 3.1 follow instantly from this result.

Just observe that \delta(C)=\tfrac{1}{2}\big{[}\delta(C)+\delta(C^{\circ})\big{]}=\tfrac{1}{2}d. The first identity holds because of the self-dual property of the cone and the rotational invariance (3.6) of statistical dimension. The second equality follows from the complementarity law (3.7). ∎

We may now calculate the statistical dimension:

The first identity follows from the direct product law (3.8) and the rotational invariance (3.6) of the statistical dimension. The next relation depends on the rule for subspaces and the calculation of the statistical dimension of the nonnegative orthant from Section 3.2. ∎

4. Circular cones

We can obtain an accurate expression for the statistical dimension of a circular cone by expressing the spherical formulation (3.3) in spherical coordinates and administering a dose of asymptotic analysis.

The statistical dimension of a circular cone satisfies

The error term is approximately equal to $\cos(2\alpha)$. See Figure 4.1[left] for a plot of (3.9).

Turn to Appendix D.1 for the proof, which seems to be novel. Even though the formula in Proposition 3.4 is simple, it already gives an excellent approximation in moderate dimensions. See [MT14a, Sec. 6.3] or [MHWG13] for refinements of Proposition 3.4 that appeared after our work.

5. Normal cones of a permutahedron

Figure 3.1 displays two signed permutahedra along with the normal cone at a vertex of each one.

We can develop an exact formula for the statistical dimension of the normal cone of a nondegenerate permutahedron. In Section 9, we use this calculation to study a signal processing application proposed in [CRPW12, p. 812].

The proof of Proposition 3.5 appears in Appendix D.4. The argument relies on the intrinsic formulation (3.1) of the statistical dimension, and it illustrates some deep connections between conic geometry and classical combinatorics.

The statistical dimension of a descent cone

Theorems II and III allow us to locate the phase transition for a class of convex optimization problems with random data. To apply these results, however, we must be able to compute the statistical dimension for the descent cone of a convex function. In this section, we describe a recipe that delivers an accurate estimate for the statistical dimension of a descent cone.

There is a classical duality between descent cones and subdifferentials [Roc70, Chap. 23]. As a consequence, we can convert questions about the statistical dimension of a descent cone into questions about the subdifferential.

where $\bm{g}\sim\textsc{normal}(\bm{0},\mathbf{I})$. We have the upper bound

Furthermore, the function $J$ is strictly convex, continuous at $\tau=0$, and differentiable for $\tau\geq 0$. It achieves its minimum at a unique point.

The inequality (4.2) generalizes some specific arguments from [CRPW12, App. C], and it is easy to establish. We use the polarity relation (3.4) to compute the statistical dimension:

Indeed, the statistical dimension of the descent cone equals the statistical dimension of its closure, which can be expressed as a double polar. The second identity uses (3.4) and the fact that polarity is an involution on closed convex cones. The third identity follows from the fact that, under our technical assumptions, the polar of the descent cone is the cone generated by the subdifferential [Roc70, Cor. 23.7.1]; see Appendix B.1 for details. The last identity holds because the distance to a union is the infimal distance to any one of its members. To reach (4.2), we pass the expectation through the infimum.

The analytic properties of the function $J$ are new, and they demand substantial effort. Lemma C.2 in Appendix C.1 contains the proof of the remaining claims. ∎

Proposition 4.1 suggests a method for studying the statistical dimension of a descent cone: Minimize the function $J$ by setting its derivative to zero. We formalize this approach in Recipe 4.1. In Section 4.3 and 4.4, we discuss some examples where this recipe is provably effective.

2. An error estimate for the descent cone recipe

The papers [Sto09, OH10] contain computational evidence that the ideas behind Recipe 4.1 lead to accurate upper bounds in some special cases. Among the major contributions of this paper is an error estimate that explains why the descent cone recipe works so well. This result is an essential ingredient in our method for locating the phase transition of a random convex program. Indeed, we need this theorem to ensure that we can calculate the statistical dimension of a descent cone correctly.

where the function $J$ is defined in (4.1).

The proof of Theorem 4.3 is technical in nature, so we defer the details to Appendix C.2. The application of this result requires some care because many different vectors $\bm{x}$ can generate the same subdifferential $\partial f(\bm{x})$ and hence the same descent cone $\mathcal{D}(f,\bm{x})$. From this class of vectors, we ought to select one that maximizes the value $f(\bm{x}/\left\|{\bm{x}}\right\|)$.

In an independent paper that appeared shortly after this work was released, Foygel & Mackey [FM14] developed another error bound for the descent cone recipe. These two results operate under different assumptions, and the two bounds are effective in different regimes. It remains an open question to find an optimal error estimate for Recipe 4.1.

See Figure 4.1[center] for a plot of the function (4.5).

Proposition 4.5 is a direct consequence of Recipe 4.1 and the error bound in Theorem 4.3. See Appendix D.2 for details of the proof; Appendix A.2 explains the numerical aspects.

Let us emphasize the following consequences of Proposition 4.5. When the number $s$ of nonzeros in the vector $\bm{x}$ is proportional to the ambient dimension $d$, the error in the statistical dimension calculation (4.4) is vanishingly small relative to the ambient dimension. When $\bm{x}$ is sparser, it is more appropriate to compare the error with the statistical dimension itself. Thus,

4. Descent cones of the Schatten 1-norm

When we wish to solve an inverse problem whose unknown is a low-rank matrix, we often use the Schatten 1-norm $S_{1}$ as a regularizer, as in (2.6) and (2.10). The following result gives an asymptotically exact expression for the statistical dimension of the descent cone of the $S_{1}$ norm at a low-rank matrix. Together with Theorems II and III, this proposition allows us to identify the exact location of the phase transition for $S_{1}$ regularized inverse problems as the ambient dimension goes to infinity.

Consider a sequence $\{\bm{X}(r,m,n)\}$ of matrices where $\bm{X}(r,m,n)$ has rank $r$ and dimension $m\times n$ with $m\leq n$. Suppose that $r,m,n\to\infty$ with limiting ratios $r/m\to\rho\in(0,1)$ and $m/n\to\nu\in(0,1]$. Then

The function $\psi:\times\to$ is defined as

The quantity $y:=(\nu-\rho\nu)/(1-\rho\nu)$, and the limits of the integral are $a_{\pm}:=1\pm\sqrt{y}$. The integral kernel $\varphi_{y}$ is a probability density supported on $[a_{-},a_{+}]$:

The optimal value of $\tau$ in (4.8) satisfies the stationary equation

See Figure 4.1[right] for a visualization of the curve (4.8) as function of $\rho$ for several choices of $\nu$. The operator $\vee$ returns the maximum of two numbers.

See Appendix D.3 for a proof of Proposition 4.7. Appendix A.2 contains details of the numerical calculation.

The literature contains several papers that, in effect, contain loose upper bounds for the statistical dimension of the descent cones of the Schatten 1-norm [RXH11, OKH11]. We single out the work [OH10] of Oymak & Hassibi, which identifies an empirically sharp upper bound via a laborious argument. The approach here is more in the spirit of the weak upper bound in [CRPW12, App. C], but our argument leads to the asymptotically correct estimate.

Conic integral geometry and the statistical dimension

To prove that the statistical dimension controls the location of phase transitions in random convex optimization problems, we rely on methods from conic integral geometry, the field of mathematics concerned with geometric properties of convex cones that remain invariant under rotations, reflections, and embeddings. Here are some of the guiding questions in this area:

What is the probability that a random unit vector lies at most a specified distance from a fixed cone?

What is the probability that a randomly rotated cone shares a ray with a fixed cone?

The theory of conic integral geometry offers beautiful and precise answers to these questions, phrased in terms of a set of geometric invariants called conic intrinsic volumes.

In Section 5.1, we formally introduce the intrinsic volumes of a cone and we compute the intrinsic volumes of some basic cones. We state the key facts about intrinsic volumes in Section 5.2. Sections 5.3 and 5.4 contain more advanced formulas from conic integral geometry, which are essential tools in our approach to phase transitions. In Section 5.5, we establish the equivalence of the two characterizations of the statistical dimension, given in Definition 2.2 and Proposition 2.4. Section 5.6 explains why the statistical dimension is canonical.

The material in this section is adapted from the book [SW08, Sec. 6.5] and the dissertation [Ame11]. The foundational research in this area is due to Santaló [San76, Part IV]. Modern treatments depend on the work of Glasauer [Gla95, Gla96]. In these sources, the theory is presented in terms of spherical geometry, rather than in terms of conical geometry. As noted in [AB12], the two approaches are equivalent, but the conic viewpoint provides simpler formulas and has other benefits that are revealed by deeper structural investigations.

We begin with the definition of the intrinsic volumes of a convex cone. Recall that a cone is polyhedral if it can be written as the intersection of a finite number of halfspaces. Polyhedral cones are automatically closed and convex.

For a polyhedral cone, it is clear that the sequence of intrinsic volumes forms a probability distribution on $\{0,1,2,\dots,d\}$. The definition also delivers insight about several fundamental examples.

Apply the intrinsic formulation (3.1) of the statistical dimension to confirm that $\delta(L_{j})=j$.

It can be shown that this limit does not depend on the approximating sequence.

Let us warn the reader that the projection formula in Definition 5.1 breaks down for a general closed convex cone because the limiting process does not preserve facial structure. To learn more about the construction behind Definition 5.4, see the book [SW08, Sec. 6.5], the thesis [Ame11], or the paper [MT14a]. The spherical Steiner formula, Fact 5.7, provides an alternative geometric interpretation of the intrinsic volumes.

2. Properties of conic intrinsic volumes

The intrinsic volumes of a closed convex cone satisfy a number of important relationships that we outline here.

Distribution. The intrinsic volumes describe a probability distribution on $\{0,1,\dots,d\}$:

Polarity. The intrinsic volumes reverse under polarity:

Gauss–Bonnet formula. When $C$ is not a subspace,

The facts (5.1), (5.2), and (5.3) are drawn from [SW08, Sec. 6.5]. See [Ame11, Prop. 4.4.13] or [MT14a, Cor. 5.1] for a proof of the product rule (5.4).

3. The spherical Steiner formula

We continue with a selection of more sophisticated results from conic integral geometry. These formulas provide detailed answers, expressed in terms of conic intrinsic volumes, to the geometric questions posed at the beginning of Section 5. To state the first result, we introduce a family of geometric functions.

Basic geometric reasoning reveals that $I_{k}^{d}(\varepsilon)$ is the proportion of points on the sphere $\mathsf{S}^{d-1}$ that lie within an angle $\arccos(\sqrt{\varepsilon})$ of the subspace $L_{k}$. Our terminology derives from the approximate geographical fact that the tropics lie within a fixed angle ($23^{\circ}\,26^{\prime}$) of the equator; the usual term regularized incomplete beta function is longer and less evocative.

The core fact in conic integral geometry is the spherical Steiner formula [Hot39, Wey39, Her43, All48, San50], which describes the fraction of points on the sphere that lie at most a fixed angle from a closed convex cone.

The spherical Steiner formula often serves as the definition of conic intrinsic volumes. The formula (5.6) can also be derived from the definition here. For a proof of Fact 5.7 in the spirit of this work, see [SW08, Thm. 6.5.1] or [MT14a, Prop. 3.4].

4. The conic kinematic formula

Next, we present another major result from the theory of conic integral geometry. This statement involves partial sums of the intrinsic volumes.

The two types of tail functionals are related through the following interlacing inequality.

We establish Proposition 5.9 in Appendix E.

With this notation, we can present a modern formulation of the conic kinematic formula, which provides an exact expression for the probability that a randomly oriented convex cone has a nontrivial intersection with a fixed convex cone.

The compact notation here disguises the equivalence between (5.9) and Fact 2.1. To verify this point, expand the half-tail functional using (5.8) and apply the direct product rule (3.8). See [SW08, p. 261] for a proof of Fact 5.10.

5. Characterizations of the statistical dimension

In Section 2, we presented two different ways of thinking about the statistical dimension. Definition 2.2, offers an intrinsic characterization in terms of the conic intrinsic volumes, and it links the statistical dimension to the theory of conic integral geometry. Proposition 2.4 provides a metric characterization that leads to powerful tools for calculating the statistical dimension for specific cones. The following result applies the spherical Steiner formula to verify that the two formulations coincide.

The Gaussian formulation (3.2) and the spherical formulation (3.3) of statistical dimension coincide, so

We have used integration by parts to express the expectation as an integral of tail probabilities. The Steiner formula (5.6) and the definition (5.5) of the tropic function allow us to write the probability as a sum:

where $L_{k}$ is an arbitrary $k$-dimensional subspace. The last identity follows from elementary geometric reasoning. ∎

6. The statistical dimension is canonical

The intrinsic characterization of the statistical dimension, Definition 2.2, has a significant consequence from the point of view of integral geometry. We summarize the ideas for the benefit of geometers; other readers may prefer to skip this material.

Valuation I. For the trivial cone, $v(\{\bm{0}\})=0$.

Valuation II. If $C,K\in\mathscr{C}_{d}$ and $C\cup K\in\mathscr{C}_{d}$, then $v(C\cup K)+v(C\cap K)=v(C)+v(K)$.

Continuity. If $C_{i}\to C$ in $\mathscr{C}_{d}$, then $\lim_{i\to\infty}v(C_{i})\to v(C)$.

Continuous, rotation-invariant valuations are natural geometric measures defined on convex cones. Many of the valuations that arise in conic geometry are also localizable, which is a subtle technical property [SW08, p. 254].

In particular, each intrinsic volume $v_{k}$ is a continuous, rotation-invariant, localizable valuation on the set of closed convex cones. It follows from the intrinsic formulation (3.1) that the statistical dimension inherits these technical properties. It is known that each continuous, rotation-invariant, and localizable valuation on $\mathscr{C}_{d}$ is determined by the values it takes on linear subspaces; see [Gla95, Satz 4.2.2], [Gla96, Thm. 5], or [SW08, Thm. 6.5.4]. Therefore,

The statistical dimension $\delta$ is the unique continuous, rotation-invariant, localizable valuation on the set $\mathscr{C}_{d}$ of closed convex cones that satisfies $\delta(L)=\dim(L)$ for each subspace $L$.

In other words, the statistical dimension canonically extends the linear dimension to the class of closed convex cones.

The long-standing spherical Hadwiger conjecture states that the condition of localizability is unnecessary here. More precisely, the conjecture posits that every continuous and rotation-invariant valuation on the set of closed convex cones can be expressed as a linear combination of the conic intrinsic volumes. For a discussion of the spherical Hadwiger conjecture, see the works [McM93, p. 976], [KR97, Sec. 11.5], and [SW08, p. 263]. The conjecture currently stands open for $d\geq 4$.

Intrinsic volumes concentrate at the statistical dimension

The main technical result in this paper describes a new property of conic intrinsic volumes: The intrinsic volumes of a closed convex cone concentrate near the statistical dimension of the cone on a scale determined by the statistical dimension. This phenomenon is depicted in Figure 2.2.

Let $C$ be a closed convex cone. Define the transition width

The tail functional $t_{k}$ is defined in (5.7). The operator $\wedge$ returns the minimum of two numbers.

See Section 6.1 for a discussion of Theorem 6.1. In Section 6.2 and 6.3, we summarize the intuition behind the proof, and we follow up with the technical details. Later, Sections 7–9 highlight applications in conic geometry, optimization theory, and signal processing. The follow-up work [MT14a] contains some improvements on Theorem 6.1.

Theorem 6.1 states that the sequence $\{t_{k}(C):k=0,1,2,\dots,d\}$ of tail functionals drops from one to zero near the statistical dimension $\delta(C)$, and the transition occurs over a range of $O(\omega(C))$ indices. Owing to the fact (5.1) that the intrinsic volumes form a probability distribution, we must conclude that the intrinsic volumes $v_{k}(C)$ are all negligible in size, except for those whose index $k$ is close to the statistical dimension $\delta(C)$. We learn that the intrinsic volumes of a convex cone $C$ with statistical dimension $\delta(C)$ are qualitatively similar with the intrinsic volumes of a subspace with dimension about $\delta(C)$.

Theorem 6.1 contains additional information about the rate at which the tail functionals of a cone transit from one to zero. To extract this information, it helps to note the weaker inequality

We see that (6.2) and (6.3) are vacuous until $\lambda\approx 4\,\omega(C)$. As $\lambda$ increases, the function $p_{C}(\lambda)$ decays like the tail of a Gaussian random variable with standard deviation $\leq 2\sqrt{2}\,\omega(C)$. When $\lambda$ reaches $\omega^{2}(C)$, the decay slows to match the tail of an exponential random variable with mean $\leq 16$. In particular, the behavior of the tail functionals depends on the intrinsic properties of the cone, rather than the ambient dimension.

2. Heuristic proof of Theorem 6.1

where $\bm{\theta}$ is uniformly distributed on the sphere $\mathsf{S}^{d-1}$ and the tropic function $I_{k}^{d}$ is defined in (5.5).

Concentration of measure on the sphere implies that the random variable $\left\|{\smash{\bm{\Pi}_{C}(\bm{\theta})}}\right\|^{2}$ is typically very close to its expected value $\delta(C)/d$, determined by (3.3). Thus, the left-hand side of (6.5) is very close to one when $\varepsilon d<\delta(C)$ and very close to zero when $\varepsilon d>\delta(C)$.

As for the right-hand side of (6.5), recall that the tropic function $I_{k}^{d}(\varepsilon)$ is the proportion of points on the sphere within a distance of $\sqrt{1-\varepsilon}$ from a fixed $k$-dimensional subspace. Once again, concentration of measure ensures that $I_{k}^{d}(\varepsilon)$ is close to zero when $k<\varepsilon d$ and close to one when $k>\varepsilon d$. Therefore, the sum on the right-hand side of (6.5) is approximately equal to the tail functional $t_{\varepsilon d}(C)$.

Combining these two observations, we conclude that the sequence $\{t_{k}(C):k=0,1,2,\dots,d\}$ of tail functionals makes a sharp transition from one to zero when $k\approx\delta(C)$. It remains to make this reasoning rigorous and to determine the range of $k$ over which the transition takes place.

3. Proof of Theorem 6.1

For all integers $0\leq k\leq d$, the tropic function $I_{k}^{d}(k/d)\geq 0.3$.

We begin by expressing the tail functional $t_{k_{+}}(C)$ in terms of the probability that a spherical variable lies near the cone $C$.

The first identity is the definition (5.7) of the tail function. To reach the second inequality, we inspect the definition (5.5) to see that $I_{k}^{d}(\varepsilon)$ is a decreasing function of $k$ when the other parameters are fixed. In the third line, we invoke the Steiner formula (5.6) to rewrite the first sum. The bound for the second sum follows and the definition (5.7) of the tail functional and from Lemma 6.2 seeing that $\varepsilon=k_{+}/d$.

The last inequality depends on the fact that $\varepsilon=k_{+}/d$ and the definition (6.3) of $k_{+}$. In other words, the tail functional is dominated by the probability that a random point on the sphere is close to the cone.

To estimate the probability in (6.7), we need a tail bound for the squared norm of the projection of a spherical variable onto a cone. This result is encapsulated in the following lemma. The approach is more or less standard, so we defer the details to Appendix E.

Introducing (6.8) into (6.7), we reach the upper bound (6.3) on the tail functional.

To develop the lower bound (6.2) on the tail functional $t_{k_{-}}(C)$, we use a polarity argument. Note that

The first identity is the definition (5.7) of the tail functional $t_{k_{-}}(C)$. The second relation holds because of the fact (5.2) that polarity reverses intrinsic volumes, and the last part relies on (5.7) and the property (5.1) that the intrinsic volumes sum to one. Owing to the complementarity law (3.7) and the definition (6.2) of $k_{-}$,

Therefore, we may apply (6.3) to obtain an upper bound on the tail functional $t_{d-k_{-}+1}(C^{\circ})$. Substitute this bound into (6.9) to establish the lower bound on the tail functional $t_{k_{-}}(C)$ stated in (6.2).

Approximate kinematic bounds

We are now prepared to establish an approximate version of the conic kinematic formula, expressed in terms of the statistical dimension. Most of the applied results in this paper ultimately depend on this theorem. The proof combines the exact kinematic formula (5.9) with the concentration of intrinsic volumes, guaranteed by Theorem 6.1.

The functions $p_{C}$ and $p_{K}$ are defined by the expression (6.1).

We discuss Theorem 7.1 below in Section 7.1. The proof appears in Section 7.2. In Section 7.3, we derive Theorem I from a similar, but slightly easier argument. The follow-up work [MT13] contains an improvement on Theorem 7.1.

Theorem 7.1 has an attractive interpretation. The first statement (7.1) shows that a randomly oriented subspace with codimension $m$ is unlikely to share a ray with a fixed cone $C$, provided that the codimension $m$ is larger than the statistical dimension $\delta(C)$ of the cone. When the codimension $m$ is smaller than the statistical dimension $\delta(C)$, the subspace and the cone are likely to share a ray.

The transition in behavior expressed in (7.1) takes place when the codimension $m$ of the subspace changes by about $\omega(C)=\sqrt{\delta(C)\wedge\delta(C^{\circ})}$. This point explains why the empirical success curves taper in the corners of the graphs in Figure 2.4. Indeed, on the bottom-left side of each panel, the relevant descent cone is small; on the top-right side of each panel, the descent cone is large, so its polar is small. In these regimes, the result (7.1) shows that the phase transition must occur over a narrow range of codimensions.

The second statement (7.2) provides analogous results for the probability that a randomly oriented cone shares a ray with a fixed cone. This event is unlikely when the total statistical dimension of the two cones is smaller than the ambient dimension; it is likely to occur when the total statistical dimension exceeds the ambient dimension.

For the case of two cones, it is harder to analyze the size of the transition region. Since the probability bounds in (7.2) are controlled by the sum $p_{C}(\lambda)+p_{K}(\lambda)$, we can only be certain that the probability estimate depends on the larger of the two quantities. It follows that the width of the transition does not exceed the larger of $\omega(C)=\sqrt{\delta(C)\wedge\delta(C^{\circ})}$ and $\omega(K)=\sqrt{\delta(K)\wedge\delta(K^{\circ})}$. This observation is sufficient to explain why the empirical success curves taper at the top-left and bottom-right of the graphs in Figure 2.6. Indeed, these are the regions where one of the descent cones is small and the polar of the other descent cone is small.

2. Proof of Theorem 7.1

Let us begin with the first set (7.1) of results, concerning the probability that a randomly oriented subspace intersects a fixed cone along a ray. Consider the first implication, which operates when $m\geq\delta(C)+\lambda$. The implication clearly holds when $C$ is a subspace. When $C$ is not a subspace, the Crofton formula (5.10) shows that

where the inequality depends on the interlacing result, Proposition 5.9. The concentration of intrinsic volumes, Theorem 6.1, demonstrates that the tail functional satisfies the bound

This completes the first bound. The second result, which holds when $m\leq\delta(C)-\lambda$, follows from a parallel argument.

The conic kinematic formula is required for the second set (7.2) of results, which concern the probability that a randomly oriented cone intersects a fixed cone nontrivially. Consider the situation where $\delta(C)+\delta(K)\leq d-2\lambda$. The kinematic formula (5.9) yields

where the inequality follows from the interlacing result, Proposition 5.9.

We rely on a simple lemma to bound the tail functional of the product in terms of the individual tail functionals.

Let $C$ and $K$ be closed convex cones. Then

The proof appears in Appendix E. See the follow-up work [MT14a] for an improvement on this result.

Since the tail functionals are weakly decreasing, our assumption that $\delta(C)+\delta(K)\leq d-2\lambda$ implies that

Theorem 6.1 delivers an upper bound of $p_{C}(\lambda)+p_{K}(\lambda)$ for the right-hand side. Introduce these bounds into the probability inequality (7.3) to complete the proof of the first statement in (7.2). The second result follows from an analogous argument. ∎

3. Proof of Theorem I

The simplified kinematic bound of Theorem I involves an argument similar with the proof of Theorem 7.1. First, assume that $\delta(C)+\delta(K)\leq d-\lambda$. As before, the kinematic formula (5.9) and the interlacing result, Proposition 5.9, ensure that

The product rule (3.8) for cones shows that $\delta(C\times K)=\delta(C)+\delta(K)\leq d-\lambda$, so the implication (6.3) in Theorem 6.1 yields

Substitute the inequality (7.5) into the kinematic bound (7.4). Then make the change of variables $\lambda\mapsto a_{\eta}\sqrt{d}$, where $a_{\eta}:=\sqrt{8\log(4/\eta)}$, to obtain the estimate

This establishes the first part of Theorem I. The argument for the second part follows the same pattern. ∎

Application: Cone programs with random constraints

The concentration of intrinsic volumes has far-reaching consequences for the theory of optimization. This section describes a new type of phase transition phenomenon that appears in a cone program with random affine constraints. We begin with a theoretical result, and then we exhibit some numerical examples that confirm the analysis.

A cone program is a convex optimization problem with the following structure:

In addition to their flexibility and modeling power, cone programs enjoy effective algorithms and a crisp theory. We refer to [BTN01] for further details.

The cone program (8.1) can exhibit several interesting behaviors. Let us remind the reader of the terminology. A point $\bm{x}$ that satisfies the constraints $\bm{A}\bm{x}=\bm{b}$ and $\bm{x}\in C$ is called a feasible point, and the cone program is infeasible when no feasible point exists. The cone program is unbounded when there exists a sequence $\{\bm{x}_{k}\}$ of feasible points with the property $\left\langle{\bm{u}},\ {\bm{x}_{k}}\right\rangle\to-\infty$.

Our theory allows us analyze the properties of a random cone program. It turns out that the number $m$ of affine constraints controls whether the cone program is infeasible or unbounded.

The function $p_{C}$ is defined by the expression (6.1).

Amelunxen & Bürgisser [AB12, Thm. 1.3] have shown that the intrinsic volumes of the cone $C$ control the properties of the random cone program (8.1):

We apply Theorem 6.1 to see that the tail functional $t_{m+1}(C)$ is extremely close to one when the number $m$ of constraints is smaller than the statistical dimension $\delta(C)$. Likewise, $t_{m}(C)$ is extremely close to zero when the number $m$ of constraints is larger than the statistical dimension. We omit the details, which are analogous with the proof of Theorem 7.1. ∎

2. A numerical example

We have conducted a computer experiment to compare the predictions of Theorem 8.1 with the empirical behavior of a generic cone program. For this purpose, we study some random second-order cone programs. In each case, the ambient dimension $d=396$, and we consider three options for the cone $C$ in (8.1):

The angles satisfy $\tan^{2}(\alpha_{1})=\tfrac{1}{5}$ and $\tan^{2}(\alpha_{2})=\tfrac{1}{7}$ and $\tan^{2}(\alpha_{3})=\tfrac{1}{11}$. Using the product rule (3.8) and the integral expression (D.1) for the statistical dimension of a circular cone, numerical quadrature yields

Theorem 8.1 indicates that a cone program (8.1) with the cone $C_{i}$ and generic constraints is likely to be feasible when the number $m$ of affine constraints is smaller than $\delta(C_{i})$; it is likely to be infeasible when the number $m$ of affine constraints is larger than $\delta(C_{i})$.

We can test this prediction numerically. For each $i=1,2,3$ and each m\in\big{\{}1,2,3,\dots,\big{[}\tfrac{1}{3}d\big{]}\big{\}}, we perform the following steps 50 times:

Use the Matlab package CVX to solve the cone program (8.1) with $C=C_{i}$.

Report failure if CVX declares the cone program infeasible.

For each $i=1,2,3$, Figure 8.1 displays the empirical success probability, along with a logistic fit (Appendix A.3). We also mark the theoretical estimate for the location of the phase transition, which equals the statistical dimension $\delta(C_{i})$. Table 8.1 reports the discrepancy between the theoretical and empirical behaviors.

Application: Vectors from lists?

This section describes a situation where our results prove that a particular linear inverse problem does not provide an effective way to recover a structured vector. Indeed, a significant contribution of our theory, which has no parallel in the current literature, is that we can obtain negative results as well as positive results.

To solve this problem, Chandrasekaran et al. propose to use a convex regularizer $f$ that exploits the information in $\bm{y}_{0}$. They consider the Minkowski gauge of the permutahedron (3.10) generated by $\bm{y}_{0}$.

and they frame the regularized linear inverse problem

It is natural to ask how many linear measurements we need to be able to solve this inverse problem reliably. Our theory allows us to answer this question decisively when the measurements are random.

Proposition 9.1 yields the depressing assessment that we need a near-complete set of linear measurements to resolve our uncertainty about the ordering of the vector. Nevertheless, we do not need all of the measurements. It would be interesting to understand how much the situation improves for vectors with many duplicated entries.

This result follows from Fact 2.8 and the kinematic bound (7.1) in Theorem 7.1 as soon as we compute the statistical dimension of the descent cone of the regularizer $\left\|{\cdot}\right\|_{\mathscr{P}(\bm{y}_{0})}$ at the point $\bm{x}_{0}$. By construction, the unit ball of $\left\|{\cdot}\right\|_{\mathscr{P}(\bm{y}_{0})}$ coincides with the permutahedron $\mathscr{P}(\bm{y}_{0})$, which equals $\mathscr{P}(\bm{x}_{0})$ by permutation invariance. Therefore,

The second identity holds because a closed descent cone coincides with the polar of the normal cone of the sublevel set; see Appendix B.1 for details. Figure 3.1 illustrates the corresponding facts about signed permutahedra. To compute the statistical dimension, we apply the complementarity law (3.7) to see that

where the second relation follows from Proposition 3.5. Apply the kinematic result (7.1) for subspaces, and invoke (6.4) to simplify the error bound $p_{C}(\lambda)$. ∎

We present a computer experiment that confirms our pessimistic analysis. Fix the ambient dimension $d=100$. Set $\bm{x}_{0}=(1,2,\dots,100)$ and $\bm{y}_{0}=\bm{x}_{0}^{\downarrow}$. For each $m=85,86,\dots,100$, we repeat the following procedure 50 times:

Use the Matlab package CVX to solve the linear inverse problem (9.1).

Declare success if the solution $\widehat{\bm{x}}$ satisfies $\left\|{\smash{\widehat{\bm{x}}-\bm{x}_{0}}}\right\|\leq 10^{-5}$.

Related work

To conclude the body of the paper, we place our work in the context of the literature on geometric analysis of random convex optimization problems. We trace four lines of thought on this subject. The first draws from the theory of polytope angles; the second involves conic integral geometry; the third is based on comparison inequalities for Gaussian processes; and the last makes a connection with statistical decision theory. Our results have some overlap with earlier work, but our discovery that the sequence of conic intrinsic volumes concentrates at the statistical dimension allows us to resolve several subtle but important questions that have remained open until now.

The theory of polytope angles dates to the work of Schläfli in the 1850s [Sch50b]. In pioneering research, Vershik & Sporyshev [VS86] used polytope-angle calculations to analyze random convex optimization problems. They were able to estimate the average number of steps that the simplex algorithm requires to solve a linear program with random constraints as the number of decision variables tends to infinity. This research inspired further theoretical work on the neighborliness of random polytopes [VS92, AS92, BH99]. More recently, Donoho [Don06b] and Donoho & Tanner [DT05, DT09a, DT10a, DT10b] have used similar ideas to study specific regularized linear inverse problems with random data. The papers [XH11, KXAH11] contain some additional work in this direction. Let us offer a short, qualitative summary of this research.

Donoho [Don06b] analyzed the performance of the convex program (1.2) for solving the compressed sensing problem described in Section 1.1. In the asymptotic regime where the number $s$ of nonzeros is proportional to the ambient dimension $d$, he obtained a lower bound $m\geq\psi(s)$ on the number $m$ of Gaussian measurements that are sufficient for the optimization to succeed (the weak threshold). Numerical experiments [DT09b] suggest that this bound is sharp, but the theoretical analysis in [Don06b] falls short of establishing that a phase transition actually exists and identifying its location rigorously. Finite-dimensional results with a similar flavor appear in [DT10b].

Donoho & Tanner [DT09a] have also made a careful study of the behavior of the convex program (1.2) in the asymptotic regime where the sparsity $s\ll d$. In this case, they succeeded in proving that weak and strong thresholds exist, and they obtained exact formulas for the thresholds. More precisely, at the computed thresholds, they show that the probability of success jumps from one to $1-\varepsilon$, where $\varepsilon$ is positive. Although these results do not ensure that certain failure awaits on the other side of the threshold curve, they do establish that the behavior changes.

Suppose that we have acquired the vector $\bm{z}_{0}=\bm{A}\bm{x}_{0}$, where $\bm{A}$ is a standard normal matrix and $\bm{x}_{0}$ is a vector with $s+1$ nonzero entries. We may assume that $\left\|{\bm{x}_{0}}\right\|_{1}=1$. Define the cross-polytope $P:=\{\bm{x}:\left\|{\bm{x}}\right\|_{1}\leq 1\}$, and note that the sparse vector $\bm{x}_{0}$ lies in an $s$-dimensional face $F$ of the cross-polytope $P$. Donoho shows that (1.2) succeeds if and only if $\bm{A}F$ is an $s$-dimensional face of the projected polytope $\bm{A}P$. In other words, we must determine whether a face of the polytope “survives” a random projection. Donoho [Don06b] and Donoho & Tanner [DT09a] use the polytope-angle theory to address this question.

1.2. Commentary

The analysis of structured inverse problems by means of polytope-angle computations has led to some striking conclusions, but this approach has inherent limitations. First, the method is restricted to polyhedral cones, which means that it is silent about the behavior of many important regularizers, including the Schatten 1-norm. Second, it requires detailed bounds on all angles of a given polytope (equivalently, all the intrinsic volumes of the normal cones of the polytope), which means that it is difficult to extend beyond a few highly symmetric examples. For this reason, most of the existing results are asymptotic in nature. Third, because of the intricacy of the calculations, this research has produced few definitive results of the form “the probability of success jumps from zero to one at a specified location.”

2. Conic intrinsic volumes

Research on polytope angles has largely been supplanted by spherical and conical integral geometry [Gla95, SW08]. Several authors have independently recognized the power of this approach for analyzing random instances of convex optimization problems.

Amelunxen [Ame11] and Amelunxen & Bürgisser [AB13, AB12] have shown that conic geometry offers an elegant way to perform average-case and smoothed analysis of conic optimization problems. Their work requires detailed computations of conic intrinsic volumes, which can make it challenging to apply to particular cases. We can simplify some of their techniques using the new fact, Theorem 6.1, that intrinsic volumes concentrate at the statistical dimension. Theorem 8.1 is based on their research.

McCoy & Tropp [MT14b] have used conic intrinsic volumes to study the behavior of regularized linear inverse problems with random measurements and regularized demixing problems under a random model. This approach leads to both upper and lower bounds for weak and strong phase transitions in a variety of problems. As with Amelunxen’s work [Ame11], this research depends on detailed computations of conic intrinsic volumes. As a consequence, it was not possible to rigorously locate the phase transition, nor was there any general theory to inform us that phase transitions must exist in general. By combining the ideas from [MT14b] with Theorem 7.1, the present work reaches stronger conclusions than [MT14b].

3. Analysis based on Gaussian process theory

The work we have discussed so far depends on various flavors of integral geometry. There is a completely different technique for analyzing linear inverse problems with random data that depends on a comparison inequality [Gor85, Thm. 1.4] for Gaussian processes due to Gordon. Gordon [Gor88] explains how to use this comparison to find accurate bounds on the probability that a randomly oriented subspace intersects a subset of the sphere.

None of these authors has examined the failure condition for random linear inverse problems, but we have observed that it is possible to obtain such a result by incorporating a polarity argument. We can also extend the Gaussian process approach to obtain a success condition for demixing, but it does not yield a failure condition for these problems. After this paper was written, Stojnic [Sto13] developed some related results.

The Gaussian width $w(C)$ is proportional to the classical mean width [Sch93, p. 42] of the set $C\cap\mathsf{S}^{d-1}$. The width $w(C)$ also has a numerical relationship with the statistical dimension $\delta(C)$, which is not surprising in view of the mean-squared-width formulation (3.5).

The lower bound in (10.1) requires little more than Jensen’s inequality. The upper bound depends on some concentration arguments. See Appendix F for a short proof.

3.2. Commentary

This link yields many insights. For example, all of the statistical dimension calculations here lead to analogous estimates for the Gaussian width. In particular, Theorem 4.3 provides the first accurate lower bounds for the Gaussian width of a descent cone. Furthermore, we can use the intrinsic characterization of the statistical dimension, Definition 2.2, to study cones that are not accessible to the metric characterization, Proposition 2.4. For instance, consider the results for permutahedra in Proposition 3.5.

Despite these connections, we did not arrive at the statistical dimension by squaring the Gaussian width. Rather, Definition 2.2 emerges from Theorem 6.1, our result that the conic intrinsic volumes concentrate. To travel from this definition to the Gaussian width, we must take several long steps: Proposition 5.12 leads to the metric characterization of the statistical dimension, Proposition 2.4; we apply Proposition 3.1 to obtain the mean-squared-width formulation (3.5) of statistical dimension; and Proposition 10.2 sandwiches the mean-squared-width formulation by the Gaussian width.

4. Minimax denoising

Several authors [DMM09a, DJM13, DGM13] have remarked on the power of statistical decision theory to empirically predict the location of the phase transition in a regularized linear inverse problem with random data. For the compressed sensing problem, two recent papers [BM12, BLM13a] provide a rigorous explanation for this coincidence. But there is no general theory that illuminates the connection between these two settings. Our work and a recent paper of Oymak & Hassibi [OH13] together resolve this issue. In short, Oymak & Hassibi show that the minimax risk for denoising is essentially the same as the statistical dimension, while our research proves that a phase transition must occur at the statistical dimension. Let us elaborate.

A classical problem in statistics is to estimate a target vector $\bm{x}_{0}$ given an observation of the form $\bm{z}_{0}=\bm{x}_{0}+\sigma\bm{g}$ where $\bm{g}$ is a standard normal vector and $\sigma$ is an unknown variance parameter. When the unknown vector $\bm{x}_{0}$ has specified properties (e.g., sparsity), we can often construct a convex regularizer $f$ that promotes this type of structure [CRPW12]. A natural estimation procedure is to solve the convex optimization problem

The regularization parameter $\gamma>0$ negotiates a tradeoff between the structural penalty and the data fidelity term. One way to assess the performance of the estimator (10.2) is the minimax MSE risk,The usual definition of the minimax risk involves an additional supremum over a class of distributions on the target $\bm{x}_{0}$. In many applications, the symmetries in the regularizer $f$ allow a straightforward reduction to the case of a fixed target $\bm{x}_{0}$. See [OH13, Sec. 6.4]. defined as

In other words, the risk identifies the relative mean-square error for the best choice of tuning parameter $\gamma$ at the worst choice of the noise variance $\sigma^{2}$.

The papers [DMM09a, DJM13, DGM13] examine several regularizers $f$ where the minimax risk empirically predicts the performance of the linear inverse problem (2.4) with a Gaussian measurement matrix $\bm{A}$. The authors of this research propound a conjecture that may be expressed as follows.

The order notation here should be interpreted heuristically.

Together, our paper and the recent paper [OH13] settle Conjecture 10.3 in the nonasymptotic setting for many regularizers of interest. Indeed, Oymak & Hassibi [OH13] prove that

Combining these two results, we conclude that, in some generality, the minimax risk coincides with the location of the phase transition in a regularized linear inverse problem with random measurements.

Appendix A Computer experiments

We confirm the predictions of our theoretical analysis by performing computer experiments. This appendix contains some of the details of our numerical work. All experiments were performed using the CVX package [GB13] for Matlab with the default settings in place.

In the compressed sensing example, we fix the ambient dimension $d=100$. For each $m=1,2,3,\dots,100$ and each $s=1,2,3,\dots,100$, we repeat the following procedure $50$ times:

Solve (2.5) to obtain an optimal point $\widehat{\bm{x}}$.

Declare success if $\left\|{\widehat{\bm{x}}-\bm{x}_{0}}\right\|\leq 10^{-5}$.

All random variables are drawn independently in each step and at each iteration. Figures 1.1[left] and 2.4[left] show the empirical probability of success for this procedure. We performed a similar experiment for ambient dimension $d=600$. In this case, we iterate over $s\in\{1,7,13,\dots,595\}$ and $m\in\{0,6,12,\dots,600\}$; Figure 1.1[right] displays a subset of this data.

In the compressed sensing experiment, 50 trials suffice to estimate the probability because of the concentration phenomenon established in Theorem II. Furthermore, the experiment does not appear particularly sensitive to the success tolerance $10^{-5}$ above. Limited tests confirm that tolerances with orders of magnitude $10^{-3}$ through $10^{-7}$ give essentially the same results. The value $10^{-5}$ was chosen as a stringent condition that would be insensitive to numerical errors produced by the CVX software package. Nevertheless, we encountered some numerical problems in the experiment with $d=600$, which led to a few spurious failures in Figure 1.1[right].

We take a similar approach in the low-rank matrix recovery problem. Fix $n=30$, and consider square $n\times n$ matrices. For each rank $r=1,2,\dots,n$ and each $m=1,29,58,87,\dots,n^{2}$, we repeat the following procedure $50$ times:

If $r\geq\lceil\sqrt{m}\rceil+1$, declare failure because the number of degrees of freedom in an $n\times n$ rank-$r$ matrix exceeds the number $m$ of measurements.

Draw a rank-$r$ matrix $\bm{X}_{0}=\bm{Q}_{1}\bm{Q}_{2}^{T}$, where $\bm{Q}_{1}$ and $\bm{Q}_{2}$ are independent $n\times r$ matrices with orthonormal columns, drawn uniformly from an appropriate Stiefel manifold [Mez07].

Solve (2.6) to obtain an optimal point $\widehat{\bm{X}}$.

As before, all random variables are chosen independently. Readers interested in reproducing this experiment should be aware that this procedure required nearly one month to execute on a desktop workstation. Figure 2.4[right] displays the results of this experiment. Once again, the probability of success and failure is relatively insensitive to the precise tolerance $10^{-5}$ used above.

A.2. Statistical dimension curves

We have encountered some numerical stability problems evaluating (4.4) when the proportional sparsity $\rho=s/d$ is close to zero or one. Similarly, there are sometimes difficulties with (4.7) when the proportional rank $\rho=r/m$ or the aspect ratio $\nu=m/n$ are close to zero or one. Nevertheless, relatively simple code based on this approach is usually reliable. Software is available online [McC14].

A.3. Logistic regression

Several of the experiments involve fitting the logistic function

Appendix B Background on conic geometry

Sections B.1–B.3 below provide some important facts from convex geometry that we will use liberally. Section B.4 establishes the properties of the statistical dimension listed in Proposition 3.1.

The normal cone of a convex set $E$ at a point $\bm{x}$ is defined as

The polar of a descent cone has some attractive duality properties. First, the polar of a descent cone coincides with the normal cone of a sublevel set:

If the descent cone is closed, we can apply the bipolar theorem [Roc70, Thm. 14.1] to transfer the polar in (B.1) from the normal cone to the descent cone. Second, there is a duality between descent cones and subdifferentials. Recall that

Assuming that the subdifferential $\partial f(\bm{x})$ is nonempty, compact, and does not contain the origin, the result [Roc70, Cor. 23.7.1] provides that

The expression $\tau\cdot\partial f(\bm{x})$ represents dilation of the subdifferential by a factor $\tau$. The relation (B.2) offers a powerful tool for computing the statistical dimension of a descent cone, as described in Proposition 4.1. Related identities hold under weaker technical conditions [Roc70, Thm. 23.7]; these results can be used to establish the formula (4.2) without the compactness assumption.

B.2. Euclidean projections onto sets

The projection takes a well-defined value because the norm is strictly convex. Let us note some properties of the distance and projection maps. First, the function $\operatorname{dist}(\cdot,E)$ is convex [Roc70, p. 34]. Next, the maps $\bm{\pi}_{E}$ and $\mathbf{I}-\bm{\pi}_{E}$ are nonexpansive with respect to the Euclidean norm [Roc70, Thm. 31.5 et seq.]:

As a consequence, the projection $\bm{\pi}_{E}$ is continuous, and the distance function is 1-Lipschitz with respect to the Euclidean norm:

The squared distance is differentiable everywhere, and the derivative satisfies

This point follows from [RW98, Thm. 2.26].

B.3. Euclidean projections onto cones

The decomposition (B.6) yields the Pythagorean identity

The squared norm of the projection has a nice regularity property, which follows from a short argument based on (B.5), (B.6), and (B.8):

The relation (B.10) is easy to check directly.

B.4. Proof of Proposition 3.1

Let us verify the elementary properties of the statistical dimension delineated in Proposition 3.1. These results follow quickly from the orthogonal decomposition (B.7) and basic facts about a standard normal random vector.

The intrinsic formulation (3.1) simply restates Definition 2.2.

The Gaussian formulation (3.2) follows from Proposition 2.4 or the equivalent Proposition 5.12.

To derive the spherical formulation (3.3) from (3.2), we introduce the spherical decomposition $\bm{g}=R\,\bm{\theta}$, where $R:=\left\|{\smash{\bm{g}}}\right\|$ is a chi random variable with $d$ degrees of freedom that is independent from the spherical variable $\bm{\theta}$. By nonnegative homogeneity and independence,

The polar identity (3.4) is a direct consequence of the distance formula (B.8), which implies that $\left\|{\smash{\bm{\Pi}_{C}(\bm{g})}}\right\|=\operatorname{dist}(\bm{g},C^{\circ})$.

The supremum formulation (3.5) also follows from (3.2). Using the Pythagorean decomposition (B.7), we observe that

The second inequality is immediate from the definition (1.4) of the polar cone. Choose $\bm{y}$ to be the unit vector in the direction $\bm{\Pi}_{C}(\bm{g})$ to see that

Square the expression, and take the expectation to complete the argument.

The rotational invariance property (3.6) follows immediately from the fact that a standard normal vector is rotationally invariant.

To compute the statistical dimension of a subspace, note that the Euclidean projection of a standard normal vector onto a subspace has the standard normal distribution supported on that subspace, so its expected squared norm equals the dimension of the subspace.

The complementarity law (3.7) follows from the Pythagorean identity (B.7).

We obtain the direct product rule (3.8) from the observation (B.10) that projection splits over a direct product, coupled with the fact that projecting a standard normal vector onto each of two orthogonal subspaces results in two independent standard normal vectors.

Finally, we verify the monotonicity law. Polarity reverses inclusion, so $K^{\circ}\subset C^{\circ}$. Using the polarity identity (3.4) twice, we obtain

Appendix C Theoretical results on descent cones

This appendix contains the theoretical analysis that permits us to calculate the statistical dimension of a descent cone. In particular, we prove Proposition 4.1 and establish Theorem 4.3.

The function $J_{\bm{u}}$ satisfies the lower bound

In particular, $J_{\bm{u}}$ attains its minimum value in the compact interval $[0,2\left\|{\bm{u}}\right\|/b]$.

The function $J_{\bm{u}}$ is continuously differentiable, and the derivative takes the form

The right derivative $J^{\prime}_{\bm{u}}(0)$ exists, and $J^{\prime}_{\bm{u}}(0)=\lim_{\tau\downarrow 0}J^{\prime}_{\bm{u}}(\tau)$.

Furthermore, the map $\bm{u}\mapsto J_{\bm{u}}^{\prime}(\tau)$ is Lipschitz for each $\tau\geq 0$:

These claims all take some work. Along the way, we also need to establish some auxiliary results to justify the main points.

Convexity. For $\tau>0$, convexity follows from the representation

By way of justification, the distance to a closed convex set is a convex function [Roc70, p. 34], the perspective transformation [HUL93, Sec. IV.2.2] of a convex function is convex, and the square of a nonnegative convex function is convex by a direct calculation.

Continuity. The representation (C.6) shows that the function $J_{\bm{u}}$ is continuous for $\tau>0$ because the distance to a convex set is a Lipschitz function, as stated in (B.4). To obtain continuity at $\tau=0$, simply note that

Indeed, each point in $\varepsilon S$ is bounded in norm by $\varepsilon B$, so the projection $\bm{\pi}_{\varepsilon S}(\bm{u})$ admits the same bound. Continuity implies that $J_{\bm{u}}$ is convex on the entire domain $\tau\geq 0$.

Attainment of minimum. Assume that $\tau\geq\left\|{\bm{u}}\right\|/b$. Then

Square this relation to reach (C.2). As a consequence, for all $\tau>2\left\|{\bm{u}}\right\|/b$, we have $J_{\bm{u}}(\tau)>J_{\bm{u}}(0)=\left\|{\bm{u}}\right\|^{2}$. If follows that any minimizer of $J_{\bm{u}}$ must occur in the compact interval $[0,2\left\|{\bm{u}}\right\|/b]$. Since $J_{\bm{u}}$ is continuous, it attains its minimal value in this set.

Differentiability. We obtain the derivative from a direct calculation:

The first relation follows from (C.6). The second relies on the formula (B.5) for the derivative of the squared distance. To obtain the last relation, we express the squared distance as $\left\|{\smash{\bm{u}-\bm{\pi}_{\tau S}(\bm{u})}}\right\|^{2}$.

Right derivative at zero. The right derivative $J^{\prime}_{\bm{u}}(0)$ exists, and the limit formula holds because $J_{\bm{u}}$ is a proper convex function that is continuous on $[0,\infty]$ and differentiable on $(0,\infty)$; see [Roc70, Thm. 24.1].

Continuity of the derivative. The expression (C.3) already implies that $J^{\prime}_{\bm{u}}$ is continuous for $\tau>0$ because the projection onto a convex set is continuous [RW98, Thm. 2.26]. Continuity of the derivative at zero follows from the limit formula for the right derivative at zero.

Bound for the derivative. Given the formula (C.3), it is easy to control the derivative when $\tau>0$:

We obtain the estimate for $\tau=0$ by taking the limit.

Lipschitz property. We obtain the Lipschitz bound (C.5) from (C.3) after some effort. Fix $\tau>0$. The optimality condition [HUL93, Thm. III.3.1.1] for a projection onto a closed convex set implies that

The last relation relies on the fact (B.3) that the map $\mathbf{I}-\bm{\pi}_{\tau S}$ is nonexpansive. Reversing the roles of $\bm{u}$ and $\bm{y}$ in the last calculation, we see that

Combining this estimate with the expression (C.3) for the derivative, we reach

For $\tau=0$, the result follows when we take the limit as $\tau\downarrow 0$. ∎

With this result at hand, we are prepared to prove a lemma that confirms the remaining claims from Proposition 4.1.

The function $J$ is strictly convex, continuous at $\tau=0$, and differentiable for $\tau>0$. It attains its minimum at a unique point. Furthermore,

For $\tau=0$, we interpret $J^{\prime}(\tau)$ as a right derivative.

These properties will follow from Lemma C.1, and we continue using the notation from this result.

Continuity at zero. Imitating the continuity argument in Lemma C.1, we find that

Convexity. The function $J$ is convex for $\tau\geq 0$ because it is an average of functions of the form $J_{\bm{g}}$, each of which is convex.

Strict convexity. We argue by contradiction. We have shown that $J$ is convex and differentiable. If $J$ were not strictly convex, its graph would contain a linear segment. More precisely, there would be numbers $0\leq\rho<\tau$ and $\eta\in(0,1)$ for which

The convexity of $J_{\bm{g}}$ ensures that, for each $\bm{g}$, the bracket on the right-hand side is no smaller than the bracket on the left-hand side. Therefore, the relation (C.8) holds if and only if the two brackets are equal almost surely with respect to the Gaussian measure. But note that

The strict inequality depends on the strict convexity of the square, together with the fact that the infimum is strictly positive. On account of (B.4), the squared distance to a convex set is a continuous function, so there is an open ball around the origin where the same relation holds. That is, for some $\varepsilon>0$,

Attainment of minimum. The median of the random variable $\left\|{\smash{\bm{g}}}\right\|$ does not exceed $\sqrt{d}$. Therefore, when $\tau b\geq\sqrt{d}$, we have

The first inequality follows from the law of total expectation, and the second depends on (C.2). In particular, $J(\tau)>J(0)=d$ when $\tau>2b^{-1}\sqrt{d}$. Thus, any minimizer of $J$ must occur in the compact interval \big{[}0,2b^{-1}\sqrt{d}\big{]}. Since $J$ is continuous and strictly convex, it attains its minimum at a unique point. ∎

C.2. Error bound for descent cone calculations

In this section, we prove Theorem 4.3, which provides an error bound for Proposition 4.1. We require a standard result concerning the variance of a Lipschitz function of a standard normal vector.

Fact C.3 is a consequence of the Gaussian Poincaré inequality; see [Bog98, Thm. 1.6.4] or [Led01, p. 49].

where $f^{\circ}$ is the norm dual to $f$. Thus, $S$ is nonempty, compact, convex, and it does not contain the origin.

As in Lemmas C.1 and C.2, we introduce the functions

We establish the result by linearizing each function $J_{\bm{g}}$ around a suitable point. Lemma C.2 shows that the function $J$ attains its minimum at a unique location, so we may define

Should $\tau_{\star}=0$, we interpret $J^{\prime}_{\bm{u}}(\tau_{\star})$ as a right derivative. Replacing $\bm{u}$ by the random vector $\bm{g}$ and taking the expectation, we reach

To compute the variance of $\tau_{\bm{g}}$, we need to devise a consistent method for selecting a minimizer $\tau_{\bm{u}}$ of $J_{\bm{u}}$. Introduce the closed convex cone $K:=\operatorname{cone}(S)$, and notice that

In other words, the minimum distance to one of the sets $\tau S$ is attained at the point $\bm{\Pi}_{K}(\bm{u})$. As such, it is natural to pick a minimizer $\tau_{\bm{u}}$ of $J_{\bm{u}}$ according to the rule

The latter identity follows from the expression (C.10) for the subdifferential $S$. In light of (C.12),

We have used the fact (B.3) that the projection onto a closed convex set is nonexpansive. Fact C.3 delivers

Finally, let us turn to the remaining variance term in (C.2). We have already computed the Lipschitz bound we need for the analysis. Indeed, the inequality (C.5) states that

Another invocation of Fact C.3 delivers the estimate

To complete the proof, we combine the inequalities (C.2), (C.13), (C.14), and the fact that $e_{1}\geq 0$. This is the advertised result (4.3). ∎

Appendix D Statistical dimension calculations

First, we approximate the statistical dimension of a circular cone.

We begin with an exact integral expression for the statistical dimension of the circular cone $C=\operatorname{Circ}_{d}(\alpha)$. The spherical formulation (3.3) of the statistical dimension asks us to average the squared norm of the projection of a random unit vector $\bm{\theta}$ onto the cone. Introduce the angle $\beta:=\beta(\bm{\theta}):=\arccos(\theta_{1})$ between $\bm{\theta}$ and the first standard basis vector $(1,0,\dots,0)$. Elementary trigonometry shows that the squared norm of the projection of $\bm{\theta}$ onto the cone $C$ admits the expression

To obtain the exact statistical dimension $\delta(C)$ from (3.3), we integrate $F(\varphi)$ in polar coordinates in the usual way (cf. [SW08, Lem. 6.5.1]) to find

We can approximate the integral by a routine application of Laplace’s method [AF03, Lem. 6.2.3], which yields

To simplify the ratio of gamma functions, recall Gautschi’s inequality [OLBC10, Sec. 5.6.4]:

Combine the last three displays to reach the expression (3.9).

To obtain the more refined estimate $\cos(2\alpha)$ for the error term, one may use the fact that the intrinsic volumes of a circular cone satisfy

This formula is drawn from [Ame11, Ex. 4.4.8]. We are using the analytic extension to define the binomial coefficient. The easiest way to study this sequence is to observe the close connection with the density of a binomial random variable and to apply the interlacing result, Proposition 5.9. In the interest of brevity, we omit the details. ∎

We can compute the distance from a standard normal vector $\bm{g}$ to the dilated subdifferential as follows.

where $\operatorname{Pos}(a):=a\vee 0$ and the operator $\vee$ returns the maximum of two numbers. Indeed, we always suffer an error in the first $s$ components, and we can always reduce the magnitude of the other components by the amount $\tau$. Taking the expectation, we reach

Introduce this expression into (D.3) and normalize by the ambient dimension $d$ to reach

This expression matches the upper bound in (4.4).

Now, we need to invoke the error estimate, Theorem 4.3. An inspection of (D.4) shows that the subdifferential $\partial\left\|{\bm{x}}\right\|_{1}$ depends on the number $s$ of nonzero entries in $\bm{x}$ but not on their magnitudes. It follows from (B.2) that, up to isometry, the descent cone $\mathcal{D}(\left\|{\cdot}\right\|_{1},\bm{x})$ only depends on the sparsity $s$. Therefore, we may as well assume that $\bm{x}=(1,\dots,1,0,\dots,0)$. For this vector, $\left\|{\bm{x}/\left\|{\bm{x}}\right\|}\right\|_{1}=\sqrt{s}$. Second, the expression (D.4) for the subdifferential shows that $\left\|{\bm{u}}\right\|\leq\sqrt{d}$ for every subgradient $\bm{u}\in\partial\left\|{\bm{x}}\right\|$. Therefore, the error in the inequality (D.6) is at most $2\sqrt{d/s}$. We reach the lower bound in (4.4).

Finally, Lemma C.2 shows that the brace in (D.6) is a strictly convex, differentiable function of $\tau$ with a unique minimizer. It can be verified that the minimum does not occur at $\tau=0$. Therefore, we determine the stationary equation (4.6) by setting the derivative of the brace to zero and simplifying. ∎

D.3. Descent cones of the Schatten 1-norm

Now, we present the calculation of the statistical dimension of the descent cone of the Schatten 1-norm at a low-rank matrix. The approach is entirely similar with the argument in Appendix D.2.

Our aim is to identify the statistical dimension of the descent cone of the Schatten 1-norm at a fixed low-rank matrix. The argument here parallels the proof of Proposition 4.5, but we use classical results from random matrix theory to obtain the final expression. Our asymptotic theory demonstrates that this simplification still results in a sharp estimate.

We begin with the fixed-dimension setting. Consider an $m\times n$ real matrix $\bm{X}$ with rank $r$. Without loss of generality, we assume that $m\leq n$ and $0<r\leq m$. The Schatten 1-norm is unitarily invariant, so we can also assume that $\bm{X}$ takes the form

The subdifferential bound (4.2) for the statistical dimension of a descent cone states that

where we compute distance with respect to the Frobenius norm. The $m\times n$ matrix $\bm{G}$ has independent standard normal entries, and it is partitioned conformally with $\bm{X}$:

According to [Wat92, Ex. 2], the subdifferential of the Schatten 1-norm at $\bm{X}$ takes the form

where $\sigma_{1}(\bm{W})$ denotes the maximum singular value of $\bm{W}$. It follows that

Using the Hoffman–Wielandt Theorem [HJ90, Cor. 7.3.8], we can derive

where $\sigma_{i}(\cdot)$ is the $i$th largest singular value. Combining the last two displays and taking the expectation,

We reach a nonasymptotic bound on the statistical dimension.

It is challenging to evaluate the formula (D.10) exactly. In principle, we could accomplish this task using the joint singular value density [And84, p. 534] of the Gaussian matrix $\bm{G}_{22}$. Instead, we set up a framework in which we can use classical random matrix theory to obtain a sharp asymptotic result.

Consider an infinite sequence $\{\bm{X}(r,m,n)\}$ of matrices, where $\bm{X}(r,m,n)$ has rank $r$ and dimension $m\times n$ with $m\leq n$. For simplicity, we assume that the problem parameters $r,m,n\to\infty$ with constant ratios $r/m=:\rho\in(0,1)$ and $m/n=:\nu\in(0,1]$. The general case follows from a continuity argument. After a change of variables $\tau\mapsto\tau\sqrt{n-r}$ and a rescaling, the expression (D.9) leads to

Here, $\bm{G}$ is an $m\times n$ standard normal matrix. The matrix $\bm{Z}$ has dimension $(m-r)\times(n-r)$, and its entries are independent $\textsc{normal}(0,(n-r)^{-1})$ random variables.

Observe that the expectation in (D.11) can be viewed as a spectral function of a Gaussian matrix. We can obtain the limiting value of this expectation from a variant of the Marčenko–Pastur Law [MP67].

The limits $a_{\pm}:=1\pm\sqrt{y}$. The kernel $\varphi_{y}$ is a probability density supported on $[a_{-},a_{+}]$:

Fact D.1 is usually stated differently in the literature. The result here follows from the almost sure weak convergence of the empirical spectral density of a sample covariance matrix to the Marčenko–Pastur density [BS10, Thm. 3.6] and the almost sure convergence of the extreme eigenvalues of a sample covariance matrix [BS10, Thm. 5.8], followed by a change of variables in the integral. We omit the uninteresting details of this reduction.

Let us apply Fact D.1 to our problem. The limiting aspect ratio $y$ of the matrix $\bm{Z}$ satisfies

As $r,m,n\to\infty$, we obtain the limit, pointwise in $\tau\geq 0$,

Simplifying the latter integral and introducing it into (D.11), we reach

By itself, pointwise convergence does not imply convergence of the infimal values. The limit above follows from the fact that all of the functions involved are strictly convex. For the details, see [McC13, p. 105].

Rescaling the error estimate for (D.10), we see that the error in the normalized statistical dimension is at most $2/(n\sqrt{mr})$, which converges to zero as the parameters grow. We obtain the asymptotic result

This is the main conclusion (4.7). To obtain the stationary equation (4.9), we differentiate the brace with respect to $\tau$ and set the derivative to zero. ∎

D.4. Permutahedra and finite reflection groups

In this section, we use a deep connection between conic geometry and classical combinatorics to compute the statistical dimension of the normal cone of a (signed) permutahedron. This computation is based on the intrinsic characterization of statistical dimension in Definition 2.2, which is also restated in (3.1).

It turns out that the chambers $C_{A}$ and $C_{BC}$ coincide with the normal cones of certain permutahedra.

Suppose that the vector $\bm{x}$ has distinct entries. Then the normal cone $\mathcal{N}(\mathcal{P}(\bm{x}),\bm{x})$ is isometric to $C_{A}$ and the normal cone $\mathcal{N}(\mathcal{P}_{\pm}(\bm{x}),\bm{x})$ is isometric to $C_{BC}$.

See [HLT11, Sec. 2] or [Zie95, Ex. 7.15] for a proof of Fact D.2.

We claim that the statistical dimensions of the chambers $C_{A}$ and $C_{BC}$ can be expressed as

Let us explain how the theory of finite reflection groups allows us to deduce the expression (D.12) for the statistical dimension of the chambers. First, it follows from [BZ09] and the characterization [SW08, Eq. (6.50)] of intrinsic volumes in terms of polytope angles that

where $\mathscr{H}_{k}:=\{\bm{U}\in\mathscr{G}:\dim(\operatorname{null}(\mathbf{I}-\bm{U}))=k\}$. Define the generating polynomial of the intrinsic volumes

This polynomial is a well-studied object in the theory of finite reflection groups, and it has many applications in conic geometry as well [Ame11, Sec. 4.4]. For our purposes, we only need the relationships

These points follow immediately from (5.1) and the intrinsic formulation (3.1) of the statistical dimension.

The roots $\{\zeta_{k}:k=1,\dots,d\}$ of the polynomial $q_{\mathscr{G}}$ are called the (negative) exponents of the reflection group [CM72, Sec. 7.9]. Factoring the generating polynomial, we obtain a concise expression for the statistical dimension:

We can deduce the value of the large parenthesis because of the normalization $q_{\mathscr{G}}(1)=1$. The exponents associated with the groups $A_{d-1}$ and $BC_{d}$ are collected in [CM72, Tab. 10], from which it follows immediately that

This completes the proof of the claim (D.12).

The intrinsic volumes of chambers of finite reflection groups, and more generally of polyhedral cones, have appeared in many different contexts. For example, the papers [DK10, KS11] relate the intrinsic volumes of regions of hyperplane arrangements to the characteristic polynomial of the arrangement. This result can be used to give an alternative derivation of (D.12).

Appendix E Technical lemmas for concentration of intrinsic volumes

This appendix contains the technical results that undergird the proof of the result on concentration of intrinsic volumes, Theorem 6.1, and the approximate kinematic bound, Theorem 7.1.

First, we establish the interlacing inequality for the tail functionals. This result is a straightforward consequence of the Crofton formula (5.10).

Let $L_{d-k+1}$ be a linear subspace of dimension $d-k+1$, and let $L_{d-k}$ be a linear subspace of dimension $d-k$ inside $L_{d-k+1}$. The Crofton formula (5.10) shows that the half-tail functionals are weakly decreasing:

where the inequality follows from the containment of the subspaces. We can express the tail functional $t_{k}$ as the average of the half-tail functionals:

Therefore, $2h_{k}(C)\geq t_{k}(C)\geq 2h_{k+1}(C)$. ∎

E.2. Bounds for tropic functions

We continue with the proof of Lemma 6.2, which provides a bound on the tropic functions. This argument is based on an approximation formula from the venerable compendium of Abramowitz & Stegun [AS64, Sec. 26.5.21].

Let $X$ be a $\textsc{beta}(a,b)$ random variable. Assume that $a+b>6$ and $(a+b-1)(1-x)\geq 0.8$. Define the quantity $y$ via the formula

The function $\Phi$ represents the cumulative distribution of a standard normal random variable.

We need to show that the tropic function $I_{k}^{d}(k/d)\geq 0.3$ for all integers $k$ and $d$ that satisfy $1\leq k\leq d-1$. (The cases $k=0$ and $k=d$ are trivial.) To accomplish this goal, we represent the tropic function in terms of a beta random variable, and we apply Fact E.1 to approximate its value.

We must show that this probability is bounded above by $0.7$.

First, the mean–median–mode inequality [vdVW93] implies that the mean $k/d$ of $X$ is smaller than the median when $k\geq\tfrac{1}{2}d$, so the probability is bounded by $0.5$ in this regime.

Second, the cases where $a+b\leq 6$ correspond with the situation where $d\leq 12$. We can enumerate the cases where $d\leq 12$ and $0\leq k\leq d/2$. In each case, we verify numerically that the required probability is less than $0.7$.

It is easy to check that for $a=\tfrac{1}{2}k$, $b=\tfrac{1}{2}(d-k)$, and $x=k/d$, the inequality $(a+b-1)(1-x)\geq 0.8$ holds when $0<k<\tfrac{1}{2}d$ and $d\geq 12$. Instantiating the formula from Fact E.1 and simplifying, we reach

Indeed, for each $d$, the extremal choice is $k=1$. The function $\Phi$ is increasing, so we conclude that

The latter bound results from numerical computation. ∎

E.3. The projection of a spherical variable onto a cone

In this section, we establish Lemma 6.3, which controls the probability that a spherical random variable has an unusually large projection on a cone. Although the lemma is framed in terms of a spherical random variable, it is cleaner to derive the result using Gaussian methods. We require an exponential moment inequality [Bog98, Cor. 1.7.9] that ultimately depends on the Gaussian logarithmic Sobolev inequality.

Using this exponential moment bound, we reach an elegant estimate for the moment generating function of the squared projection of a standard normal vector onto a cone.

The result is trivial when $\xi=0$, so we may limit our attention to the case where the parameter $\xi$ is strictly positive or strictly negative. First, suppose that $\xi>0$. Consider the zero-mean function

The gradient calculation follows from (B.9), and it is easy to see that $F\in H^{1}(\gamma_{d})$ because the projection onto a cone is a contraction. The exponential moment bound (E.1) delivers the estimate

The second relation follows when we add and subtract $\xi\,\delta(K)$ in the exponential function. We have compared the moment generating function of $F(\bm{g})$ with itself. Solving the relation, we obtain the inequality

This is the bound (E.2) for the positive range of parameters.

Now, we turn to the negative range of parameters, which requires a more convoluted argument. To make the analysis clearer, we continue to assume that $\xi>0$, and we write the negation explicitly. Replacing $F$ by $-F$, the exponential moment bound (E.1) yields

This time, we cannot identify a copy of the left-hand side on the right-hand side. Instead, let us run the moment comparison argument directly on the remaining expectation:

The last inequality follows from the exponential moment bound (E.1), just as before. Solving this relation, we obtain

Introduce the latter inequality into (E.4) to reach

This estimate addresses the remaining part of the parameter range in (E.2). ∎

With this result at hand, we can easily prove the tail bound for the projection of a spherical random variable onto a cone.

For a parameter $\xi>0$, the Laplace transform method [BLM13b, Sec. 2.1] delivers

Let $R$ be a chi random variable with $d$ degrees of freedom, independent from $\bm{\theta}$. Using Jensen’s inequality, we can bound the expectation:

Substitute the inequality for the moment generating function (E.2) with $K=C$ into (E.5) to reach

Select $\xi=\lambda/(4\,\delta(C)+4\lambda)$ to determine that

This completes the first half of the argument.

The second half of the proof results in an analogous bound with $C$ replaced by $C^{\circ}$. Note that

The second relation follows from the Pythagorean identity (B.7) and the complementarity law (3.4). Repeating the Laplace transform argument from above, with $\xi>0$, we obtain the inequality

Introduce the bound (E.2) with $K=C^{\circ}$ into (E.7) to see that

Choose $\xi=\lambda/(4\,\delta(C^{\circ})+4\lambda)$ to reach

Combine the probability bounds (E.6) and (E.8) and identify the transition width $\omega^{2}(C)$ to complete the proof. ∎

E.4. Tail functionals of a product

Finally, we argue that the tail functional of a product cone is controlled by the tail functionals of the two summands.

According to the rule (5.4) for the intrinsic volumes of a product cone,

By dint of this identity, we can use probabilistic reasoning to bound the tail functionals of the cone $v_{k}(C\times K)$. Indeed, observe that

We can rewrite this inequality in terms of tail functionals:

Appendix F Statistical dimension and Gaussian width

This appendix contains a short proof of Proposition 10.2, which states that the Gaussian width of a spherical convex set is comparable with the statistical dimension of the cone generated by the set.

The first inequality holds because we have enlarged the range of the supremum. Afterward, we invoke Jensen’s inequality, and we recognize the supremum form (3.5) of the statistical dimension.

The last inequality follows from Fact C.3

On account of (3.3), we identify the right-hand side as the statistical dimension $\delta(C)$. ∎

Acknowledgments

DA is with the School of Mathematics, The University of Manchester. Research supported by DFG grant AM 386/1-1 and 386/1-2.

ML is with the School of Mathematics, The University of Manchester. Research supported by Leverhulme Trust grant R41617 and a Seggie Brown Fellowship of the University of Edinburgh.

MBM and JAT are with the Department of Computing and Mathematical Sciences, California Institute of Technology. Research supported by ONR awards N00014-08-1-0883 and N00014-11-1002, AFOSR award FA9550-09-1-0643, and a Sloan Research Fellowship.

The authors wish to thank Babak Hassibi and Samet Oymak for helpful discussions on the connection between phase transitions and minimax risk. Jared Tanner provided detailed information about contemporary research on phase transitions for random linear inverse problems.

References