Universality laws for randomized dimension reduction, with applications

1.1. Randomized Dimension Reduction.; 1.2. Technical Setting.

• Randomized dimension reduction succeeds when the map’s null space avoids the data set, making random-subspace intersection the central geometric question.For a closed, spherically convex subset Ω of the unit sphere, the technical setting asks for the probability that Ω∩null(Π) is empty.Source: §1.1 · p. 5, §1.2 · p. 5

1.3. A Phase Transition for Uniformly Random Partial Isometries.

• For uniformly random partial isometries, the statistical dimension δ(Ω) marks the phase transition: success is likely when embedding dimension d exceeds δ(Ω).This result applies to closed, spherically convex sets.Source: §1.3 · p. 6

1.4. Other Types of Random Linear Maps?

• In a 100-trial experiment, independent Rademacher, 20%-sparse Rademacher, and Student t5 maps behaved almost exactly like uniformly random partial isometries.The comparison used the nonnegative unit vectors in R^64, whose statistical dimension is 32.Source: §1.4 · p. 7

1.5. A Universality Law for the Embedding Dimension.

• For closed, spherically convex sets not too small relative to ambient dimension, success transitions near δ(Ω) across independent, standardized, symmetric random maps with modest regularity.The class includes maps with an arbitrarily small but constant proportion of nonzero entries.Source: §1.5 · p. 8

1.6. A Universality Law for the Restricted Minimum Singular Value.

• For compact convex sets not too small, the restricted minimum singular value depends primarily on the set’s geometry and embedding dimension, rather than the random map’s distribution.The theorem assumes the set lies in the unit ball and the map entries are independent, standardized, symmetric, and modestly regular.Source: §1.6 · p. 9

1.7. Applications of Universality.

• The universality laws explain indistinguishable behavior across random measurements in compressed sensing and show that certain random codes correct sparse errors independently of codebook choice.They also indicate that the facial structure of convex hulls of suitable independent random vectors depends little on their distribution.Source: §1.7 · p. 10
• The results guide implementation-friendly numerical algorithms, yield a new proof of the Bai–Yin law, and establish universality for LASSO prediction error across broad random designs and error models.They also show LAD regression can correct a small number of arbitrary errors and suggest random neural activity may support dimension reduction with shared behavior.Source: §1.7 · p. 10

1.8. The Scope of the Universality Phenomenon.

• Universality has limits: the ℓ1 restricted minimum singular value and restricted maximum singular value can depend on the random map, even when Euclidean minimum-singular-value behavior is universal.For convex Lipschitz optimization, the authors consider universality likely; for shifted Euclidean balls, the Euclidean phase transition and minimum singular value are universal while the ℓ1 functional is not.Source: §1.8 · pp. 10–11

1.9. Reproducible Research.

• MATLAB code reproduces the figures from stored data, reruns experiments for new instances, and lets readers explore parameter changes.The authors rely on the code rather than detailed recitations of the numerical experiments.Source: §1.9 · p. 11

1.10. Roadmap.

• The paper has five parts: universality laws and proof comments; applications and empirical confirmation; proofs of universal restricted-minimum-singular-value behavior and likely success; a proof of likely failure; and background, acknowledgments, and references.Part III’s argument also yields the condition under which randomized embedding is likely to succeed.Source: §1.10 · pp. 11–12
• The simplex experiment illustrates non-universality of the restricted maximum singular value across four random-map distributions, with markers estimated over 100 trials.It applies random linear maps from R^64 to R^d to the probability simplex Δ64.Source: Figure 1.6 · p. 12, §1.10 · p. 12

1.11. Notation.

• The notation distinguishes scalars, vectors, matrices, sets, and random variables, and uses indexed subscripts for restricted vectors and matrix submatrices.Roman letters denote universal constants, which may vary between appearances; subscripts can specify particular constant values.Source: §1.11 · p. 12

A. If there is a single index AJ, it always refers to the column submatrix indexed by J.

• The analysis uses real Euclidean spaces, ℓ2 norms, positive- and negative-part functions, and standard probability notation; γ, bold γ, g, h, and Γ denote standard normal variables, vectors, and matrices.The expectation convention makes E X^2 the expectation of the square, and 1_A denotes an event indicator.Source: A. If there is a single index AJ, it… · p. 12

Part I. Main Results.

• The paper presents the embedding-dimension phase transition as a universality law alongside a second law for restricted minimum singular values.Proof details for these results are deferred to Parts III and IV.Source: Part I. Main Results · p. 13

2.1. Bounded Random Matrix Model.

