Neighborliness of randomly projected simplices in high dimensions

David L. Donoho, Jared TannerProceedings of the National Academy of Sciences 2005 · DOI

TL;DR

This paper investigates how the geometric properties of a standard simplex change when it's randomly projected into a lower-dimensional space. The key finding is that for high-dimensional projections, the projected simplex surprisingly retains many of the "neighborly" properties of the original, meaning its faces and their relationships are preserved with high probability, up to a certain dimension. This has implications for understanding the behavior of high-dimensional data and the efficiency of algorithms for solving sparse linear systems.

What Problem Does This Paper Address?

When we take a high-dimensional object, like a standard simplex (a fundamental shape in geometry), and project it randomly onto a lower-dimensional space, we intuitively expect it to "lose" some of its structure. Specifically, we might expect many of its faces to collapse or merge. The question this paper tackles is: how much structure is preserved, and under what conditions? This is particularly relevant in the context of "neighborliness," a property of polytopes where subsets of vertices form faces. A polytope is k-neighborly if every subset of k vertices forms a (k-1)-face. The paper asks: when does a randomly projected simplex AT (where A is a random projection matrix and T is the original simplex) behave like a k-neighborly polytope, and how does this behavior change as the dimensions and the projection parameter vary? This question is motivated by applications in understanding the geometry of random point clouds and the performance of algorithms for solving sparse linear systems.

Methods

The core of the paper's method involves analyzing the expected number of faces of different dimensions in the projected simplex AT and comparing it to the number of faces in the original simplex T. The authors use a probabilistic approach, leveraging results from convex integral geometry. They derive an expression for the expected difference in the number of k-dimensional faces, denoted by $\Delta(k, d, n)$, which represents a "discrepancy." The key insight is that for specific conditions on k, d, and n, this discrepancy $\Delta(k, d, n)$ decays exponentially with n. This exponential decay allows them to prove that with overwhelming probability, the number of faces of the projected simplex matches that of the original simplex up to a certain dimension k. This dimension is determined by a critical threshold function, $\rho_N(\delta)$, which they define and analyze. They also compare their results to a "weak neighborliness" notion studied by Vershik and Sporyshev, which involves approximate equality of face counts.

Datasets

Not discussed in the paper. The paper deals with theoretical constructions of random matrices and geometric objects rather than empirical datasets.

Key Insights and Ideas

  • Surprising Structural Preservation: Despite being a random projection, the simplex AT retains a significant amount of combinatorial structure from the original simplex T. Specifically, its k-skeleton (the collection of faces up to dimension k-1) can be combinatorially equivalent to that of T.
  • Neighborliness Phase Transition: The paper identifies a sharp "phase transition" for k-neighborliness. There's a critical proportion $\rho_N(\delta)$ such that if k is proportional to d by a factor less than $\rho_N(\delta)$, the projected simplex is k-neighborly with high probability. Beyond this threshold, this property breaks down.
  • Connection to Gaussian Point Clouds: The results imply that a cloud of n points sampled from a high-dimensional Gaussian distribution (where n is proportional to the dimension d) will have a convex hull that "looks like a simplex" in a specific geometric sense. All points lie on the convex hull, and all subsets of a certain size form faces.
  • Implications for Sparse Solutions: The neighborliness thresholds are directly linked to the performance of linear programming in finding sparse solutions to underdetermined linear systems. A higher degree of neighborliness in the projected simplex implies that linear programming is more likely to find the sparsest solution for a wider range of problems.
  • Weak vs. Exact Neighborliness: The paper distinguishes between exact k-neighborliness (where face counts are identical) and weak neighborliness (where face counts are approximately equal). They show that the threshold for weak neighborliness, $\rho_{VS}(\delta)$, is different from and generally larger than the threshold for exact neighborliness, $\rho_N(\delta)$.

Key Results

  • Theorem 1: For a random projection A from $\mathbb{R}^n$ to $\mathbb{R}^d$ with $d \approx \delta n$, and for $k \lesssim \rho_N(\delta) d$, the projected simplex $AT^{n-1}$ has the same number of $l$-dimensional faces as $T^{n-1}$ for all $l \leq k$, with overwhelming probability as $n \to \infty$. This implies $AT^{n-1}$ is $[\rho_N(\delta)d]$-neighborly.
  • Figure 1: Visualizes the critical proportions $\rho_N(\delta)$ and $\rho_{VS}(\delta)$ as functions of $\delta$. For instance, when $d \approx n/2$ (i.e., $\delta = 1/2$), k-neighborliness holds for $k \gtrsim 0.089d$.
  • Corollary 1.1: For a typical realization of n i.i.d. Gaussian samples in $\mathbb{R}^d$ (with $d \approx \delta n$), their convex hull has the same k-skeleton as the original simplex for $k \lesssim \rho_N(\delta)d$.
  • Corollary 1.2 & 1.3: These corollaries connect the neighborliness thresholds to the ability of linear programming to find sparse nonnegative solutions. Specifically, if a solution has fewer than $\approx \rho_{VS}(\delta)d$ nonzeros, linear programming is likely to find it.

Limitations and Future Work

  • Asymptotic Regime: The results are primarily for the asymptotic regime where dimensions d and n are large and proportional. The behavior for finite dimensions might differ.
  • "Typical" Matrices: The analysis focuses on random projections chosen from the Grassmann manifold. While this captures the behavior of "typical" matrices, specific deterministic matrices might exhibit different properties.
  • Comparison of Thresholds: The paper computes and displays $\rho_N$ and $\rho_{VS}$ and notes substantial numerical differences. Understanding the precise relationship and implications of these different thresholds for various applications remains an area of interest.
  • Generalizing to Other Polytopes: The paper focuses on simplices. Extending these results to other types of high-dimensional polytopes would be a natural next step.

Summary updated

Abstract

Let A be a d x n matrix and T = T(n-1) be the standard simplex in Rn. Suppose that d and n are both large and comparable: d approximately deltan, delta in (0, 1). We count the faces of the projected simplex AT when the projector A is chosen uniformly at random from the Grassmann manifold of d-dimensional orthoprojectors of Rn. We derive rhoN(delta) > 0 with the property that, for any rho < rhoN(delta), with overwhelming probability for large d, the number of k-dimensional faces of P = AT is exactly the same as for T, for 0 < or = k < or = rhod. This implies that P is left floor rhod right floor-neighborly, and its skeleton Skel(left floor rhod right floor)(P) is combinatorially equivalent to Skel( left floor rhod right floor)(T). We also study a weaker notion of neighborliness where the numbers of k-dimensional faces f(k)(P) > or = f(k)(T)(1-epsilon). Vershik and Sporyshev previously showed existence of a threshold rhoVS(delta) > 0 at which phase transition occurs in k/d. We compute and display rhoVS and compare with rhoN. Corollaries are as follows. (1) The convex hull of n Gaussian samples in Rd, with n large and proportional to d, has the same k-skeleton as the (n-1) simplex, for k < rhoN (d/n)d(1 + oP(1)). (2) There is a "phase transition" in the ability of linear programming to find the sparsest nonnegative solution to systems of underdetermined linear equations. For most systems having a solution with fewer than rhoVS(d/n)d(1 + o(1)) nonzeros, linear programming will find that solution.
BibTeX
@inproceedings{donoho2005neighborliness,
  author = {David L. Donoho and Jared Tanner},
  title = {{Neighborliness of randomly projected simplices in high dimensions}},
  booktitle = {Proceedings of the National Academy of Sciences},
  year = {2005},
  doi = {10.1073/pnas.0502258102},
}

Loading related content...

Figure