{'fraction_non_alphanumeric': 0.04636287235035951, 'fraction_numerical': 0.019450929125035016, 'mean_word_length': 4.013623595505618, 'pattern_counts': {'":': 0, '<': 38, '<?xml version=': 0, '>': 57, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sharp recovery bounds for convex demixing, with applications

Demixing refers to the challenge of identifying two structured signals given only the sum of the two signals and prior information about their structures. Examples include the problem of separating a signal that is sparse with respect to one basis from a signal that is sparse with respect to a second basis, and the problem of decomposing an observed matrix into a low-rank matrix plus a sparse matrix. This paper describes and analyzes a framework, based on convex optimization, for solving these demixing problems, and many others. This work introduces a randomized signal model which ensures that the two structures are incoherent, i.e., generically oriented. For an observation from this model, this approach identifies a summary statistic that reflects the complexity of a particular signal. The difficulty of separating two structured, incoherent signals depends only on the total complexity of the two structures. Some applications include (i) demixing two signals that are sparse in mutually incoherent bases; (ii) decoding spread-spectrum transmissions in the presence of impulsive errors; and (iii) removing sparse corruptions from a low-rank matrix. In each case, the theoretical analysis of the convex demixing method closely matches its empirical behavior.


Introduction
In modern data-intensive science, it is common to observe a superposition of multiple information-bearing signals. Demixing refers to the challenge of separating out the constituent signals from the observation. A fundamental computational question is to understand when a tractable algorithm can successfully complete the demixing. Problems of this sort arise in fields as diverse as acoustics [1], astronomy [70], communications [7], [8], geophysics [77], image processing [71], [35], machine learning [14], and statistics [12]. Some well-known examples of convex methods for demixing include morphological component analysis [70], robust principal component analysis [17], [12], and inpainting [35].
This work presents a general framework for demixing based on convex optimization. We study the geometry of the optimization problem, and we develop conditions that describe precisely when our method succeeds. Let us illustrate the major aspects of our approach through a concrete example. Starck et al. use demixing to model the problem of distinguishing stars from galaxies in an astronomical image [70]. This task requires hypotheses on the two types of objects. First, we must assume that stars and galaxies exhibit different kinds of structure: stars appear as localized bright points, while galaxies are wispy or filamented. Second, we must insist that the image is not so full of stars, nor of galaxies, that they obscure one another. These two properties are modeled by the notions of incoherence and sparsity. With these hypotheses, we can solve the demixing problem using a method known as morphological component analysis (MCA) [70], [71], [35], [7], [84].

The MCA signal model
We model the observation z 0 ∈ R d as the superposition of two structured signals: The matrices A and B are known, while the vectors x 0 and y 0 are unknown. Each column of A contains an elementary structure that might appear in the first signal; the columns of B reflect the structures in the second signal. The vector x 0 selects the columns of A that appear in the first signal, e.g., stars in different locations, while y 0 selects the columns of B that generate the second signal, e.g., galaxies in different locations. Incoherence demands that the columns of A and B are weakly correlated, and sparsity requires that x 0 and y 0 have few nonzero elements.
For simplicity, we assume that A and B are orthonormal bases. By changing coordinates, we may take A = I, the identity matrix. The observation then has the form z 0 = x 0 +Q y 0 for a known orthogonal matrix Q. The specialization to orthonormal bases is standard [26], [35], [71], [46].
Instead of restricting our attention to specific choices of Q that are incoherent with the identity matrix, we consider an idealized model for incoherence where Q is a uniformly random orthogonal matrix. This formulation ensures that the structures in the two signals are oriented generically with respect to each other. Other authors have also used this approach to study incoherence [26], [35].
We quantify the sparsity of the two constituent signals by fixing parameters τ x and τ y in the interval [0, 1] such that the unknown signals x 0 and y 0 satisfy nnz(x 0 ) = τ x d and nnz(y 0 ) = τ y d , where nnz(x) denotes the number of nonzero elements of x. * In other words, τ x and τ y measure the proportion of nonzero entries in x 0 and y 0 . These sparsity parameters emerge as the major factor that determines how hard it is to extract x 0 and y 0 from the observation z 0 .

The constrained MCA demixing procedure
The goal of morphological component analysis is to identify the pair (x 0 , y 0 ) of sparse vectors given the observation z 0 and the matrix Q. A natural technique for finding a sparse vector that satisfies certain conditions is to minimize the 1 norm subject to these constraints [18], where the 1 norm is defined as x 1 := d i =1 |x i |. Assume that we have access to side information α = y 0 1 . Then the intuition above leads us to frame the following convex optimization problem for demixing: Phase transition for success of constrained MCA (d=100) τ x : Sparsity ratio for x 0 τ y : Sparsity ratio for y 0 Figure 1 Performance of constrained MCA. The variables τ x and τ y on the axes represent the fraction of components in x 0 and y 0 that are nonzero. The background shading indicates the empirical probability that the constrained MCA problem (1.1) identifies the pair (x 0 , y 0 ) from the observation z 0 = x 0 + Q y 0 , where Q is a random orthogonal basis. The yellow curve marks the empirical 50% success threshold. The green curve locates the theoretical phase transition for demixing a single pair (x 0 , y 0 ). For sparsity levels below the blue curve, constrained MCA (1.1) provably recovers all (τ x , τ y )-sparse pairs with high probability in the dimension. Further details are available in Section 1.1.3 and Section 6.1.
where the decision variables are x, y ∈ R d . We call this optimization problem constrained MCA, and we say that it succeeds if (x 0 , y 0 ) is the unique optimal point of (1.1). Since (1.1) can be written as a linear program, constrained MCA offers a tractable procedure for attempting to identify the underlying components (x 0 , y 0 ), provided the observation z 0 , the orthogonal matrix Q, and the side information α = y 0 1 .
Constrained MCA is closely related to the standard MCA procedure, which is a Lagrangian formulation of (1.1) that does not require the side information α [71,Eq. (4)]. The constrained problem (1.1) is more powerful than the standard MCA procedure, so it provides hard limits on the effectiveness of the usual approach. In most cases, the two methods are equivalent, provided that we can choose the Lagrange multiplier correctly-a nontrivial task in itself. See Section 1.2.4 for more details. Figure 1 displays the result of a numerical experiment on constrained MCA. We fix the dimension d = 100. For sparsity levels (τ x , τ y ) varying over the unit square [0, 1] 2 , we form vectors x 0 and y 0 with sparsity levels nnz(x 0 ) = τ x d and nnz(y 0 ) = τ y d . (The manner in which we choose the nonzero entries is irrelevant.) We draw a random orthogonal matrix Q and construct the observation z 0 = x 0 + Q y 0 . Then we solve the constrained MCA problem (1.1) to identify the pair (x 0 , y 0 ). The background of the figure shows the empirical probability of success over the randomness in Q; dark areas denote low probability of success, while light areas denote high success rates. The yellow curve marks the 50% success threshold.

Numerical and theoretical results for constrained MCA
This work establishes two theoretical results for constrained MCA. The first result provides a phase transition curve, parameterized by the sparsity (τ x , τ y ), for the probability that constrained MCA will demix a single pair (x 0 , y 0 ) from the associated observation z 0 . This weak bound is marked by the green line in  Second, we establish a strong bound. For a fixed instantiation of the random orthogonal basis Q, with high probability, constrained MCA (1.1) can identify every sufficiently sparse pair (x 0 , y 0 ) from the associated observation z 0 . The blue curve in the bottom left corner of Figure 1 is a lower estimate for the sparsity pairs (τ x , τ y ) where this uniform guarantee holds. Section 6.1 provides the details regarding the computation of the weak and strong bounds as well as a fully detailed description of our numerical experiment.

A recipe for demixing
This work is not primarily about MCA. We are interested in developing methods that apply to a whole spectrum of demixing problems. The following two sections describe how to construct a convex program that can separate two structured signals.

Structured signals and atomic gauges
The 1 norm is a convex complexity measure that tends to be small near sparse vectors, so we can minimize the 1 norm to promote sparsity. We now describe a method for building complexity measures that are appropriate for other types of structure. This construction was originally introduced in the nonlinear approximation literature [21], [78]. The recent paper [15] explains how to apply these ideas to solve signal processing problems.
In practice, we often encounter signals that are formed as a positive linear combination of a few elementary structures, called atoms, drawn from a fixed collection. For example, a sparse vector in R d is a conic combination of a small number elements from the set {±e i : i = 1, . . . , d } of signed standard basis vectors. We want to construct a function that reflects the complexity of an atomic signal.
We define the atomic gauge of a vector x ∈ R d with respect to a set A ⊂ R d of atoms by with the convention that f A (x) = +∞ if the set is empty. Then f A is a homogeneous convex function. The "unit ball" of f A is conv(A ), and the level sets of f A are dilations of this unit ball. The atomic gauge f A is a norm if and only if conv(A ) is a bounded, symmetric set that contains zero in its interior.
The convex hull of an atomic set A tends to have sharp corners at atoms; see Figure 2. At these sharp points, most perturbations of the objective increase the value of the gauge, so the atomic gauge tends to take small values at atoms. Similar behavior occurs at a signal comprised of a relatively small number of atoms. This observation is a key reason that atomic gauges make good complexity measures for atomic signals [15]. Some common atomic gauges include • The 1 norm. The 1 norm on R d is the atomic gauge generated by the set A = {±e i : i = 1, . . . , d } of signed standard basis vectors. This norm is widely used to promote sparsity [18], [13], [24]. The 1 norm may also be defined for matrices via the formula X 1 = i , j |X i j |. In this context, the 1 norm reflects the sparsity of matrices [16], [14], [17].
• The ∞ norm. The ∞ norm on R d , given by x ∞ = max i =1,...,d |x i |, is the atomic gauge generated by the set A = {±1} d ⊂ R d of all 2 d sign vectors. We use this norm to demix binary codewords. See also [31], [15], [51]. For matrices, the ∞ norm returns X ∞ = max i , j |X i j |; this function is the atomic gauge generated by the set of sign matrices.
• The Schatten 1-norm. The Schatten 1-norm on R m×n is the sum of the singular values of a matrix. It is the atomic gauge generated by the set of rank-one matrices in R m×n with unit Frobenius norm.
• The operator norm. The operator norm returns the maximum singular value of a matrix. On the space R n×n of square matrices, the operator norm is the atomic gauge generated by the set O n of orthogonal matrices. This norm can be used to search for orthogonal matrices [15,Prop. 3.13] Our applications focus on these four instances, but a dizzying variety other structure-promoting atomic gauges are available. For example, there are atomic gauges for vectors that are sparse in a dictionary (also known as analysis-sparsity) [34], [11], block-and group-sparse vectors [20], [72], and low-rank tensors and probability measures [15, Sec. 2].

A generic model for incoherence
Demixing is hopeless when the structures in the constituent signals are too strongly aligned. As an extreme example, suppose we observe z 0 = x 0 + y 0 , where both x 0 and y 0 are sparse. There is clearly no principled way to assign the nonzero elements of z 0 correctly to x 0 and y 0 . In contrast, if we observe z 0 = x 0 + Hy 0 , where H is a normalized Walsh-Hadamard transform and both x 0 and y 0 are sparse, then the pair (x 0 , y 0 ) is typically identifiable [79]. The latter situation is more favorable than the former because the Walsh-Hadamard matrix and the identity matrix are incoherent; that is, their columns are weakly correlated. In order to avoid restricting our attention to special cases, such as the Walsh-Hadamard matrix, we model incoherence by assuming that the basis Q is drawn randomly from the invariant Haar measure on the set of all orthogonal matrices O d . We call this the random basis model. This idealized approach to incoherence guarantees that the structures in the two constituent signals are generically oriented. This model has precedents in the literature on sparse approximation [26], [35], and it is analogous to the assumption of a measurement operator with a uniformly random nullspace that appears in the context of compressed sensing [25], [73].
We expect that the random basis model also sheds light on other highly incoherent problems, such as the case where Q = H is the Walsh-Hadamard transform or Q = D is the discrete cosine transform (DCT). Some limited numerical simulations suggest that both the Walsh-Hadamard and the DCT matrices behave qualitatively similar to the random matrix Q in the examples considered in this work. This observation is in line with the universality of phase transitions that appear in 1 minimization for many classes of measurement matrices [30]. However, more coherent situations may exhibit different behavior, and thus they fall outside the purview of this work.

Formulating a convex demixing method
We are ready to introduce a computational framework for demixing structured signals. This approach unifies several related procedures that appear in the literature. See, for example, [47], [17], [83].
Assume we observe the superposition of two structured signals: where Q is a known orthogonal matrix and the pair (x 0 , y 0 ) is unknown. We include the matrix Q in the formalism because it allows us to model incoherence using the random basis model described in Section 1.2.2 above. Our goal is to demix the pair (x 0 , y 0 ) from the observation z 0 . Let f and g be convex complexity measures-such as atomic gauges-associated with the structures we expect to find in x 0 and y 0 . Suppose we have access to the additional side information α = g (y 0 ). We combine these ingredients to reach the following convex demixing method: where the decision variables are x, y ∈ R d . The display (1.2) describes a convex program because f and g are convex functions. We say that the convex demixing method (1.2) succeeds at demixing (x 0 , y 0 ), or simply succeeds, if (x 0 , y 0 ) is the unique optimal point of (1.2); otherwise, it fails. In this work, we develop conditions that describe when the convex demixing method (1.2) succeeds and when it fails.

The Lagrangian counterpart
In practice, the value α = g (y 0 ) may not be known. In this case, we may replace the convex demixing method (1.2) with its Lagrangian relative subject to x +Q y = z 0 , (1.3) where λ > 0 is a regularization parameter that must be specified. The constrained problem (1.2) is slightly more powerful than (1.3), so its performance dominates the Lagrangian formulation (1.3). It is well known that (1.2) and (1.3) are essentially equivalent when the regularization parameter λ is chosen correctly and a mild regularity condition holds; see Appendix A for details. Thus, we can interpret our results as delineating the best possible performance of the Lagrange problem (1.3). This type of best-case analysis has precedents in the literature on sparse approximation, e.g., [82], yet the identification of optimal Lagrange parameters for demixing remains a significant open problem. Several works prove that specific demixing procedures succeed for specific choices of Lagrange parameters under incoherence assumptions [26], [84], [17], [12], [88], but these conservative guarantees fail to identify phase transitions. Since this document was submitted, some additional theoretical guidance choosing Lagrange parameters has appeared [76], [74], [37], [61]. Nevertheless, a comprehensive theory describing the optimal choices of Lagrange parameters for (1.3) does not currently exist.

One hammer, many nails
The convex demixing method (1.2) includes many interesting special cases. Our analysis provides detailed information about when (1.2) is able to separate two structured, incoherent signals. We now describe some applications of this machinery. The vertical line at τ ≈ 0.018 provides a uniform guarantee applicable to adversarial corruptions. For τ 0.018, with high probability, our protocol will decode a message subject to any τ-sparse corruption whatsoever. See Section 1.3.1 and Section 6.2 for more details.

A secure communications protocol that is robust to sparse errors
Suppose we wish to securely transmit a binary message across a communications channel. We can obtain strong guarantees of security by modulating the message with a random rotation before transmission [85], [86]. Our theory shows that decoding the message via demixing also makes this secure scheme perfectly robust to sparse corruptions such as erasures or malicious interference. Consider the following simple communications protocol. We model the binary message as a sign vector The transmitter sends the scrambled message s 0 = Qm 0 across the channel, where it is corrupted by an unknown sparse vector c 0 ∈ R d . The receiver must determine the original message given only the corrupted signal and knowledge of the scrambling matrix Q. This signal model is perfectly suited to the demixing recipe of Section 1.2. The discussion in Section 1.2.1 indicates that the 1 and ∞ norms are natural complexity measures for the structured signals c 0 and m 0 . Since the message m 0 is a sign vector, we also have the side information m 0 ∞ = 1. Our receiver then recovers the message with the convex demixing method minimize c 1 subject to m ∞ ≤ 1 and c +Qm = z 0 , (1.4) where the decision variables are c, m ∈ R d . This method succeeds if (c 0 , m 0 ) is the unique optimal point of (1.4). In Section 6.2, we apply the general theory developed in this work to study this communications protocol. Before summarizing the results of this analysis, we fix some notation. Suppose the corruption Low-rank matrix recovery with sparse corruptions. The horizontal axis is the normalized rank ρ = rank(X 0 )/n, and the vertical axis is the sparsity level τ = nnz(Y 0 )/n 2 . The intensity of the background denotes the empirical probability that (1.5) recovers (X 0 , Y 0 ) from the observation Z 0 = X 0 + Q(Y 0 ). In the region below the green curve, the convex demixing method (1.5) recovers a low-rank matrix X 0 from a randomly rotated sparse corruption Q(Y 0 ) with overwhelming probability in high dimensions. See Section 1.3.2 and Section 6.3 for more details. c 0 ∈ R d is τ-sparse; that is, nnz(c 0 ) = τd for some τ ∈ [0, 1]. We further distinguish between two types of corruption. A benign corruption c 0 is independent of the scrambling matrix Q. In contrast, an adversarial corruption may depend on both Q and m 0 . Adversarial corruptions also include nonlinear effects that are not necessarily malicious. For example, we can model an erasure at the i th time instant by taking (c 0 ) i = −(Qm 0 ) i . Figure 3 presents the results of a numerical experiment on this communications protocol; the complete experimental procedure is detailed in Section 6.2.3. Briefly, we consider messages of length d = 100 and d = 300, and we let the sparsity τ range over the interval [0, 0.35]. We test the benign case by adding a τ-sparse corruption that is independent from Q. We also consider a particular adversarial corruption in which we set the [τd ] largest-magnitude entries in the transmitted message s 0 to zero. The curves indicate the empirical probability that the protocol succeeds as a function of τ.
In the benign case, our theory shows that there exists a phase transition in the success probability of the convex demixing method (1.4) at sparsity level τ ≈ 0.19. The empirical 50% failure threshold for benign corruptions closely matches this prediction. In the adversarial case, our results guarantee that with high probability, our protocol will tolerate all corruptions that affect no more than 1.8% of the components in the received message z 0 . This bound is conservative for the type of adversarial corruption in the numerical experiment; this is not surprising because we may not have constructed the worst possible corruption.

Low-rank matrix recovery with generic sparse corruptions
Consider now the matrix observation Z 0 = X 0 +Q(Y 0 ) ∈ R n×n , where X 0 has low rank, Y 0 is sparse, and Q is a random rotation on R n×n . This type of signal provides a highly stylized model for applications such as latent variable selection [14], [17] and robust principal component analysis [12]. In these settings, X 0 has low rank because the underlying data is drawn from a low-dimensional linear model, while Q(Y 0 ) represents a corruption. (Note, however, that this stylized model is not equivalent to pre-and post-multiplying Y 0 by independent random rotations of R n .) We aim to discover the matrix X 0 given the corrupted observation Z 0 and the rotation Q.
We follow the now-familiar pattern of Section 1.2. The Schatten 1-norm · S 1 serves as a natural complexity measure for the low-rank structure of X 0 , and the matrix 1 norm · 1 is appropriate for the sparse structure of Y 0 . We further assume the side information α = Y 0 1 . We then solve This convex demixing method succeeds if (X 0 , Y 0 ) is the unique solution to (1.5). Figure 4 displays the results of a numerical experiment on this approach to rank-sparsity demixing. We take the matrix side length n = 35 and draw a random rotation Q for R n×n . For parameters 0 ≤ ρ, τ ≤ 1, we generate matrices X 0 and Y 0 such that rank(X 0 ) = [ρn] and nnz(Y 0 ) = [τn 2 ]. The background shading indicates the empirical probability that (1.5) succeeds given the observation Z 0 = X 0 + Q(Y 0 ). We mark the empirical 50% success probability with a yellow curve. See Section 6.3.1 for the experimental details.
The results of this work show that, with high probability, program (1.5) succeeds so long as the pair (ρ, τ) lies below the green curve on Figure 4. When the rank parameter ρ is small, our theoretical bound closely tracks the phase transition visible in the numerical experiment, although the bound appears loose when ρ is larger. Section 6.3 provides further details.

Matrix demixing mix-and-match
Our results are not restricted to the convex demixing methods (1.1), (1.4) or (1.5). Let us mention a few other situations we can analyze using the theory developed in this work. With a tractable convex program, it is possible to demix • An orthogonal matrix from a matrix that is sparse in a random orthogonal basis, • A randomly oriented sign matrix from a sufficiently low-rank matrix, and • A randomly rotated low-rank matrix from an orthogonal matrix. See Section 6.4 for the details.

Theoretical insights
Our approach reveals a number of theoretical insights.

Design of convex demixing methods for incoherent structures.
In the incoherent regime we analyze, the parameters that determine when the convex demixing method (1.2) succeeds reflect the structures in the constituent signals and the associated complexity measures. These summary parameters are independent of the relationship between the two incoherent structures. We discuss this fact and its consequences for the design of demixing procedures in Section 4.2.1.
Connection with linear inverse problems. The parameters that determine success of the convex demixing method (1.2) are closely related to number of random linear measurements required to identify a structured signal. In Section 5.2, we leverage this relationship to compute these parameters from Gaussian width bounds developed in [15].
Phase transitions. Our theory indicates that there is often a phase transition in the behavior of the demixing method (1.2). See Section 4.2.2 for a discussion of this point.

Outline
This work begins with demixing in the deterministic setting. Section 2 describes the geometry of the convex demixing method (1.2) and provides a geometric characterization of successful demixing. Section 3 presents a random model for incoherence along with some techniques from spherical integral geometry that allow us to analyze this model. In Section 4, these ideas yield theory that predicts success and failure regimes for the convex demixing method (1.2). Section 5 develops methods for computing the parameters necessary to apply the theorems of Section 4.
In Section 6, we analyze the application problems described in Sections 1.1 and 1.3. Section 7 concludes with a discussion of this work's place in the literature and future directions.

Notation and conventions
All variables are real valued. We write t , t , and [t ] for the floor, ceiling, and rounded integer values of t . The signum function is sgn (t ) := t / |t | for t = 0 and sgn (0) := 0. Bold lowercase letters represent vectors, and bold capital letters are matrices. The i th element of a vector is written x i or (x) i , while the (i , j )th element of a matrix is X i j or (X ) i j . We express the transpose of X as X * . The vector signum sgn (x) is defined by applying the signum elementwise.
The symbol · p stands for the p vector norm on R d , defined by x The p norm of a matrix treats the matrix as a vector and applies the corresponding vector p norm. The Schatten 1-norm X S 1 is the sum of the singular values of a matrix X , while the operator, or spectral, norm X Op returns the maximum singular value of X .
We reserve the symbols f and g for convex functions. A convex function may take the value +∞, but we assume that all convex functions are proper; that is, each convex function takes on at least one finite value and never takes the value −∞.
The Euclidean unit sphere in R d is the set S d −1 . The orthogonal group-the set of d × d orthogonal matrices-is denoted O d . The subset of O d with determinant one (the special orthogonal group) is SO d . For brevity, we use the term basis to refer to an orthogonal matrix from O d . In the sequel, the letter Q will always refer to a basis.
The symbol P denotes the probability of an event. Gaussian vectors and matrices have independent standard normal entries. A random basis is a matrix drawn from the Haar measure on O d .
A special note is in order when our observations are matrices. The space of matrices R m×n is equipped with a natural isomorphism to R mn through the vec(·) operator, which stacks the columns of a matrix on top of one another to form a tall vector. We define a random basis Q for R m×n by Q(Y ) = vec −1 Q vec(Y ) , where Q is a random basis for R mn . It is easily verified that such a Q is a random basis for R m×n equipped with the Euclidean structure induced by the Frobenius norm.
We deal frequently with convex cones, which are positively homogeneous convex sets. For any cone K , we define the polar cone A polyhedral cone is the intersection of a finite number of closed halfspaces, each containing the origin. One important polyhedral cone is the nonnegative orthant, defined by For a set A ⊂ R d , we write conv(A) for its convex hull and A for its closure. Two cones K 1 ,

The geometry of demixing
This short section lays the geometric foundation for the rest of this work. Section 2.1 describes the local behavior of convex functions in terms of special convex cones. In Section 2.2, this geometric view yields a concise characterization of successful demixing in terms of the configuration of two cones. The results in this section are deterministic, that is, they hold for any fixed basis Q.

Feasible cones
The success of the convex demixing method (1.2) depends on the properties of the complexity measures f and g at the structured vectors x 0 and y 0 . The following definition captures the local behavior of a convex function.  Therefore, the feasible cone of the ∞ norm at x is congruent to the nonnegative orthant: The feasible cone is always a convex cone containing zero, but it is not necessarily closed. If A is a set of atoms and a ∈ A , the feasible cone F ( f A , a) of the atomic gauge f A at the atom a tends to be small because the unit ball of f A is the smallest convex set containing all of the atoms. See Figure 2 for an illustration. The positive homogeneity of atomic gauges further implies that the feasible cones of atomic gauges do not depend on the scaling of a vector, in the sense that for all x ∈ R d and any λ > 0. Remark 2.3. Definition 2.1 is equivalent to the definition of the "tangent cone" appearing in [15,Eq. (8)]. However, that definition differs slightly from the standard definition of a tangent cone; cf., [66,Thm. 6.9]. The cone of feasible directions [62, p. 33] is the closest relative of the feasible cone that we have identified in the literature, and this is the source of our terminology.

A geometric characterization of optimality
The following lemma provides a geometric characterization for success in the convex demixing method (1.2) in terms of the configuration of two feasible cones. This is the main result of this section. In words, the demixing method (1.2) succeeds if and only if the two feasible cones are rotated so that they intersect trivially. Intuitively, we expect that many bases Q satisfy this condition when the two feasible cones are small. This observation provides further support for choosing atomic gauges as our complexity measures. We illustrate Lemma 2.4 in Figure 5.
The proof of Lemma 2.4 requires two technical propositions. The first is an alternative characterization of feasible cones.  Proof. The "if" part is immediate: given any such λ 0 , the assumption by the definition of feasible cones. The other direction follows from convexity. Indeed, suppose δ ∈ F ( f , x), so that there exists a number λ 0 > 0 for which f (x + λ 0 δ) ≤ f (x). By convexity, the map λ → f (x + λδ) lies below the chord connecting 0 and λ 0 , which is the claim.
Our second technical proposition is a change of variables formula for the feasible cone under a nondegenerate affine transformation. Proposition 2.6. Let g be any convex function, and define h( The proof of Proposition 2.6 follows directly from the definition of a feasible cone. We omit the details. Proof of Lemma 2.4. Because Q is unitary, we may eliminate the variable y in (1.2) via the equality constraint y = Q * (z 0 − x). Therefore, (x 0 , y 0 ) is the unique optimum of (1.2) if and only if x 0 is the unique optimum of minimize f (x) with decision variable x. The equality in (2.1) follows from the definition z 0 = x 0 +Q y 0 . The original claim thus reduces to the statement that x 0 is the unique optimum of (2.1) if and only if F ( f , x 0 )∩ −QF (g , y 0 ) = {0}. The rest of the proof is devoted to this claim.
We show that x 0 is the unique optimum of (2.1) by verifying that the strict inequality f (x) > f (x 0 ) holds for any feasible point x of (2.1) with x = x 0 .
To this end, assume x is feasible for (2.1) and x = x 0 . Feasibility of x is equivalent to By definition of the feasible cone and the transformation rule of Proposition 2.6, the inequality above implies x − x 0 ∈ F g Q * (z 0 − ·) , x 0 = −QF g ,Q * (z 0 − x 0 ) = −QF (g , y 0 ); The final equality above follows from z 0 = x 0 +Q y 0 .
. By the definition of feasible cones, we must have f (x) = f x 0 + (x − x 0 ) > f (x 0 ). We have deduced f (x) > f (x 0 ) for every feasible x = x 0 , and so conclude that x 0 is the unique optimum of (2.1).
(⇒) Suppose x 0 is the unique optimum of (2.1). Let δ be some vector in the intersection F ( f , x 0 ) ∩ −QF (g , y 0 ) . We must show δ = 0. As for all sufficiently small λ > 0. We have used the relation z 0 = x 0 + Q y 0 again here. In summary, for some small enough λ > 0, the perturbed point x 0 + λδ is feasible for (2.1), and its objective value is no larger than f (x 0 ). In other words, x 0 + λδ is an optimal point of (2.1). But x 0 is the unique optimal point of (2.1) by assumption, so we must have δ = 0. This is the claim.

Background from integral geometry
By coupling the random basis model of Section 1.2.2 with the optimality condition of Lemma 2.4, the optimality condition for the demixing method (1.2) boils down to a geometric question: When does a randomly oriented cone strike a fixed cone?
This section provides a background in spherical integral geometry, a subfield of integral geometry that studies random configurations of cones and quantities related to these configurations [69, Section 6.5]. This theory provides an exact expression, called the spherical kinematic formula, for the probability that the convex demixing method (1.2) succeeds under our random model. Unfortunately, the quantities involved in the spherical kinematic formula are typically difficult to compute. To ease this burden, Section 3.3 defines geometric summary parameters that greatly simplify the application of the spherical kinematic formula.
We use subspaces and the nonnegative orthant as running examples to illustrate the concepts from integral geometry. These are not simply toy examples. A subspace plays an important role in the linear inverse problems in Section 5, while the orthant, which is congruent to the feasible cone of the ∞ norm at a sign vector, appears at several points in our examples in Section 6.

Spherical intrinsic volumes
We begin our introduction to integral geometry with fundamental geometric parameters known as spherical intrinsic volumes [54]. Spherical intrinsic volumes quantify geometric properties of convex cones such as the fraction of space a cone consumes (a type of volume), the fraction of space taken by the corresponding dual cone, and quantities akin to surface area. The following characterization [3, Proposition 4.4.6] is convenient.
where the vector ω is drawn from the standard Gaussian distribution on R d .
Although computing spherical intrinsic volumes is often challenging, a direct application of Definition 3.1 can bear fruit in some situations. In Figure 6, we demonstrate how to compute spherical intrinsic volumes for cones in R 2 . A subspace of R d provides another simple example.

Proposition 3.2 (Spherical intrinsic volumes of a subspace). Suppose L ⊂ R d is a linear subspace of dimension n. Then v i
Proof. A subspace L of dimension n is a polyhedral cone with a single face, with dimension n. The projection of any point onto L lies in the relative interior of this face. The claim follows immediately from Definition 3.1.
The computation of the spherical intrinsic volumes for the nonnegative orthant requires only some elementary probability theory. We illustrate the following result in Figure 7.
Proof. The Euclidean projection onto the nonnegative orthant is given by the componentwise threshold operation Therefore, the projection Π R d + (ω) lies in the relative interior of an (i + 1)-dimensional face of R d + if and only if ω has exactly i + 1 strictly positive values.
When ω is drawn from a standard Gaussian distribution, the number of positive entries is distributed as a binomial random variable. Hence, Π R d . This is precisely the definition of the i th spherical intrinsic volume v i (R d + ).

Remark 3.4 (Extension to nonpolyhedral cones)
. The definition of spherical intrinsic volumes extends to all closed convex cones by approximation with polyhedral cones, but note that the probabilistic characterization above does not hold for nonpolyhedral cones. The technical details involve continuity properties of the spherical intrinsic volumes under the spherical Hausdorff metric. This theory is developed in [38], [39]. See [69, Ch. 6.5] for a self-contained overview of spherical integral geometry developed via polyhedral approximation, or see [3, Sec. 4] for a development using tools from differential geometry.

Key facts from integral geometry
We now collect some of the properties of spherical intrinsic volumes that are required for our development.
We start with some elementary facts.
Fact 3.5. Let K ⊂ R d be a closed convex cone. Then

(Basis invariance) For any basis U ∈ O d and index
Proof sketch. First, assume K is a polyhedral cone. The positivity of spherical intrinsic volumes follows from the positivity of probability. The unit-sum rule follows immediately from the fact that the projection Π K (x) lies in the relative interior of a unique face of K . Finally, the basis invariance of spherical intrinsic volumes is immediate from the corresponding invariance of the Gaussian distribution. Continuity of the spherical intrinsic volumes under the spherical Hausdorff metric implies that these facts must hold for all closed convex cones by approximation with polyhedral cones.
We conclude our background discussion with the following remarkable formula for the probability that a randomly oriented cone strikes a fixed cone. In view of Lemma 2.4, this result is fundamental to our understanding of the probability that the convex demixing method (1.2) succeeds under the random basis model.

Fact 3.6 (Spherical kinematic formula [69, p. 261]). Let K andK be closed convex cones in R d , at least one of which is not a subspace, and let Q be a random basis. Then
Remark 3.7. Fact 3.6 is usually stated for random rotations drawn according to the Haar measure on the special orthogonal group SO d , but the unitary invariance given by Fact 3.5.3 readily implies that the spherical kinematic formula holds for Q drawn from the Haar measure on the orthogonal group O d .
Remark 3.8. The spherical Gauss-Bonnet formula (Fact B.2 in Appendix B.1) can be used to eliminate the apparent asymmetry between K andK in (3.2). In particular, the identity holds for any convex cones K andK .

High-dimensional decay of spherical intrinsic volumes
The spherical kinematic formula (3.2), coupled with the geometric optimality conditions of Lemma 2.4, provides an exact expression for the probability that the demixing problem (1.2) succeeds. Nevertheless, the formula involves the spherical intrinsic volumes of two cones, and it is challenging to determine these quantities directly from the definition except in simple situations.
To confront this challenge, we seek summary statistics for the intrinsic volumes as the dimension d → ∞. We motivate our approach with the orthant. In Figure 7, we see that the spherical intrinsic volumes of the orthant v i (R d + ) decay rapidly as d → ∞ when the index i falls outside of the region i ≈ d /2. The intrinsic volumes with indices i far away from d /2 will contribute very little to the sum (3.2) appearing in the kinematic formula. This observation simplifies the application of the kinematic formula when one of the cones is congruent to the orthant.
In general, we might hope that for some sequence of cones K (d ) ∈ R d , the spherical intrinsic volumes v i (K (d ) ) decay rapidly as d → ∞ for indices i outside of some interval [κ d , θ d ]. We codify this behavior with decay thresholds that indicate which intrinsic volumes are very small as the ambient dimension d grows.
On the other hand, we say that κ ∈ [0, 1] is a lower decay threshold for {K (d ) } if, for every κ < κ , there exists an ε > 0 such that, for all d ∈ D sufficiently large, we have We extend these definitions to non-closed cones by taking the closure. We say θ is an upper decay threshold for {K (d ) } if and only if it is an upper decay threshold for K (d ) . Similarly, κ is a lower decay threshold for {K (d ) } if and only if it is a lower decay threshold for K (d ) .
When it will not cause confusion, we omit the index set D.
Remark 3.10 (Nonuniqueness of decay thresholds). The upper decay threshold θ for an ensemble {K (d ) } defined above is not unique since any θ > θ is also a decay threshold for {K (d ) }. An analogous comment holds for the lower decay threshold.

Examples of decay thresholds
Since the intrinsic volumes are positive and sum to one (Fact 3.5), not every intrinsic volume is exponentially small in the ambient dimension d . In particular, the inequality κ ≤ θ between lower and upper decay thresholds always holds. In practice, however, we can often find decay thresholds that satisfy the equality κ = θ , as the following examples demonstrate. Proof. Let n = n (d ) = dim(L (d ) ). By Proposition 3.2, we have v i (L (d ) ) = δ i ,n−1 . Then for any θ > σ, we have θd > σd for all large enough d ∈ D, so that Feasible cones of the Schatten 1-norm at n × n rank ρn matrices 6ρ − 3ρ 2 (See also Rem. 5.5.) Feasible cones of the spectral norm at an orthogonal matrices 3 4 where is the natural entropy; be aware that the logarithms are base-e rather than the customary base-2 used in information theory. Basic calculus shows that H (θ) achieves its unique maximum at θ = 1 2 , where it has maximum value H 1 2 = log(2). Let θ > 1 2 . By continuity of H , there is an ε > 0 such that H (θ) < log(2) − ε for allθ ≥ θ > θ . Continuity of the exponential and the uniform convergence in (3.5) together imply that, for all sufficiently large d ∈ D, and any i ≥ θd , we have The left-hand side is equal to the spherical intrinsic volume v i (R d + ) by Proposition 3.3, so we see that θ = 1 2 is an upper decay threshold for {R d + : d ∈ D}. The proof that κ = 1 2 is a lower decay threshold for {R d + : d ∈ D} follows along similar lines. Briefly, for any κ < 1 2 , there is an ε > 0 such that H (κ) < log(2) − ε for everyκ ≤ κ. For the same reasons as before, when d is large enough, we have for all i ≤ κd . We conclude that κ = 1 2 is a lower decay threshold for the ensemble of nonnegative orthants {R d + : d ∈ D}. Figure 8 illustrates the computation above. We discuss other approaches for finding decay thresholds in Section 5. Table 1 summarizes the decay thresholds determined in this work.

Success and failure
This section synthesizes the material from Sections 2 and 3 to determine whether the convex demixing method (1.2) succeeds, or fails, with high probability. Section 4.1 introduces the concept of a demixing ensemble. Our main results arrive in Section 4.2, where we find that the success and failure of the convex demixing method (1.2) are characterized by decay thresholds. Section 4.3 extends our methods to achieve uniform guarantees on the success of method (1.2).

Ensembles of demixing problems
A demixing ensemble is a collection of demixing problems that is indexed by the ambient dimension of the observation. We explain this idea in the context of MCA, and we develop the abstract definition in Section 4.1.2.

Example: The MCA demixing ensemble
Recall from Section 1.1 that MCA seeks to demix a superposition of two sparse vectors. Let us fix sparsity levels τ x and τ y in [0, 1]. For each pair (τ x , τ y ), we construct an ensemble of demixing problems with one In other words, the sparsity of each vector is proportional to the ambient dimension. Draw a random basis To set up a convex demixing method, we need to introduce appropriate complexity measures for x (d ) 0 and y (d ) 0 . For both vectors, the 1 norm on R d is the natural choice for inducing sparsity. Assume we have access to the side information α (d ) = y (d ) 0 1 . Together, these data define a demixing ensemble for MCA. We want to study when the MCA problem (1.2) succeeds with high probability for all members of the ensemble with d sufficiently large.

Abstract demixing ensembles
It is straightforward to extend this idea to other demixing problems. Let D ⊂ N be an infinite set of indices. A demixing ensemble consists of one problem per index. For each d ∈ D, the data are • A random basis Q (d ) ∈ O d that is statistically independent of the other ensemble data, . Given such a demixing ensemble, we seek to determine conditions for which the convex demixing method succeeds with high probability when the dimension d is large. When it does not cause confusion, we omit the superscript d . Our goal in this paper is to describe regions where the demixing program (4.1) succeeds, or fails, with high probability as the dimension d → ∞. In order to avoid cumbersome repetition in our theorems, we make a shorthand definition. Definition 4.1 (Overwhelming probability in high dimensions). Given a demixing ensemble as in Section 4.1.2, we say that (4.1) succeeds with overwhelming probability in high dimensions if there exists an ε > 0 such that, for every sufficiently large dimension d ∈ D, program (4.1) succeeds with probability at least 1−e −εd over the randomness in Q (d ) . Similarly, we say that (4.1) fails with overwhelming probability in high dimensions if there exists an ε > 0 such that, for every sufficiently large dimension d ∈ D, program (4.1) succeeds with probability at most e −εd .
Following common practice in asymptotic analysis, the definition above masks the dependence between the probability decay rate ε and the "sufficiently large" dimension d 0 . This approach represents a tradeoff. We will find that it provides demixing guarantees in terms of only decay thresholds, but it does not provide explicit probabilistic bounds for finite d . Nevertheless, our asymptotic analysis proves quite accurate at predicting the behavior in our experiments. See Remark 4.6 for further discussion.

The main results
We are now in a position to state our main results. The first result shows that the upper decay threshold provides guarantees for the success of demixing under the model of Section 4.1.
then program (4.1) succeeds with overwhelming probability in high dimensions.
The proof of this result appears in Section 4.2.
3. This next result shows that the failure of demixing is characterized by the lower decay threshold.
then program (4.1) fails with overwhelming probability in high dimensions.
The proof of this second result is similar in spirit to the proof of Theorem 4.2, but it requires additional technical finesse; we defer the details to Appendix B.1.

Consequences for the choice of complexity functions
The complementary nature of Theorems 4.2 and 4.3 has striking implications. The success, or failure, of the convex demixing method (4.1) in high dimensions depends only on the sum of the decay thresholds. As a consequence, the upper and lower decay thresholds assess the quality of the complexity measures f (d ) and g (d ) in high dimensions.
Since the decay thresholds are independent of any interrelationship between the structured vectors x (d ) 0 and y (d ) 0 in the superimposed observation z (d ) 0 , the quality of the complexity measure f (d ) is independent of the choice g (d ) . This explains, for instance, the ubiquity of the use of the 1 norm for inducing sparsity and the Schatten 1-norm as a complexity measure for rank. Simply put, when a complexity measure is good for one incoherent demixing problem, it is good for another.

Sharp phase transitions
Theorems 4.2 and 4.3 have an important consequence for phase transitions in the convex demixing method (4.1). Equality between the lower and upper decay thresholds holds in cases where we have access to exact formulas for the spherical intrinsic volumes. Proposition 3.11 shows that the upper and lower decay thresholds are equal for subspaces whose dimension is proportional to the ambient space, and Proposition 3.12 implies that the upper decay threshold is equal to the lower decay threshold for the ensemble of nonnegative orthants. Moreover, our computations in Appendix C suggest that equality between the upper and lower decay thresholds also holds for the ensemble of feasible cones of the 1 norm at vectors with a fixed proportion of nonzero elements.
The equality of the upper and lower decay thresholds explains the close agreement between our theoretical bounds and the empirical experiments. For instance, consider Figure 1. For sparsity levels below the green curve, the sum of the upper decay thresholds is less than one, so Theorem 4.2 implies that demixing succeeds with overwhelming probability in high dimensions. On the other hand, with sparsity levels above the green curve, the sum of the lower decay thresholds exceeds one, so demixing fails with overwhelming probability in high dimensions by Theorem 4.3. (See Section 6.1 for the details of this calculation.) One may wonder whether the transition between success and failure is sharp in general. In work undertaken after the submission of this article, with collaborators, we have determined that the answer to this question is yes for a large class of demixing ensembles. In essence, the result [5, Thm.

Proof of Theorem 4.2
The proof of Theorem 4.2 follows readily from a geometric statement concerning the probability that a random cone strikes a fixed cone as the dimension d becomes large.
except with probability e −εd , for all sufficiently large d .
Since cones are contained in their closure, the two feasible cones have a trivial intersection at least as frequently as their closures (but see the remark below). Applying our geometric optimality condition, Lemma 2.4, immediately implies that (4.1) succeeds with probability at least 1 − e −εd for every sufficiently large d .

Remark 4.5.
In fact, the probability that randomly oriented convex cones strike is equal to the probability that their closures strike. This seemingly innocuous claim appears to have no simple proof from first principles. However, this fact readily follows from the discussion of touching probabilities in [69, pp. 258-259]. Figure 9 illustrates the main idea behind the following proof.
Proof of Theorem 4.4. The spherical kinematic formula (3.2) only applies when at least one cone is not a subspace, so we split the demonstration into two cases. First, we assume that at least one of the ensembles {K (d ) } or {K (d ) } of cones does not contain any subspace. Then, we consider the case where both ensembles of cones contain only subspaces. The argument readily extends to the general case by considering subsequences where one of the two cases above holds. Throughout the proof, we drop the explicit dependence of K (d ) andK (d ) on the dimension d for notational clarity. We start with the first case: assume that either K orK is not a subspace. Our main tool is the spherical kinematic formula, Fact 3.6. The positivity of the spherical intrinsic volumes and the bound (1 + (−1) k ) ≤ 2 imply that the probability P of interest satisfies (4. 2) The equality follows by a change in the order of summation and a change of the summation index. Since θ +θ < 1, there exist parameters θ > θ andθ >θ for which θ +θ < 1. We expand the right-hand sum of (4.2) into four terms, say Σ 1 , Σ 2 , Σ 3 , and Σ 4 : We bound each summand separately. First, the fact θ +θ < 1 implies that, for all sufficiently large d , we have θd + θ d < d − 1. We conclude that Σ 1 = 0 when d is large enough: The inner sum is empty.
To bound Σ 2 , apply Facts 3.5.1 and 3.5.2 to the inner sum to find where the second inequality holds for some ε > 0 and all sufficiently large d owing to the definition of the upper decay threshold θ . Through analogous reasoning, the definition ofθ gives the exponential bounds for some ε , ε > 0 and all sufficiently large d . Taking ε sufficiently small (say ε = 1 2 min{ε , ε , ε }) and d sufficiently large gives the result for the first case.
for some ε > 0, all sufficiently large d , and every i ≥ θd . In particular, this inequality implies n − 1 < θd for all d large enough. Similarly, we findñ − 1 < θ d for all d sufficiently large.
Since θ +θ < 1, we have n +ñ ≤ θd + θ d + 2 < d whenever d is large enough. That is, the sum of the dimensions of the subspaces is less than the ambient dimension. Since two randomly oriented subspaces are almost surely in general position, we see that K ∩ QK = {0} with probability one, whenever d is large enough. This completes the second case, so we are done.
Remark 4.6 (Explicit dimensional dependence). The methods above can provide explicit dependence between the sum of the decay thresholds θ x + θ y , the "sufficiently large" dimension and the probability decay rate ε when detailed information about the intrinsic volumes is available. In the case of the orthant, for example, Stirling's formula with remainder [59, Sec. 5.6.1] may provide enough information. For the descent cones of the 1 norm, it may be possible to achieve such explicit dependence using the approach of [32].

Uniform demixing guarantees
Suppose that Q is drawn at random and fixed. For example, in the MCA problem from Section 1.1, we may observe a number of different images, but the structures that we expect to find (encoded by Q) are the same in each image. In this case, we ask whether (1.1) demix every sparse pair (x 0 , y 0 ) from the associated observation z 0 = x 0 +Q y 0 , and thus successfully identify the structures in a large family of images.
More generally, we can study the probability that the generic demixing program (1.2) will demix every structured pair (x 0 , y 0 ) with a random-but fixed-basis Q. (These uniform guarantees go by the name of strong bounds [28], [25], [29], [31].) By the geometric optimality condition of Lemma 2.4, this probability is equal to the probability of the event −QF (g , y 0 ) = {0} for every structured pair (x 0 , y 0 ). (4.4) In this section, we control the probability of (4.4) by coupling the argument leading to Theorem 4.2 with a union bound. This approach does not necessarily limit our methods to a finite number of structured pairs (x 0 , y 0 ), however. In the case of a sparse vectors, for example, the set of feasible cones consists of d k 2 k cones because the feasible cone F ( · 1 , x) depends only on the sparsity and sign pattern, and not the magnitude, of the elements of x. (See Section 6.1.1 for more details.) Thus, even the simple union bound can offer insight into the behavior of constrained MCA (1.1) for an infinite family of images.
Applying a union bound to a finite, but rather large, set of cones such as (4.5) requires stronger probabilistic information than provided by the decay thresholds. Therefore, we define an extension of the upper decay threshold that provides detailed information on the rate of decay of spherical intrinsic volumes. holds for all i ≥ θd . When no level is specified, we take ψ = 0 for compatibility with Definition 3.9. As in Definition 3.9, this definition extends to non-closed cones by taking the closure.
Subspaces and orthants again provide useful examples. The computation for the orthant is only slightly more involved. The following result is illustrated in Figure 10. where H (θ) is the entropy defined in (3.6).
is an upper decay threshold at level ψ for the ensemble {R d + }.
We now extend the decay threshold to cover the family of cones considered in condition (4.4). In our applications, the feasible cones appearing in (4.4) are congruent, so we restrict our attention to this case.  If θ +θ < 1, then there exists an ε > 0 such that for every sufficiently large d , where the probability is taken over the random basis Q ∈ O d .
The proof of Theorem 4.11 simply couples a union bound to the proof of Theorem 4.4, so we defer the demonstration to Appendix B.2. Note that the statement of Theorem 4.11 is equivalent to that of Theorem 4.4 when K (d ) andK (d ) are singletons, because we may take ψ =ψ = 0 in this case. Theorem 4.11 can be used to verify that event (4.4) holds with high probability when the dimension d becomes large. In Section 6.1.1, we use this approach to verify that the MCA formulation (1.1) can demix all sufficiently sparse vectors, and in Section 6.2.2, we use Theorem 4.11 to show that the channel coding method (1.4) is robust to adversarial sparse corruptions.

Computing decay thresholds
Section 4.2 demonstrates that the decay thresholds provide a simple way to analyze demixing under the random basis model. This section describes several methods for computing decay thresholds. We begin by considering direct approaches, where precise formulas for the spherical intrinsic volumes give correspondingly precise thresholds.
The direct method is powerful, but its application is limited to regimes where we have access to formulas for spherical intrinsic volumes. In Section 5.2, we observe that known results on linear inverse problems [15] imply bounds on decay thresholds. This observation allows us to study upper decay thresholds for several structural classes, including low-rank matrices.

Direct approach
There are several situations where the direct approach for calculating decay thresholds is feasible. Propositions 3.11 and 3.12 compute upper and lower decay thresholds for ensembles of subspaces and orthants directly from the definition of spherical intrinsic volumes. In Appendix C, we use the asymptotic polytope angle computations of [25] to compute the decay threshold for ensembles of feasible cones of the 1 norm at sparse vectors. The approach follows roughly the same lines as Propositions 3.12 and 4.9, but the argument requires a good deal of background information that is tangential to this work.

Relationship to linear inverse problems
There is a useful link between the number of random linear measurements required to identify a structured signal with a convex complexity measure and the upper decay threshold of the associated feasible cone. Roughly speaking, the upper decay threshold is the ratio between the number of linear measurements required to identify a structured signal and the ambient dimension. This observation provides a powerful method for determining decay thresholds.
Linear inverse problems are closely related to demixing problems. Suppose we observe the linear image z 0 = Ax 0 , where A is a known matrix and x 0 is a structured vector. Given an associated convex complexity measure f , Chandrasekaran et al. [15] study the convex optimization program minimize f (x) subject to Ax = z 0 . (5.1) These authors consider the question "Given the data z 0 = Ax 0 , when is x 0 the unique optimal point of (5.1)?" The answer to this question is closely related to our demixing problem.
To place the linear inverse problem in our asymptotic framework, we consider an ensemble of problems indexed by the ambient dimension d . with decision variable x ∈ R d . This method succeeds when x (d ) 0 is the unique optimal point of (5.2). The following result shows that the problem of computing the number of random linear measurements needed to identify a structured vector is equivalent to determining an upper decay threshold. When A = Ω is a Gaussian matrix, its null space is a randomly oriented subspace. Combining this fact with the kinematic formula (3.2) lets us compute the decay threshold using the number of observations required to recover a vector with (5.1) under a Gaussian measurement model. In Appendix C.3, we describe how our computation of the upper decay threshold for the feasible cone of the 1 norm at sparse vectors relates to the recovery guarantees for basis pursuit explored in the series of papers [23], [25], [29], [30], [33]. Our approach also yields a sharp transition between success and failure regimes for basis pursuit. See Appendix C.3.2 for the details.

Remark 5.2.
A counterpart to Lemma 5.1 that links the failure of linear inverse problems to the lower decay threshold κ is readily derivable with the techniques used in this work. This may enable the computation of lower decay thresholds through information-theoretic arguments [81].

The upper decay threshold from the Gaussian width
Lemma 5.1 provides a powerful tool for computing upper decay thresholds. Define the Gaussian width of a cone K ⊂ R d by the expression where the random vector ω is drawn from the Gaussian distribution on R d . The following corollary lets us determine upper decay thresholds from Gaussian width bounds. As usual, D is an infinite subset of the natural numbers. This machinery allows us to compute upper decay thresholds in situations involving matrix observations. For simplicity, we consider only the space R n×n of square n × n matrices, where n ∈ N. The ambient dimension of this vector space is d = n 2 , but we will index the observations by the parameter n. This poses no difficulty, because it is equivalent to indexing over the set D = {1 2 , 2 2 , 3 2 , . . . }. Proposition 5.4. Fix ρ ∈ [0, 1]. For each n ∈ N, let X (n) 0 ∈ R n×n be a matrix with rank(X (n) 0 ) = ρn . Then the corresponding ensemble F ( · S 1 , X (n) 0 ) of feasible cones has upper decay threshold θ = 6ρ − 3ρ 2 .

Proof. From [15, Prop. 3.13], we have
The result follows upon dividing by n 2 , taking limits, and applying Corollary 5.3.
We list all of the bounds computed in our work in Table 1

Experiments
We can tackle a variety of scenarios using the theory developed in Section 4 and the decay threshold calculations of Section 5.

Morphological component analysis
We return to the MCA model of Section 1.1. Our goal is to analyze when we can demix two signals that are sparse in incoherent bases. To apply our theoretical results, we consider the demixing ensemble from Section 4.1.1.
Fix sparsity levels τ x and τ y in [0, 1]. For each dimension d ∈ N, we construct signals x 0 and y 0 in R d that satisfy nnz(x 0 ) = τ x d and nnz(y 0 ) = τ y d .
Draw a random basis Q, and suppose that we observe z 0 = x 0 +Q y 0 .
The 1 norm is a natural complexity measure for sparse vectors. Given the side information α = y 0 1 , we pose the constrained MCA problem minimize x 1 subject to y 1 ≤ α and x +Q y = z 0 . (6.1) The theory of Section 4 describes when (6.1) identifies (x 0 , y 0 ) with overwhelming probability in high dimensions in terms of decay thresholds for the ensembles {F ( · 1 , x 0 )} and {F ( · 1 , y 0 )} indexed by the dimension d .
Observe that, up to rotations, the geometry of the feasible cone F ( · 1 , w ) depends only on the number of nonzero entries in w , but not on the positions or magnitudes of the entries. For a fixed sparsity level τ ∈ [0, 1], consider an ensemble {w (d ) } with w (d ) ∈ R d and nnz(w (d ) ) = τd for each d ∈ N. In Appendix C, we compute the optimal upper decay threshold for the ensemble {F ( · 1 , w (d ) )}. We denote this value by θ 1 (τ) (see Figure 11, left panel). Therefore, the ensembles {F ( · 1 , x 0 )} and {F ( · 1 , y 0 )} have decay thresholds θ 1 (τ x ) and θ 1 (τ y ).
Theorem 4.2 implies that our demixing method (6.1) for sparse vectors succeeds with overwhelming probability in high dimensions so long as θ 1 (τ x ) + θ 1 (τ y ) < 1. The right panel of Figure 11 shows the level sets of the function θ 1 (τ x ) + θ 1 (τ y ) for (τ x , τ y ) on the unit square [0, 1] 2 . The green curve is the level set Theorem 4.2 implies that program (6.1) succeeds with overwhelming probability when the joint sparsity (τ x , τ y ) lies below the green curve.
On the other hand, our computations show that the upper decay threshold θ 1 (τ) is numerically equal to the lower decay threshold κ 1 (τ)-see the discussion in Appendix C.2. Theorem 4.3 implies that the sparse demixing method (6.1) fails with overwhelming probability for sparsity levels (τ x , τ y ) in the region above the green curve. In other words, the green curve on the right panel of Figure 11 delineates a sharp transition between success and failure for constrained MCA (6.1). The green curve in Figure 11(b) is the same as the green curve in Figure 1.

Strong guarantees
The theory of Section 4.3 allows us to provide a uniform recovery guarantee. For a fixed draw of the random basis, constrained MCA can demix all sufficiently sparse pairs of vectors with overwhelming probability in high dimensions.
Fix the sparsity (τ x , τ y ) and the ambient dimension d . Suppose Q ∈ O d is a random basis. By Lemma 2.4, constrained MCA can identify every (τ x , τ y )-sparse pair (x 0 , y 0 ) given the observation z 0 = x 0 +Q y 0 , provided that the event holds. Theorem 4.11 guarantees that the probability of event (6.2) is large when some associated decay thresholds are small enough; let us describe how to verify the required technical assumptions. First, the results in Appendix C allow us to compute upper decay threshold at levels ψ ≥ 0 for the ensemble {F ( · 1 , w (d ) )} from Section 6.1 consisting of feasible cones for the 1 norm at τ-sparse vectors. We extend our earlier notation by writing this quantity as θ 1 (τ, ψ). This is the first element required to check the hypotheses of Theorem 4.11.
We also require information on the total number of feasible cones under consideration. Let where the unions take place over all τ x d -sparse x 0 ∈ R d and all τ y d -sparse y 0 ∈ R d . There are exactly 2 k d k different-but congruent-feasible cones of the 1 norm at vectors in R d with k nonzero entries, one for each sign/sparsity pattern. This corresponds to the number of (k − 1)-dimensional faces of the crosspolytope; see, e.g., [25,Sec. 3.3]. With k = τd , it follows from the proof of Proposition 3.12 that uniformly as d → ∞. By continuity of the exponential, for every η > 0 and all sufficiently large d , the number of feasible cones is bounded above by for large enough d . Similarly, |K (d ) y | ≤ e d (E (τ y )+η) for all sufficiently large d . We have now collected enough information to apply our theory. By Theorem 4.11, the event (6.2) holds with overwhelming probability in high dimensions so long as The blue curve appearing in Figure 1 on page 3 shows the level set When the sparsity level (τ x , τ y ) lies below the blue curve, inequality (6.4) holds, so that the demixing method (6.1) succeeds at demixing every pair (x 0 , y 0 ) of (τ x , τ y )-sparse vectors with overwhelming probability in high dimensions.

Numerical experiment for constrained MCA
The following numerical experiment illustrates the accuracy of these theoretical results. We fix the dimension d = 100. For each pair (k x , k y ) ∈ {0, 1, . . . , 100} 2 , we repeat the following procedure 25 times.
1. Draw x 0 , y 0 ∈ R d with k x or k y nonzero elements, respectively. The locations of the nonzero elements are chosen at random, and these elements are equally likely to be +1 or −1.
2. Generate a random basis Q ∈ O d ; see Remark 6.1 below.
The background of Figure 1 shows the results of this experiment as a function of τ x = k x /d and τ y = k y /d . The yellow curve marks the empirical 50% success line, and we note that it tracks the green theoretical curve closely. It emerges that d = 100 is already large enough to see the high dimensional behavior described by our theoretical results.

Remark 6.1. A random basis in Q ∈ O d is often defined through a conceptually simple two-step operation.
First, draw a square d × d Gaussian matrix; second, orthogonalize the columns of this matrix via the Gram-Schmidt procedure. Although this definition has the flavor of a numerical algorithm, the conceptual process is not numerically stable. Moreover, standard procedures for stabilizing the orthogonalization do not preserve the Haar measure. For a straightforward, numerically stable approach to generating random bases, see [55].

Secure and robust channel coding
Next, we study the secure channel coding scheme of Section 1.3.1. We want to analyze when the receiver can decode a transmitted message that is subject to a sparse corruption. The difficulty depends on the sparsity level τ of the corruption, where τ ∈ [0, 1]. Let us introduce an ensemble of demixing problems. In each dimension d ∈ N, choose a d -bit message m 0 ∈ {±1} d and a corruption c 0 ∈ R d with nnz(c 0 ) = τd . Draw a random basis Q known to both the receiver and transmitter. The receiver observes z 0 = Qm 0 + c 0 , the encoded message plus the sparse interference. The natural complexity measure for the sparse corruption c 0 is the 1 norm, while the ∞ norm is the appropriate complexity measure for the sign vector m 0 . Note that m 0 ∞ = 1. To recover the original message, the receiver solves the problem minimize c 1 subject to m ∞ ≤ 1 and c +Qm = z 0 . (6.5) This approach succeeds when (m 0 , c 0 ) is the unique optimal point of (6.5).
We consider two types of corruptions. Benign corruptions are taken in any manner that is independent of Q-this would happen, for instance, when the corruption is generated by an adversary with no knowledge of Q or the transmission Qm 0 . Adversarial corruptions are worst-case sparse corruptions; these corruptions may model malicious interference or an erasure channel that sets some of the coordinates of z 0 to zero. We first consider with the benign corruption, and then consider the adversarial case in Section 6.2.2.

Benign corruptions
Since the corruption is chosen independently of the basis Q, the convex demixing method (6.5) succeeds if it can identify the single pair (c 0 , m 0 ). Theorems 4.2 and 4.3 describe where procedure succeeds, or fails, with overwhelming probability in high dimensions, but we must first determine some decay thresholds.
The feasible cone of the ∞ norm at a sign vector is congruent to an orthant (Example 2.2). From Table 1, we see that the sequence {R d + : d ∈ N} of orthants has an upper decay threshold of θ R d + = 1 2 and a matching lower decay threshold κ R d + = 1 2 . Appendix C defines an upper decay threshold θ 1 (τ) for the sequence of feasible cones of the 1 norm at τ-sparse vectors.
With these thresholds in hand, Theorem 4.2 guarantees that (6.5) succeeds with overwhelming probability in high dimensions provided that θ R d + + θ 1 (τ) < 1, or, equivalently, provided that θ 1 (τ) < 1 2 . On the other hand, Theorem 4.3 shows that (6.5) fails with overwhelming probability in high dimensions if the corresponding upper decay threshold satisfies κ 1 (τ) + κ R d + > 1. This condition holds when κ 1 (τ) > 1 2 . Numerically, we find that θ 1 (τ) < 1 2 when the sparsity level τ 0.193; see the left panel of Figure 11. The fact that κ 1 (τ) = θ 1 (τ) to numerical precision implies that κ 1 (τ) > 1 2 for τ 0.193. In other words, if fewer than 19% of the entries of c 0 are nonzero, the scheme (6.5) succeeds with overwhelming probability in high dimensions; otherwise, it fails with overwhelming probability in high dimensions. This sharp transition corresponds to the location of the dashed line in Figure 3.

The adversarial case
In the adversarial case, the corruptions are sparse but may depend on the basis Q and the message m 0 . To ensure that no corruption with τd nonzero entries can cause (6.5) to fail, we must verify that (6.
for any η > 0 and all sufficiently large d .
Since K (d ) m is a singleton, Theorem 4.11 implies that event (6.6) holds with overwhelming probability in high dimensions whenever Computing θ 1 (τ, ψ) and θ R d + (ψ) numerically, we find that for all τ 0.0186, inequality (6.7) holds. We conclude that our channel coding scheme is robust to all adversarial corruptions so long as the corruptions have no more than about 1.8% nonzero entries. This computation is illustrated in Figure 12.

Numerical experiment
We perform two numerical experiments to complement our theory, one for the benign corruptions and the other for a specific type of malicious erasure. The curves in Figure 3 show the results of these experiments. For benign corruptions, the empirical 50% success rate occurs very near the predicted sparsity value τ = 0.193, and the transition region is more narrow for larger d . Thus, the experiment closely match our prediction for the location of the asymptotic phase transition.
The empirical evidence suggests that our adversarial guarantees are conservative for the type of malicious corruption used in the experiment. This is expected, as we have no reason to believe that such erasures correspond to the worst-case corruption. However, the empirical transition between success and failure near τ ≈ 0.05 suggests that our adversarial bound lies within a factor of two or three of the best possible guarantee.

Low-rank matrices under sparse corruptions
Consider the problem of separating a low-rank square matrix from a corruption that is sparse in a random basis. The parameters that determine the difficulty are the proportional rank ρ ∈ [0, 1] and the sparsity level τ ∈ [0, 1]. Let us introduce a demixing ensemble. For each side length n ∈ N, choose a low-rank matrix X 0 ∈ R n×n with rank(X 0 ) = ρn and a sparse matrix Y 0 ∈ R n×n with nnz(Y 0 ) = τn 2 . Draw a random basis Q for R n×n , and suppose we observe Z 0 = X 0 + Q(Y 0 ).
To promote low-rank, we use the Schatten 1-norm, and to promote sparsity, we use the matrix 1 norm. Given the side information α = Y 0 1 , we pose the convex demixing method minimize We study when (X 0 , Y 0 ) is the unique solution to (6.8) with overwhelming probability in high dimensions. The feasible cone of the 1 -matrix norm at a matrix Y 0 ∈ R n×n with k nonzero elements is isomorphic to the feasible cone of the 1 norm at a sparse vector y 0 := vec(Y 0 ) ∈ R n 2 with k nonzero entries. It follows that the value θ 1 (τ) from (C.14) is an upper decay threshold for the ensemble {F ( · 1 , Y 0 )} of feasible cones indexed by the ambient dimension d = n 2 of the matrix space R n×n .

Numerical experiment
Let us summarize the experiment in Figure 4. The matrix side length n = 35 is fixed, and for each pair (ρ, τ) in the set 1 n , 2 n , . . . , 1 2 , we repeat the following procedure 25 times: 1. Draw a matrix X 0 = Q L ΛQ R ∈ R n×n with rank r = [ρn], where Λ is a diagonal matrix that satisfies Λ i i = 1 for i = 1, . . . r and Λ i i = 0 otherwise and Q L , Q R are independent random bases in O n .
2. Generate a random matrix Y 0 ∈ R n×n with [τn 2 ] nonzero entries; the nonzero entries in Y 0 take the values +1 or −1 with equal probability.
3. Generate a random basis Q for R n×n .

Declare success if
From Figure 4, we see that the theoretical bound closely matches the empirical success curve throughout the entire regime.

Assorted matrix demixing problems
We conclude this section with some other combinations of structured square matrices that we can separate using the convex demixing method (1.2). In each of these applications, we observe a superposition of the form Z 0 = X 0 + Q(Y 0 ) ∈ R n×n , where Q is a random basis for the matrix space R n×n . We consider various structures for X 0 and Y 0 -either low rank, orthogonal, sparse, or sign matrices-and we show that our theory quickly identifies a regime where an appropriate convex demixing method succeeds with overwhelming probability in high dimensions. While we know of no concrete applications for these particular demixing programs, the analysis below illustrates the ease with which our theory extends to new settings.

Orthogonal and sparse matrices
Fix a sparsity level τ in [0, 1]. For each side length n ∈ N, choose an orthogonal matrix X 0 ∈ O n and a sparse matrix Y 0 ∈ R n×n with nnz(Y 0 ) = τn 2 . We use the operator norm as a complexity measure for X 0 and the matrix 1 norm as a complexity measure for Y 0 . Since X 0 Op = 1, we pose the convex demixing method The interchange of the objective and constraint as compared with (1.2) poses no difficulty because the optimality conditions of Lemma 2.4 are symmetric with respect to the objective and constraint. By Theorem 4.2, the convex demixing method (6.9) succeeds with overwhelming probability in high dimensions so long as where θ 1 (τ), defined in Appendix C, is an upper decay threshold for the ensemble {F ( · 1 , Y 0 )} and θ Op = 3 4 is an upper decay threshold for the ensemble {F ( · Op , X 0 )} by Proposition 5.6. Therefore, program (6.9) succeeds with overwhelming probability in high dimensions whenever θ 1 (τ) < 1 4 . † Our actual computation uses the simpler, but equivalent, formula given in [5,Prop. 4.9].
This occurs for τ < 0.06; see the left panel of Figure 11. We conclude that (6.9) demixes an orthogonal matrix X 0 from a matrix sparse in a random basis Q(Y 0 ) with high probability when no more than about 6% of the elements of Y 0 are nonzero.

Low-rank and sign matrices
Fix the proportional rank ρ in [0, 1]. We abbreviate the ambient dimension d = n 2 . For each side length n ∈ N, choose a low-rank matrix X 0 ∈ R n×n with rank(X 0 ) = ρn and a sign matrix Y 0 ∈ {±1} n×n . We use the Schatten 1-norm as a complexity measure for rank and the matrix ∞ norm as a complexity measure for sign matrices. Given that Y 0 ∞ = 1, we consider the convex demixing method minimize We invoke Theorem 4.2 to see that (6.10) succeeds with overwhelming probability in high dimensions whenever θ S 1 (ρ) + θ R d + < 1. Here, θ S 1 (ρ) is an upper decay threshold for the ensemble {F ( · S 1 , X 0 )} of feasible cones, and θ R d + is an upper decay threshold for the ensemble of nonnegative orthants. By Proposition 3.12, we have θ R d + = 1 2 , while Proposition 5.4 gives θ S 1 (ρ) = 6ρ − 5ρ 2 . Therefore, the convex demixing method (6.10) succeeds with overwhelming probability in high dimensions so long as This bound is valid when ρ ≤ 0.09. We conclude that (6.10) can demix a low-rank matrix from a sign matrix in a random basis with overwhelming probability if rank(X 0 ) ≤ 0.09n, where n is side length of X 0 .

Low-rank and orthogonal matrices
Let ρ ∈ [0, 1] be a proportional rank parameter. For each side length n ∈ N, choose a low-rank matrix X 0 ∈ R n×n with rank(X 0 ) = ρn and an orthogonal matrix Y 0 ∈ O n . With the usual choice of complexity measures, the convex demixing method is minimize X S 1 subject to Y Op ≤ 1 and X + Q(Y ) = Z 0 . (6.11) By Theorem 4.2, program (6.11) succeeds with overwhelming probability in high dimensions so long as θ S 1 (ρ) + θ Op < 1. Propositions 5.4 and 5.6 imply that this occurs whenever For instance, it suffices that ρ ≤ 0.04. Therefore, the convex demixing method (6.11) can identify a superposition of a low-rank matrix and an orthogonal matrix with overwhelming probability in high dimensions so long as rank(X 0 ) ≤ 0.04n, where n is the side length of X 0 .

Prior art and future directions
This work occupies a unique place in the literature on demixing. The analysis is highly general and applies to many problems. At the same time, the results are sharp or nearly sharp. This final section offers a wideangle view of the field of demixing, from applications to analytical techniques, with a focus on methods based on convex optimization. We conclude by discussing some extensions of our current approach in the hope of encouraging further development in this field.

A short history of convex demixing and incoherence
The use of convex optimization for signal demixing has a long history. Early predecessors to morphological component analysis come from the work of Claerbout & Muir [19] and Taylor et al. [77], where 1 minimization is used to identify sparse spike trains from an observed seismic trace.
In the last decade, new classes of convex regularizers have been introduced for solving inverse problems in signal processing. In particular, the Schatten 1-norm is used for problems involving low-rank matrices [36], [64]. Demixing methods that involve the Schatten 1-norm include robust principal component analysis [12], [87], [88], [52] and latent variable selection [14]. Rigorous theoretical results for these techniques typically involve a spectral incoherence assumption, but no previous work in this area identifies phase transition behavior.

The neighborhood of this work
We take much of our inspiration from the geometric analysis of linear inverse problems in [15]. Indeed, the geometric optimality condition (Lemma 2.4) is a direct generalization of a geometric result [15,Prop. 2.1] for linear inverse problems. Moreover, the Gaussian width bounds from that work prove useful for computing the decay thresholds in this research.
A related line of work, due to Negahban et al. [56], [57], is based on the concept of restricted strong convexity. The results in these papers are sharp within constant factors, but they do not yield bounds as precise as ours. Another general approach to demixing appears in of [46], where a deterministic incoherence condition leads to recovery guarantees, even in nonconvex settings. The recovery bounds available through this method are not competitive with the guarantees we provide.
Several works also consider demixing two sparse vectors. The works [84], [58] show that a nearly dense vector could be demixed from a sufficiently sparse vector, but they do not identify phase transition behavior. Recent work [63] also offers demixing guarantees for demixing sparse vectors when the sparsity is mildly sublinear in the dimension. Their model is similar to our MCA formulation in Section 1.1, but again the results do not identify the phase transition between success and failure.

Random geometry and convex optimization
We now trace the use of methods from integral geometry for understanding randomized convex optimization programs. Vershik & Sporyshev [80] use an asymptotic analysis of polytope angles to analyze the average-case behavior of the simplex method for linear programming. The underlying formulas have their roots in the results of Ruben [67], although some of the ideas apparently go back to the work Schläfli from the mid-nineteenth century-see Ruben's paper for a discussion.
The analysis of Vershik & Sporyshev fed a line of investigation on the expected face counts of randomly projected polytopes [2], [9], a topic of theoretical interest in combinatorial geometry. These computations resurfaced in convex optimization in the line of work of Donoho & Tanner [23], [28], [25], [29], [30], [31], [33]. These articles characterize the behavior of convex optimization methods for solving several linear inverse problems under a random measurement model. In Appendix C, we leverage the asymptotic polytope angle calculations of Donoho & Tanner to compute decay threshold for the 1 norm at sparse vectors.
This asymptotic polytope angle approach also yields stability guarantees for basis pursuit [89]. Furthermore, it has been used to establish that iteratively reweighted basis pursuit can provide strictly stronger guarantees than standard basis pursuit [90], [48], [49].
Our approach to random geometry differs from these earlier works because it starts with the modern theory of spherical integral geometry. Previous research was based on an older theory of polytope angles [44], [45], [54]. Spherical integral geometry reached its current state of development in the dissertation [38], [39]. Chapter 6.5 of [69] and the notes therein summarize this research. We also draw on insights from the thesis [3].

Conclusions and future directions
The results in this work demonstrate the power of spherical integral geometry in the context of demixing. Our bounds are often tight, and they are broadly applicable. This approach raises many questions worth further attention. We conclude with a list of directions for future work. During the period that our original manuscript was under review, several of these areas have seen significant progress. We augment our original list of open problems with a summary of progress made in the interim. Multiple demixing. It would be interesting to study demixing problems involving more than two structured vectors.
A study of this problem appears in [83]. The present authors provide sharp phase transition characterizations for demixing an arbitrary number of signals in [53].
Spherical intrinsic volumes for more cones. Computation of additional decay thresholds will provide new bounds for convex demixing methods. The sharpest decay thresholds appear to require formulas for spherical intrinsic volumes. For instance, an asymptotic analysis of the spherical intrinsic volumes for feasible cones of the Schatten 1-norm would provide sharp recovery results for low-rank matrix demixing problems. Amelunxen & Bürgisser have made some recent progress in this direction by developing a formula for the spherical intrinsic volumes for the semidefinite cone [4]. Extensions to more general probability measures. The analysis in this work focuses on a specific random model. It would be interesting to incorporate more general probability measures into our framework. This may be a difficult problem; by the results of Section 5.2, this question is closely related to the observed universality phenomenon in basis pursuit [30].
Bayati et al. [6] provide a rigorous version the universality property for basis pursuit observed in [30].
It remains unclear whether their methods adapt to demixing problems considered here.

A Equivalence of the constrained and penalized methods
This appendix provides a geometric account of the equivalence between the constrained (1.2) and penalized (1.3) convex demixing methods. The results in this section let us interpret our conditions for the success of the constrained demixing method (1.2) as limits on, and opportunities for, the Lagrange demixing method (1.3). We begin with the following well-known result; it holds without any technical restrictions. We omit the demonstration, which is an easy exercise in proof by contradiction. (See also [65,Cor. 28 Before stating a partial converse to Proposition A.1, we require a technical definition. We say that a proper convex function f is typical at x if f is subdifferentiable at x but does not achieve its minimum at x. With this technical condition in place, we have the following complement to Proposition A.1. Note that there is a subtlety here: the Lagrange program may have strictly more optimal points than the corresponding constrained problem even for the best choice of λ, so that we cannot guarantee that (x 0 , y 0 ) is the unique optimum. See [65,Sec. 28] for more details.

Proof of Proposition A.2.
The key idea is the construction of a subgradient that certifies the optimality of the pair (x 0 , y 0 ) for the Lagrange penalized problem (1.3) for an appropriate choice of parameter λ. As with many results in convex analysis, a separating hyperplane plays an important role.
By Lemma 2.4, the constrained problem (1.2) succeeds if and only if F ( f , x 0 ) ∩ −QF (g , y 0 ) = {0}. The trivial intersection of the feasible cones implies that there exists a hyperplane that separates these cones. (This fact is a special case of the Hahn-Banach separation theorem for convex cones due to Klee [50].) In other words, there exists some vector u = 0 such that 〈u, x〉 ≤ 0 for all x ∈ F ( f , x 0 ), and moreover 〈u, y〉 ≥ 0 for all y ∈ −QF (g , y 0 ).
In the language of polar cones, the first separation inequality is simply the statement that u ∈ F ( f , x 0 ) • , while the second inequality is equivalent to Q * u ∈ F (g , y 0 ) • .
We will now show that u generates a subgradient optimality certificate for the point (x 0 , y 0 ) in problem (1.3) for an appropriate choice of parameter λ > 0. We denote the subdifferential map by ∂.
At this point, we invoke our technical assumption. Since f is typical at x 0 , the polar to the feasible cone is generated by the subdifferential of f at x 0 [65,Thm 23.7]. In particular, there exists a number λ f ≥ 0 such that u ∈ λ f ∂ f (x 0 ). In fact, the stronger inequality λ f > 0 holds because u = 0. For the same reason, there exists a number λ g > 0 such that Q * u ∈ λ g ∂g (y 0 ).
Define h(x) := λ f f (x) + λ g g (Q * (z 0 − x)). By standard transformation rules for subdifferentials [65,Thms. 23.8,23.9], we have is the Minkowski sum of the sets A and −B . Since u ∈ λ f ∂ f (x 0 ) and u ∈ λ g Q∂g (y 0 ), we see 0 ∈ ∂h(x 0 ). By the definition of subgradients, x 0 is a global minimizer of h. Introducing the variable y = Q * (z 0 − x), it follows that (x 0 , y 0 ) is a global minimizer of subject to x +Q y = z 0 . This is Lagrange problem (1.3) with the parameter λ = λ g /λ f > 0, so we have the result.

B Regions of failure and uniform guarantees
We now present the proofs of the results of Section 4 concerning regions of failure (Theorem 4.3) and strong demixing guarantees (Theorem 4.11) for the convex demixing method. These demonstrations closely follow the pattern laid down by the proof of Theorem 4.2.

B.1 Regions of failure: The proof of Theorem 4.3
We first state an analog of Theorem 4.4. As usual, D is an infinite set of indices.   In the proof below, the Gauss-Bonnet formula is crucial for dealing with the parity term (1 + (−1) k ) that arises in the spherical kinematic formula (3.2).
Proof of Theorem B.1. Since the Gauss-Bonnet formula only applies to cones that are not subspaces, we split the demonstration into three cases: neither ensemble {K (d ) } nor {K (d ) } contains a subspace, one ensemble consists of subspaces, or both ensembles consist of subspaces. We assume without loss that each case holds for every dimension d ∈ D; the proof extends to the general case by considering subsequences where only a single case applies.
We drop the superscript d for clarity. Assume first that neither K norK is a subspace. Let (k) = (1 + (−1) k ) be the parity term in the spherical kinematic formula (3.2). Changing the order of summation in the spherical kinematic formula, we find Let κ < κ andκ <κ with κ +κ > 1; such scalars exist because κ +κ > 1. By positivity of the spherical intrinsic volumes (Fact 3.5.1), we have We will see that the inner sum above is very close to one. Indeed, whereξ i is a discrepancy term (see (B.3) below). The second equality follows by the spherical Gauss-Bonnet formula (Fact B.2), and the assumption thatK is not a subspace. We now bound the discrepancy termξ i uniformly over i ≥ κd + 1. Since κ +κ > 1, for any i ≥ κd + 1 we have d − 2 − i ≤ κd . By definition of the lower decay threshold, we see that the discrepancy term must be small: for any i ≥ κd + 1, for some ε > 0 and all sufficiently large d . Applying (B.2) and (B.3) to (B.1), we find where the second inequality follows from Fact 3.5: the spherical intrinsic volumes are positive and sum to one. We now reindex the sum on the right-hand side of (B.4) over i = −1, 0, . . . , d − 1 with only exponentially small loss: for some ε > 0 and all sufficiently large d by definition of the lower decay threshold. Applying these observations to (B.4), we deduce that for some ε > 0 and all sufficiently large d . Since d −1 i =−1 v i (K ) = 1 by Fact 3.5.2, this shows the result when both K andK are not subspaces, completing the first case.
For the second case, suppose that only one of the cones is a subspace. Without loss, we may assumeK is the subspace by the symmetry of the spherical kinematic formula (see Remark 3.8). Denote the dimension of the subspaceK byñ := dim(K ), and take parameters κ andκ as above.
By Proposition 3.2, the spherical intrinsic volumes ofK are given by v i (K ) = δ i ,ñ−1 . Inserting this Kronecker δ into the spherical kinematic formula (3.2) and simplifying the resulting expression, we find the probability of interest is given by Reindexing the sum over k = −1, 0, . . . , d − 1, we see where the second equality holds by the spherical Gauss-Bonnet formula (Fact B.2).
We now show thatñ is relatively large. The definition of the lower decay threshold implies that there exists an ε > 0 such that v i (K ) = δ i ,ñ−1 ≤ e −ε d for all i ≤ κd when d is sufficiently large. This inequality cannot hold ifñ − 1 ≤ κd , so we deduce thatñ ≥κd for all sufficiently large d .
Sinceñ ≥κd and κ +κ > 1, we must have d −ñ − 1 < κd for all sufficiently large d . Applying the definition of the lower decay threshold, we find the sum on the right-hand side of (B.5) is exponentially small: there exists an ε > 0 such that for all sufficiently large d . The result for the second case follows immediately.
Finally, we consider the case when both of the cones are subspaces. Suppose K has dimension n, whileK has dimensionñ, and let κ,κ be as above. As in the second case, we find that n ≥ κd andñ ≥κd when d is sufficiently large. Then the inequality κ +κ > 1 implies that n +ñ > d , that is, the sum of the dimensions of the subspaces is larger than the ambient dimension. A standard fact from linear algebra implies K ∩QK = {0} for any unitary Q-in other words, for all d large enough, the probability of nontrivial intersection is one. This completes the third case, and we are done.

B.2 Proof of the strong guarantees of Theorem 4.11
Proof of Theorem 4.11. For clarity, we drop the superscript d in this proof. We begin with the union bound: the probability of interest P is bounded above by From here, the proof closely parallels the proof of Theorem 4.4, so we compress the demonstration. We consider two cases, one where at least one cone is a subspace, the other where neither cone is a subspace; the result extends to the mixed case by considering subsequences. Suppose first that at least one cone is a subspace. Let θ > θ andθ >θ with θ +θ < 1. We bound the probability on the right-hand side of (B.6) by where the Σ i are given in (4.3). The fact that θ +θ < 1 implies that Σ 1 = 0 for sufficiently large d , as in the proof of Theorem 4.4. Since θ > θ , the definition of the upper decay threshold at level ψ +ψ implies for some ε > 0 and all sufficiently large d . With analogous reasoning, we find similar exponential bounds for Σ 3 and Σ 4 : again for positive ε , ε and all sufficiently large d . Summing these inequalities and taking d sufficiently large gives for someε > 0. The claim then follows from our exponential upper bound on the growth of |K | and |K | with η =ε/2: Table 2 Notation translation between this work and [25]. Note that in the reference, Ψ net is defined for three arguments, but only depends on two parameters, namely ν and ρδ.

Parameter
Our notation Notation of [25] Sparsity ratio τ ρδ Ratio of measurements to ambient dimension σ δ Taking ε =ε/4 and d sufficiently large gives the claim in the first case. Now consider the case where both cones are subspaces, and let n := dim(K ) andñ := dim(K ). Take parameters θ > θ , andθ >θ , such that θ +θ < 1. As in the proof of Theorem 4.4, the Kronecker δ expression for the intrinsic volumes of the subspaces K andK given by Proposition 3.2, combined with the definition of the upper decay threshold, reveals that n ≤ θd andñ ≤ θ d for all sufficiently large d . The fact that θ +θ < 1 implies n +ñ < d for all sufficiently large d . Since randomly oriented subspaces are almost always in general position, the probability that K ∩QK = {0} is zero. This is the second case, so we are done.

C Decay thresholds for feasible cones of the 1 norm
This section describes how we compute decay thresholds for the feasible cone of the 1 at sparse vectors. The polytope angle calculations appearing in [25] form an important part of this computation. For convenient comparisons, Table 2 provides a map between our notation and that of the reference.
Fix a sparsity parameter τ ∈ [0, 1], and let D be an infinite set of indices. For each dimension d ∈ D, we define a vector x (d ) ∈ R d such that nnz(x (d ) ) = τd . The following results describes the behavior of the spherical intrinsic volumes of the feasible cone F ( · 1 , x (d ) ) in terms of the sparsity τ and the normalized index θ = i /d when d is large.
Lemma C.1. Consider the ensemble above. There exists a function Ψ total such that, for every ε > 0 and all sufficiently large d ∈ D, we have We discuss the definition and computation of the normalized exponent Ψ total in Section C.1. This function provides decay thresholds for the ensemble F ( · 1 , x (d ) ) : d ∈ D in the same way that the limit (3.5) provides decay thresholds for the ensemble of orthants. See Section C.2 for details.
Proof of Lemma C.1. We leave the dependence on the dimension implicit for clarity. Define k := τd .
We first show that (C.1) holds. The proof relies on an expression for spherical intrinsic volumes in terms of polytope angles. For a face F of a polytope P , we define β(F, P ) as the internal angle of P at F and γ(F, P ) as the external angle of P at F (see [44,Chapter 14] for the definitions). The following is an important alternative characterization of the spherical intrinsic volumes in terms of these angles.
We now specialize Fact C.2 to the case where K = F ( · 1 , x). Define the sublevel set S := {w : w 1 ≤ x 1 }. Recalling that our assumption τ > 0 implies x 1 > 0, we have where C := {w : w 1 ≤ 1} is the standard crosspolytope. The fact that x is k-sparse is equivalent to the statement that x/ x 1 lies in the relative interior of a (k − 1)-dimensional face of the crosspolytope C . Relationship (C.4) implies that there is a one-to-one correspondence between the i -dimensional faces of F ( · 1 , x) and the i -dimensional faces of the crosspolytope C that contain x/ x 1 . Since the internal and external angles only depend on the local structure of a given polytope, we find that for every nonempty face F of F ( · 1 , x) the internal and external angles satisfy whereF is the face of the crosspolytope C naturally corresponding to the face F of the feasible cone F ( · 1 , x).
A number of important relationships due to Böröczky & Henk [9] for faces of the crosspolytope C are conveniently collected in [25,Section 3.3]. In particular, we will need the following two facts: containing a given (k −1)-dimensional face of C , and 2. The high degree of symmetry of the crosspolytope ensures that the internal and external angles at these faces depend only on the dimensional parameters k and i .
Applying the observations above to equation (C.3), we find Above,F i +1 is any (i + 1)-dimensional face of the crosspolytope C , and T j is the j -dimensional regular simplex. The internal and external angles in (C.5) have explicit expressions due to [9] and the work of Ruben [67]. Donoho [25] conducts an asymptotic investigation of these formulas. To distill the essence of the analysis, Donoho gives continuous functions Ψ int (θ, τ) and Ψ ext (θ) such that, for any ε > 0 and all sufficiently large d , the inequalities hold uniformly over i = { τd , . . . , d − 1}. Moreover, it follows from Equation (3.5) that for sufficiently large d , we have 1 d where the exponent Ψ cont for the number of containing faces is defined by The function H (θ) is the entropy defined by (3.6). Equation (C.1) follows by defining and taking logarithms in (C.5). This is the first claim. We now show that, for any θ < τ, Equation (C.2) holds for all sufficiently large d . Since x/ x 1 lies in a (k − 1)-dimensional face of the crosspolytope C , every face of F ( · 1 , x) has dimension at least (k − 1). It follows immediately from Definition 3.1 that v i F ( · 1 , x) = 0 for all i < k − 1. Since k = τd , we see that (C.2) holds for all sufficiently large d so long as θ < τ. This is the second claim.

C.1 Computing the exponents
We now define the functions needed to compute Ψ total in (C.9). Recall that Ψ cont is explicitly defined in (C.8). The functions Ψ int and Ψ ext are defined in [25], but we recapitulate their definitions for completeness. where x = x(θ) is given by (C.10) above. Figure 13 displays Ψ total (·, τ) for a few values of the parameter τ. Empirically, it appears that Ψ total (·, τ) is concave for every value of τ ∈ [0, 1] and has a unique maximal value of zero.
We abbreviate the upper decay threshold at level zero by θ 1 (τ) := θ 1 (τ, 0) (C. 16) for consistency with Definition 3.9. Figure 13 illustrates the definition of θ 1 (τ, ψ). Numerically, it appears that zero is the unique maximal value of Ψ total (τ, ·) for every value τ ∈ (0, 1]. If this is indeed the case, then we would be able to deduce that θ 1 (τ) = κ 1 (τ) for all values of sparsity τ. ‡ Equation (C.12) requires a significant amount of wholly uninteresting algebraic simplification from the formulas of [25]. The key steps in this simplification follow from the equations on page 638 of the reference. In particular, we write y explicitly in terms of s with their Eq. (6.12), and then write ξ explicitly in terms of s using this expression for y-see equation (6.13) in the reference. Noting that the reference defines γ = τ θ on page 631 gives (C.12), modulo trivial simplifications.

C.3 Reconciliation with [25]
We now discuss the relationship between our spherical intrinsic volume approach and the bounds of [25], [28] for basis pursuit. Numerically, it appears that the two approaches provide equivalent success guarantees, but the expressions for the exponents seem to preclude a direct proof of equivalence. We also describe how our approach gives matching upper bounds for region of success of basis pursuit, which shows that our results are the best possible up to numerical accuracy.

C.3.1 Reconciliation with the weak threshold
Recall that basis pursuit is the linear inverse problem (5.1) with objective f (·) = · 1 . By the first part of Lemma 5.1, basis pursuit with a Gaussian measurement matrix Ω ∈ R σd ×d succeeds at recovering a k = τd -sparse vector with overwhelming probability in high dimensions, so long as the pair (τ, σ) satisfies θ 1 (τ) < σ. Then the result [25,Thm. 2] is equivalent to the statement that basis pursuit with a Gaussian matrix Ω ∈ R σd ×d succeeds with overwhelming probability in high dimensions whenever the pair (τ, σ) satisfies τ < τ W (σ). These two approaches show strong similarities, and methods provide the same results to numerical precision. Indeed, under the assumption that both τ W (σ) and θ 1 (τ) are monotonically increasing functions (this appears to hold empirically), one can show that these approaches are equivalent. Rather than dwell on this fine detail, we present a matching failure region for basis pursuit.

C.3.2 Matching upper bound
The following result shows links the lower decay threshold to regions where basis pursuit fails.
Proposition C.4. Suppose κ 1 (τ) > σ. Then basis pursuit with n = σd Gaussian measurements fails with overwhelming probability in high dimensions for the τ-sparse ensemble of Lemma C.1.
Since the function Ψ total (·, τ) has a unique maximal value of zero up to our ability to compute the functions involved (see Figure 13), we have the equality κ 1 (τ) = θ 1 (τ) to numerical precision. Coupling Proposition C.4 with our discussion in Section C.3.1 reveals that basis pursuit with a Gaussian measurement matrix exhibits a phase transition between success and failure at σ = θ 1 (τ).

Proof of Proposition C.4. Let {x (d )
0 ∈ R d } be an ensemble of τ-sparse vectors as in Lemma C.1. The null space of an n × d Gaussian matrix is distributed as QL, where L is a linear subspace of dimension (d − n). It then follows from [15, Prop. 2.1] that basis pursuit with n = σd Gaussian measurements succeeds with the same probability that QL ∩ F ( · 1 , x 0 ) = {0}. By Proposition 3.11, the value κ = (1 − σ) is a lower decay threshold for L. Our assumption implies κ 1 (τ) + κ > 1, so by Theorem B.1, we see QL ∩ F ( · 1 , x 0 ) = {0} with overwhelming probability in high dimensions. We conclude that basis pursuit fails with overwhelming probability in high dimensions.

D Proof of Lemma 5.1 and Corollary 5.3
We begin with the proof of the two claims of Lemma 5.1 concerning the relationship between the upper decay threshold and the linear inverse problem (5.1). The first result is a corollary of [15,Prop. 2.1]. We drop the superscript d for clarity.
Proof of Lemma 5.1, Part 1. Let Ω be the n × d Gaussian measurement matrix, where n = σd . The null space of Ω is distributed as QL, where Q is a random basis, and L is any fixed (d −n)-dimensional subspace of R d . Therefore, the probability that (5.1) succeeds is equal to the probability that QL ∩ F ( f , x 0 ) = {0} [15, Prop. 2.1]. By Proposition 3.11, the subspace L has an upper decay threshold θ L = 1 − σ, so that the assumption θ < σ implies that θ + θ L < 1. The claim follows from Theorem 4.4.
The second claim of Lemma 5.1 requires additional effort. We require the following technical lemma. Again, the spherical kinematic formula (3.2) is at the heart of the proof.
Proof of Lemma D.1. We split the argument into two cases: first, we consider the case where K (d ) is not a subspace, and then consider the case where K (d ) is a subspace. The general mixed-cone case follows by applying these arguments to the subsequences consisting of only one type of cone.
We drop the superscript d for clarity. Let n = σd . We first assume that K is not a subspace. By the spherical kinematic formula, the probability of interest P is given by By Proposition 3.2, v i (L) = δ i ,d −n−1 , so by replacing k with k − n, the probability above reduces to P = By assumption, we have P ≤ e −εd for all sufficiently large d , so the positivity of spherical intrinsic volumes (Fact 3.5.1) implies v k (K ) ≤ e −εd , for any k ≥ n such that k ≡ n mod 2.
It requires an additional geometric observation to remove the dependence on parity. LetL be a (d − n − 1)-dimensional subspace contained in L. By containment, it is immediate that where the last inequality is by assumption. But the same manipulations as before show so we have v k (K ) ≤ e −εd for every k ≥ n + 1 such that k ≡ n + 1 mod 2. In summary, for every d sufficiently large and any k ≥ n = σd , we have v k (K ) ≤ e −εd . By definition, σ is an upper decay threshold for the ensemble of cones K . This completes the first case. Now suppose that K is a subspace and define m := dim(K ). Since dim(L) = d − σd , we have P := P {K ∩QL = {0}} = 0, m < σd 1, otherwise because randomly oriented subspaces are almost always in general position. The assumption that P ≤ e −εd for all sufficiently large d requires that m < σd for all sufficiently large d . By Proposition 3.11, the scalar σ is an upper decay threshold for subspace K . This is the result for the second case, so we are done.
Proof of Lemma 5.1, Part 2. The results of [15] imply that the linear inverse problem (5.1) with a Gaussian measurement matrix Ω succeeds with the same probability that a randomly oriented (n − d )-dimensional subspace QL strikes the feasible cone F ( f , x 0 ) trivially. The result then follows from Lemma D.1.
We conclude with the proof of Corollary 5.3, which asserts that θ is an upper decay threshold for the ensemble {F ( f (d ) , x (d ) 0 ) : d ∈ D} whenever the bound (5.3) holds.