• The bounded-matrix model requires independent, mean-zero, variance-one, symmetric entries bounded in absolute value by B, without requiring identical distributions.In some cases, symmetry can be dropped; Rademacher matrices are an example with B = 1.Source: §2.1 · p. 13

2.2. Heavy-Tailed Random Matrix Model.

• Model 2.4 allows independent, symmetric, standardized entries with bounded pth moments for p > 4, including Student t entries with α > 4; sparsification preserves the model with ν′ = α^-1/pν.The model admits heavy-tailed entries; sparsification keeps p unchanged while modifying ν.Source: §2.2 · pp. 13–14

3.1. Embedding Dimension: Problem Formulation.

• The embedding problem asks whether Π(E) excludes the origin, with success probability intended to depend chiefly on d and E’s size measure, not the distribution of Π.The set E is assumed nonempty, compact, and to exclude the origin.Source: §3.1 · p. 15

3.2. Some Concepts from Spherical Geometry.

• Spherical retraction removes dependence on point scale, and spherical convexity is required for a complete analysis of projection success and failure.The retraction of a compact convex set excluding the origin is compact and spherically convex.Source: §3.2 · p. 15

3.3. The Statistical Dimension Functional.

• Statistical dimension is the geometric measure of set content governing how success probability changes with the embedding dimension.It is monotone under set inclusion and agrees with linear dimension on subspaces.Source: §3.3 · pp. 15–16

3.4. Theorem I: Universality of the Embedding Dimension.

• For sufficiently large ambient dimension and δ(E) proportional to D, maps from Model 2.4 likely succeed when d exceeds δ(E) and fail when d is smaller, if θ(E) is spherically convex.The result requires a nonempty compact E excluding the origin; the failure guarantee also requires that its statistical dimension is not too small relative to D.Source: §3.4 · p. 17

3.5. Theorem I: Proof Strategy.

• The proof strategy converts the embedding question to an analytic problem by passing from E to its spherical retraction and identifying conditions for a linear map to annihilate points in that set.The strategy uses spherical duality when the retracted set is spherically convex.Source: §3.5 · p. 18
• A dimension-counting argument handles the subspace case, while separation and duality yield the required intersection conclusion in the general case.The proof strategy also derives Theorem I(a) from restricted minimum singular value universality (Corollary 10.1) and Theorem I(b) from a positive-margin condition when d ≤ (1+ε)δ(Ω), with high probability (Corollary 17.1).Source: §3.5 · p. 18

3.6. Theorem I: Extensions.

• The authors characterize Theorem I as a first step toward a broader theory of universality in high-dimensional stochastic geometry.They describe the scope of the phenomenon as an open challenge with opportunities to improve the result.Source: §3.6 · p. 19
• Theorem I establishes only an o(D)-wide phase transition; the authors ask how width behaves for more general random maps and when the theorem extends to sets with δ(E) much smaller than the ambient dimension.They also note empirical evidence of universality beyond Model 2.4, including for structured random maps, and ask when universality of successful-embedding probability can be formalized.Source: §3.6 · p. 19

4.1. Restricted Minimum Singular Value: Problem Formulation.

• The restricted minimum singular value measures the distance of the projected set from the origin and the stability of inverting the map on its image.It generalizes the ordinary minimum singular value, recovered by taking T=S^(D−1).Source: §4.1 · p. 19, §4 · p. 19

4.2. The Excess Width Functional.

• The sign of the d-excess width indicates whether random dimension reduction succeeds or fails with high probability, and the functional captures the set’s relevant geometric content.The excess width is weakly increasing in its parameter and decreases under set inclusion.Source: §4.2 · pp. 19–20

4.3. Theorem II: Universality for the Restricted Minimum Singular Value.

• Under Model 2.4, when D≥N, λD≤d≤D^(6/5), and E_d(E) is at least ϱ√d, the distance from Π(E) to the origin is typically close to E_d(E), from below and, for convex E, from above.The theorem is vacuous when E_d(E)≤0; for spherically convex θ(E), E_d(θ(E))+o(D)≤0 implies σmin(Π;E)=0 with high probability.Source: §4.3 · pp. 20–21

4.4. Theorem II: Proof Strategy.

• The proof compares the map with a Gaussian matrix using Lindeberg exchange, dissecting E so large coordinates do not make column replacement errors intolerable.For subsets with small coordinates outside J, the argument replaces only columns in Jc and uses Gaussian minimax, convex duality, and random-matrix estimates to relate the hybrid map’s RSV to the full set’s excess width.Source: §4.4 · p. 22

4.5. Theorem II: Extensions.

• The analysis estimates the RSV by excess width with error at most o(√D), while whether universality holds for very small excess width or broader map classes remains open.For standard normal matrices, the error has constant order [TOH15, Thm. II.1].Source: §4.5 · p. 22
• The proposed approach may extend universality to other convex Lipschitz functionals, but restricted maximum singular values are non-universal for many sets under Model 2.4.The paper identifies determining the full scope of the universality principle as an open challenge.Source: §4.5 · p. 22

5.1. The Phase Transition for Sparse Signal Recovery.

• For sparse-signal ℓ1 recovery, success probability transitions from zero to one within o(n) measurements around nψℓ1(s/n), with the location independent of the measurement distribution in Model 2.4.This extends the Gaussian phase transition to a broad class of random measurement matrices and resolves the open question identified in.Source: §5.1 · pp. 23–24
• The sparse-signal phase-transition proposition is informative when sparsity is proportional to dimension; finer arguments extend it to s proportional to n^(1−ε), while the vanishing-sparsity limit for universality remains open.Universality for measurement systems more structured than Model 2.4 also remains an open question.Source: §5.1 · p. 25

5.2. Other Signal Recovery Problems.

• For minimizing a convex complexity measure from random measurements, recovery has a phase transition at the statistical dimension of the measure’s descent directions for every map in Model 2.4.The framework includes sparsity via the ℓ1 norm and low-rank structure via the Schatten 1-norm.Source: §5.2 · p. 26

5.3.1. Geometric Implications.

• The ℓ1 recovery phase transition also describes whether random projection preserves a specified face of the ℓ1 ball, equivalently informing the facial structure of convex hulls of random points.For the associated random-point face, the cited conditions state that it is likely preserved below the threshold and unlikely above it.Source: §5.3.1 · p. 27

5.3.2. Other Signal Processing Applications.

• The universality laws can analyze precise compressed-detection and classification behavior for more general random linear maps, beyond prior qualitative or Gaussian-only analyses.The applications include deciding whether a signal is a noisy template or whether it belongs to one of two classes.Source: §5.3.2 · p. 27

6. DECODING WITH STRUCTURED ERRORS.

• A large family of random codes can correct structured errors at a universal error level, including sparse discrete codebooks closer to practical coding schemes.The random-decoding result also has interpretations for least-absolute-deviation regression and a class of demixing problems.Source: §6 · p. 27, §6.1 · p. 29

6.1. Decoding with Sparse Errors.

• For Model 2.4 codebooks, ℓ1 decoding succeeds with probability 1−o(1) below the universal error threshold and fails with probability 1−o(1) above it.The result assumes m ≤ n and s ≤ (1−ξ)n; it applies to arbitrary messages and errors independent of the codebook.Source: §6.1 · p. 28
• Least-absolute-deviation regression identifies the true model exactly when the contaminated-data fraction satisfies s/n < ψ^-1.The method fits observations y = X β⋆ + z, where z contains a small number of arbitrary statistical errors.Source: §6.1 · p. 29
• The paper presents its result as the first precise decoding analysis for codebooks with more general distributions, extending beyond prior standard-normal and random-orthogonal analyses.Source: §6.1 · p. 29

6.2. Other Demixing Problems.

• The decoding problem is an instance of convex demixing, and the universality results can also study other problems of this type [ALMT14].Source: §6.2 · p. 30
• For two low-complexity signals observed in superposition, demixing requires information equal to their summed complexities, a result holding for a wide class of distributions on Φ0 and Φ1.The statistical dimension of the direct product of the two descent sets is the sum of their statistical dimensions.Source: §6.2 · p. 30

7.1. Subspace Embeddings.

• For sufficiently large ambient dimension, Model 2.4 maps embed each k-dimensional subspace with probability 1-o(1) when d≥k+o(D), including sparse Rademacher maps with a fixed, arbitrarily small nonzero-entry proportion.The stated error constants depend only on the Model 2.4 parameters p and ν.Source: §7.1 · p. 31
• The arguments also yield a new proof of a slightly weaker Bai–Yin limit for the minimum singular value of random matrices drawn from Model 2.4.The proof modifies the subspace-embedding argument; the classical Bai–Yin law gives the corresponding conclusion almost surely under a four-finite-moments condition.Source: §7.1 · pp. 31–32

7.2. Sketching and Least Squares.

• With high probability, sketching least squares has negligible excess error when d is comparable to D and exceeds (1+ϱ)n; the result also improves on prior bounds and assumptions.The analysis extends to least-squares problems with convex constraint sets, for which the authors report optimal bounds.Source: §7.2 · p. 32

8. THE PREDICTION ERROR FOR LASSO

• This is the first general universality result for LASSO prediction error, extending the Gaussian-design result [OTH13] to more general random models, including heavy-tailed predictors and noise.Source: §8 · p. 35, §8.1 · p. 35, §8.2 · p. 39

8.1. The Sparse Linear Model and the LASSO.

• In the sparse model, only predictors with nonzero true coefficients are relevant, and prediction error is controlled by squared coefficient-estimation error.Source: §8.1 · p. 35
• Under the stated sample-size conditions, Proposition 8.1 bounds LASSO mean squared prediction error with high probability; the bound is sharp when n ≫ pψ_ℓ1(s/p) or σ² → 0.The conditions include λp ≤ n ≤ p^6/5 and n ≥ (1+ϱ)pψ_ℓ1(s/p).Source: §8.1 · p. 36
• The theorem assumes n is roughly comparable to p, while analogous results are said to hold for many other convex constraints.The authors note that relaxing the sample-size condition may be possible, but their argument does not establish a stronger conclusion.Source: §8.1 · p. 36

8.2. Proof of Proposition 8.1.

• The proof bounds the LASSO optimizer’s coefficient-error norm with high probability, then uses that bound to obtain the prediction-error bound.Source: §8.2 · pp. 37–38

9.1. Theorem 9.1: Main Result for the Bounded Random Matrix Model.

• For bounded Model 2.1, Theorem 9.1 gives concentration of the squared RSV, an excess-width lower bound, and a convex-set upper bound, even when entries are nonsymmetric.The lower bound concerns the expected squared RSV; the upper bound applies when T is convex.Source: §9.1 · p. 40

9.2. Proof of Theorem 9.1(1): Concentration.

• Theorem 9.1(1) is proved by concentration inequalities derived using the entropy method.The concentration claim is established in Proposition 11.1.Source: §9.2 · p. 40

9.3. Setup for Proof of Theorem 9.1(2) and (3): Dissection of the Index Set.

• For the lower- and upper-bound proofs, T is dissected into subsets TJ whose coordinates outside J are sufficiently small, allowing control of the number of subsets examined.Convexity of T ensures each TJ is convex.Source: §9.3 · p. 41

9.4. Proof of Theorem 9.1(2): Lower Bound for the RSV.

• The lower-bound proof uses Lindeberg exchange to replace only the small-coordinate columns indexed by Jc with Gaussian columns, requiring k ≥ m^2/3.It then compares the expected RSV with excess width.Source: §9.4 · p. 41

9.5. Proof of Theorem 9.1(3): Upper Bound for the RSV of a Convex Set.

• The convex-set upper-bound proof also exchanges matrix entries for Gaussian variables and compares RSV with excess width, using convex duality and convexity of TJ.The argument also requires k ≥ m^2/3.Source: §9.5 · p. 42

10.1. Corollary 10.1: Main Result for the p-Moment Random Matrix Model.

• For p > 4, Corollary 10.1 extends the RSV bounds to Model 2.4, giving high-probability excess-width lower bounds and, for convex T, upper bounds.The proof truncates matrix entries, applies Theorem 9.1 to the bounded part, and controls the tails with a norm bound.Source: §10.1 · p. 43

10.2. Proof of Theorem II from Corollary 10.1.

• Theorem II follows from Corollary 10.1 by applying it with Φ = Π and T = E, then choosing the ambient dimension large enough to control the error term.The argument uses the positive exponent κ(p) for p > 4.Source: §10.2 · pp. 43–44

10.3. Proof of Theorem I(a) from Corollary 10.1.

• For d ≥ (1 + ε)δ(E), Corollary 10.1 supplies the restricted-singular-value lower bound used to derive the first half of Theorem I(a).The proof reduces to d = ⌈(1 + ε)δ(E)⌉.Source: §10 · p. 43, §10.3 · p. 44

11. THEOREM 9.1: CONCENTRATION FOR RESTRICTED SINGULAR VALUES

• The restricted minimum singular value of a bounded random matrix concentrates about its mean, yielding Theorem 9.1(1).Source: §11 · p. 45

11.1. Proposition 11.1: The Lower Tail of the RSV.

• The lower-tail result shows that a bounded random matrix’s restricted singular value is unlikely to fall much below its mean.The proof uses an exponential-moment inequality derived from Massart’s modified logarithmic Sobolev inequality.Source: §11.1 · pp. 45–46

11.2. Proposition 11.1: The Upper Tail of the RSV.

• The upper-tail result shows that a bounded random matrix’s restricted singular value is unlikely to rise much above its mean.Its proof uses a self-bounded random-variable tail inequality, also derived from Massart’s modified log-Sobolev inequality.Source: §11.2 · p. 46

12. THEOREM 9.1: PROBABILITY BOUNDS FOR DISSECTIONS

• The section compares expectations of minima indexed by a set with expectations of minima indexed by its subsets, using concentration phenomena.Source: §12 · p. 47

12.1. Dissection of the Excess Width.

• The excess width of a closed set in the unit ball is related to the excess widths of a finite decomposition into closed subsets.Source: §12.1 · p. 47

12.2. Dissection of the Restricted Singular Value.

• The restricted minimum singular value on a closed set in the unit ball is controlled by the corresponding values on its finite decomposition into closed subsets.The result assumes a random matrix satisfying Model 2.1 with uniform bound B.Source: §12.2 · p. 48

13. THEOREM 9.1: REPLACING MOST ENTRIES OF THE RANDOM MATRIX

• Under Model 2.1, entries in columns Jc can be replaced by standard normals with little change in the restricted minimum singular value when |t_j| ≤ k^-1/2 for every j ∈ Jc.The condition is essential because it controls the errors incurred during replacement.Source: §13 · p. 49

13.1. Proof of Proposition 13.1.

• The proof chooses ε = (mn)^-1 and β^3 = k^(3/2)/(B^6m); when B ≥ 1 and m^(2/3) ≤ k ≤ n, its third error term dominates.The argument discretizes the index set, passes to a soft minimum, and compares expectations by exchanging entries.Source: §13.1 · pp. 49–50

13.2. Proposition 13.1: Discretizing the Index Set.

• A volumetric argument constructs an ε-cover of TJ with at most (3/ε)^n points, enabling discretization while bounding the resulting error for both Φ and Ψ.The covering argument cites [Ver12, Lem. 5.2].Source: §13.2 · p. 50

13.3. Proposition 13.1: Smoothing the Minimum.

• The proof replaces the minimum over the finite index set with a differentiable soft-min, whose expected value differs from the discrete minimum by a controlled smoothing cost for both Φ and Ψ.The bound follows from elementary bounds on the sum defining the soft-min.Source: §13.3 · p. 51

13.4. Proposition 13.1: Exchanging the Entries of the Random Matrix.

• The exchange step compares soft-min expectations after replacing ΦJc with ΨJc, using successive row replacements and the bounded coordinates of the discretized index set.The matrices share entries on J, while Ψ has independent standard normal entries on Jc; smoothness makes each exchange error small.Source: §13.1 · p. 49, §13.4 · pp. 51–52

13.4.1. Lemma 13.4: Comparison Principle for One Row.

• A one-row comparison supports the exchange argument by applying the Lindeberg principle to independent, standardized bounded entries and their Gaussian replacements.The principle uses a third-order Taylor expansion, with first- and second-order terms canceling because the variables have matching means and variances.Source: §13.4.1 · pp. 52, 54

13.4.2. Sublemma 13.5: Derivative Calculations.

• The derivative calculation bounds the soft-min's third derivative using Jensen’s and Lyapunov’s inequalities, then uses a correlation inequality to simplify averages over the index set.The correlation inequality is [BLM13, Thm. 2.14].Source: §13.4.2 · pp. 54–56
• Substituting (13.23) and (13.24) into (13.22) yields an inequality, and the result follows by expressing the μ* averages as expectations over a random vector v ∈ T ε.Source: §13.4.2 · p. 56

14. THEOREM 9.1: BOUNDING THE RESTRICTED SINGULAR VALUE BY THE EXCESS WIDTH

• Proposition 14.1 relates the hybrid matrix’s restricted singular value to the excess width of T_J.The setup uses a random matrix Φ from Model 2.1, a standard Gaussian matrix Γ, and the hybrid matrix Ψ(J).Source: §14 · p. 56

14.1. Proof of Proposition 14.1.

• The lower bound applies to general closed T_J, while the upper bound assumes convexity and uses k ≥ m^1/2 to simplify its error term.The proof first reduces the bounds to expressions involving Gaussian vectors, then relates them to the excess width.Source: §14.1 · p. 57

14.2. Proposition 14.1: Moment Comparison Inequality for the Hybrid RSV.

• Lemma 14.2 provides a moment comparison between the expected square of the hybrid restricted singular value and its expectation.Its proof applies moment comparison to Φ conditional on Γ, then to Γ.Source: §14.2 · pp. 57–58

14.3. Proposition 14.1: The Role of the Gaussian Minimax Theorem.

• The Gaussian Minimax Theorem converts matrix probability bounds into bounds involving Gaussian vectors; convexity also permits complementary bounds through convex duality.The argument formulates a saddle-point problem and applies the theorem, with an approximation step to handle the full set T_J × B_m.Source: §14.3 · pp. 58–59

14.4. Proposition 14.1: Reducing the Gaussian Matrix to Some Gaussian Vectors.

• Lemmas 14.5 and 14.6 give lower and upper bounds that reduce the Gaussian matrix to independent standard Gaussian vectors.Both results are stated for a fixed matrix A; the upper-bound lemma follows the lower-bound argument and invokes the complementary minimax bound.Source: §14.4 · p. 61

14.5. Proposition 14.1: Removing the Remaining Part of the Original Random Matrix.

• Lemma 14.7 removes the remaining original-matrix component under the independent standardized-entry assumption, which applies in particular to Φ.The resulting matching bounds complete this step of the proof.Source: §14.5 · p. 62

14.6. Proposition 14.1: Replacing the Coordinates Missing from the Excess Width.

• Lemmas 14.8 and 14.9 bound the effect of restoring coordinates in J to the excess-width-like functional involving g_{J^c} · t_{J^c}.The lower-bound argument uses independence of g_J and g_{J^c}.Source: §14.6 · p. 63
• The proof’s final step uses the fact that #J = k.The preceding passage characterizes the calculation as easy but gives no further details.Source: §14.6 · p. 63

15.1. Proof of Corollary 10.1.

• For convex T, a similar truncation argument gives the corresponding upper bound using Theorem 9.1(3) to control the expected restricted singular value.The expectation-bound error term becomes R^4(m+n)^0.94.Source: §15.1 · pp. 63–64
• Truncating each entry splits Φ into a bounded matrix covered by Theorem 9.1 and a centered tail controlled by a matrix norm bound, yielding the restricted-singular-value lower bound.The truncated entries are independent, symmetric, standardized, and bounded by 2R; tail entries have variance at most Cν^pR^(2−p) and pth moments at most (2ν)^p.Source: §15.1 · pp. 63–64

15.2. Corollary 10.1: Truncation of Individual Random Variables.

• The scalar truncation lemma decomposes a standardized symmetric variable into a standardized symmetric truncated part and a centered tail with pth moment at most (2ν)^p.The argument assumes p>4 and a truncation parameter R satisfying the stated condition in Lemma 15.1.Source: §15.2 · p. 65

• The part establishes Theorem I(b), the second part of the embedding-dimension universality law, by giving a condition for high-probability failure of random projection.Source: Part IV. Universality of the Embedding… · p. 67
• Section 16 gives a condition under which a bounded random matrix maps a point in a set to the origin.Source: Part IV. Universality of the Embedding… · p. 67
• Section 17 extends the argument to heavy-tailed Model 2.4, and Section 17.2 uses that result to derive Theorem I(b).Source: Part IV. Universality of the Embedding… · p. 67

16.1. The RAP Functional: Dual Condition for Failure.

• The RAP functional uses the polar cone in its inner minimum, and a positive value is a sufficient condition for the map to send some point of the set to zero.The same sufficient-condition principle also applies when the cone is a subspace.Source: §16.1 · p. 67

16.2. Theorem 16.2: Main Result for the Bounded Random Matrix Model.

• Under m+n ≤ min{m,n}^{9/8}, Theorem 16.2 bounds the squared RAP functional’s lower-tail deviation on a B,m,n-dependent scale and bounds its expected square below for Model 2.1.The result uses the symmetry assumption in Model 2.1.Source: §16.2 · p. 67

16.3. Proof of Theorem 16.2: Lower Tail Bound.

• The lower-tail proof adapts the argument for the squared restricted minimum singular value, showing that the squared RAP functional does not deviate substantially below its mean.The proof omits repetitive details.Source: §16.3 · p. 68

16.4. Proof of Theorem 16.2: Truncation and Dissection.

• For the expected-square lower bound, the proof truncates the polar cone to a wedge and dissects sets into subsets indexed by coordinate sets of cardinality k.The proof uses the heuristic that k is much smaller than either ambient dimension.Source: §16.4 · p. 68

16.5. Proof of Theorem 16.2: Lower Bound for RAP Functional.

• The lower-bound argument controls truncation error, exchanges the bounded matrix for one with standard normal entries, and uses the Gaussian Minimax Theorem to identify a geometric functional.The proof discretizes sets, smooths minima with soft-min, applies the Lindeberg principle, and sequences the estimates to obtain Theorem 16.2(2).Source: §16.5 · pp. 68–69

17. WHEN EMBEDDING FAILS FOR A HEAVY-TAILED RANDOM MATRIX

• Section 17 extends Theorem 16.2 to Model 2.4 and uses the extension to derive the second half of the embedding-dimension universality result, Theorem I(a).The supplied passage states this connection as the section’s purpose; the corollary is the heavy-tailed extension.Source: §17 · p. 69, §17.1 · p. 69

17.1. Corollary 17.1: Main Result for the p-Moment Random Matrix Model.

• For p > 4 and ν ≥ 1, Corollary 17.1 extends the RAP bound to Model 2.4 random matrices, with κ(p) and constants c_p, C_p strictly positive and depending only on p.The corollary concerns a closed convex cone K in R^m and Ω = K ∩ S^{m−1}; the supplied passage does not show the probability-bound formula.Source: §17.1 · p. 69

17.2. Proof of Theorem I(b) from Corollary 17.1.

• Theorem I(b) follows from Corollary 17.1 in the failure regime d ≤ (1−ε)δ(E), for compact E excluding the origin with δ(E) ≥ ϱD and a Model 2.4 map.The proof uses the corollary to obtain a positive lower bound on the RAP functional for the cone generated by the spherical retraction of E.Source: §17.2 · p. 70

17.3. Proof of Proposition 6.1: Application of RAP functional to decoding with structured errors.

• Under the condition in (17.4), the ℓ1 decoding application yields Ω ∩ range(Φ) = ∅ with probability 1−o(1).The proof identifies this with the Theorem I(b) failure regime using d = m, D = n, E = Ω◦, and Π = Φ∗; the stated sparsity condition ensures δ(Ω◦) is proportional to n.Source: §17.3 · pp. 70–71

18. THEOREM 16.2: TRUNCATION OF THE CONE

• For S = K◦ ∩ R B_m, Proposition 18.1 truncates the cone to a bounded set under Theorem 16.2’s hypotheses.The section’s stated purpose is to show that truncation changes τ_min(Φ;K) little enough to permit discretization arguments.Source: §18 · p. 71
• Concentration of the random matrix norm makes the minimizing vector s⋆ unlikely to have large norm, supporting the cone-truncation argument.The proof combines this norm control with bounds on the probability that the minimizer falls outside the truncated set.Source: §18 · p. 71

19. THEOREM 16.2: REPLACING MOST ENTRIES OF THE RANDOM MATRIX

• Replacing most entries of Φ with standard normal variables leaves Eτ2 min(Φ;K) substantially unchanged.Source: §19 · p. 72
• For the partial-replacement setup, I and J each have size k, and the sets constrain coordinates outside them by Rk^-1/2 and k^-1/2, respectively; Γ is standard normal.Source: §19 · p. 72

19.1. Proof of Proposition 19.1.

• The proof balances discretization, soft-min smoothing, and Lindeberg exchange errors, choosing ε=(mn)^-1 and β^3=k^3(m+n)/(B^3R^3mn).Source: §19.1 · pp. 72–73

19.2. Proposition 19.1: Discretizing the Index Sets.

• For ε∈(0,1], the index sets admit finite ε-coverings, and the discretization bound also holds when Φ is replaced by Ψ.Source: §19.2 · p. 73

19.3. Proposition 19.1: Smoothing the Minimum.

• The proof replaces the minimum with a soft-min at parameter β>0, and the smoothing estimate also holds when Φ is replaced by Ψ.Source: §19.3 · p. 73

19.4. Proposition 19.1: Exchanging the Entries of the Random Matrix.

• The exchange step replaces rows indexed by I^c, controlling the accumulated error through a single-row comparison under the stated coordinate constraints.Source: §19.4 · pp. 73–74

20. THEOREM 16.2: BOUNDING THE RAP FUNCTIONAL BY THE EXCESS WIDTH

• Proposition 20.1 gives an excess-width bound for the RAP functional after replacing Φ with the hybrid matrix Ψ.The setup takes Ω = K ∩ S^{m−1} and adopts Proposition 19.1’s notation and hypotheses.Source: §20 · pp. 74–75

20.1. Proof of Proposition 20.1.

• The proof writes the target as a minimax, applies the Gaussian Minimax Theorem to replace a Gaussian matrix with two Gaussian vectors, then identifies Gaussian width.The remaining random matrix Φ is treated as negligible in the overview; the vector terms contribute the width and a dimensional factor.Source: §20 · p. 75, §20.1 · p. 75

20.2. Proposition 20.1: Duality for the RAP Functional.

• For closed convex K, minimax duality gives min_{s∈K°} ||s − Ψt|| ≥ max_{u∈K∩B_m} u·Ψt.The argument uses the polar-cone support function, which is zero on K and infinite outside it.Source: §20.2 · p. 76

20.3. Proposition 20.1: Reducing the Gaussian Matrix to Some Gaussian Vectors.

• The Gaussian-matrix reduction replaces the Gaussian block of Ψ with independent standard normal vectors g and h.In the proof overview, the term involving g generates W(U), while the h term contributes a dimensional factor.Source: §20.1 · p. 75, §20.3 · p. 76

20.4. Proposition 20.1: Finding the Gaussian Width.

• The Gaussian-width estimate is built by simplifying the minimax in two stages, reducing it to scalar optimization, and deriving probabilistic bounds for its terms.The scalar problem is bounded by balancing an increasing and a decreasing branch when their crossing lies in [0,1].Source: §20.4 · p. 76, §20.4.1 · p. 76, §20.4.2 · p. 77

20.4.5. Sublemma 20.7: Probabilistic Lower Bound for Bilinear Minimax.

• Under k < m, X an m × k random matrix satisfying Model 2.1 with bound B, g standard normal, and U a subset of the unit ball in R^m, bounds (20.12) and (20.16) hold simultaneously with probability at least 3/4.These results are substituted into (20.11), and constants are adjusted to obtain the stated bound.Source: §20.4.5 · pp. 79, 81

20.4.6. Sublemma 20.7: Lower Estimate for the Empirical Width.

• The empirical width of U is comparable to its Gaussian width up to a logarithmic factor.The Gaussian width is at most a logarithmic factor larger than the empirical width; for bounded random matrices, this comparison is the only step requiring symmetry.Source: §20.4.5 · p. 80, §20.4.6 · p. 81

20.4.7. Sublemma 20.7: Lower Tail of the Empirical Width.

• Sublemma 20.11 gives a lower-tail result for the empirical width for a fixed unit-norm vector under Sublemma 20.9’s hypotheses.The supplied passage does not include the inequality itself.Source: §20.4.7 · p. 82
• The proof applies Talagrand’s inequality [BLM13, Thm. 8.6] to a function of bounded matrix entries.The entries of A and Z are bounded in magnitude by B; the proof uses the Euclidean unit-ball condition on t and s.Source: §20.4.7 · p. 82

Part V. Back Matter

• Appendix A presents facts about Gaussian analysis used throughout the paper.Source: Part V. Back Matter · p. 83
• Appendix B describes spectral bounds for random matrices with independent entries used throughout the paper.Source: Part V. Back Matter · p. 83
• The paper concludes with acknowledgments and a list of works cited.Source: Part V. Back Matter · p. 83

APPENDIX A. TOOLS FROM GAUSSIAN ANALYSIS

• Gaussian-analysis tools recur in the paper to study functions of Gaussian variables, including concentration results for Lipschitz functions.The appendix presents both a variance bound and a normal concentration inequality.Source: Appendix A · p. 83, §A.1 · p. 83

A.1. Concentration for Gaussian Lipschitz Functions.

• For an L-Lipschitz function of independent Gaussian variables, the appendix gives both a variance bound and a normal concentration inequality.The cited results are [Bog98, Thm. 1.6.4] for variance and [Bog98, Thm. 1.7.6] for concentration.Source: §A.1 · p. 83

A.2. The Gaussian Minimax Theorem.

• The Gaussian minimax theorem compares expectations for two centered Gaussian processes indexed by finite sets, and extends to infinite index sets by approximation.The comparison principle is attributed to Gordon [Gor85, Thm. 1.1].Source: §A.2 · p. 83

APPENDIX B. SPECTRAL BOUNDS FOR RANDOM MATRICES

• The appendix uses rough, non-asymptotic spectral estimates for random matrices with independent entries.One result bounds the tails of the largest and smallest singular values of rectangular matrices with independent, standardized, uniformly subgaussian entries.Source: Appendix B · p. 84
• For rectangular matrices with independent, standardized, uniformly subgaussian entries, the appendix provides tail bounds for the largest and smallest singular values.The bounds concern the largest singular value and the d2-th largest singular value.Source: Appendix B · p. 84
• For independent entries with bounded variances and pth moments, the appendix gives a matrix-norm tail bound based on matrix Rosenthal and concentration inequalities.The entries are centered, Var(X_ij) ≤ α, and E|X_ij|^p ≤ ν_p, with p ∈ [2, log(d1 + d2)]; the methods cited are [Tro15c, Thm. 1.1] and [BLM13, Thm. 15.5].Source: Appendix B · p. 84