Counting faces of randomly-projected polytopes when the projection radically lowers dimension

By David L. Donoho, Jared Tanner. 2006

435 citations recorded by the source corpus.

1.1. Three surprises of high dimensions. This paper develops asymptotic methods to count faces of random high-dimensional polytopes; a seemingly dry and unpromising pursuit. Yet our conclusions have surprising implications - in statistics, probability, information theory, and signal processing - with potential impacts in practical subjects like medical imaging and digital communications. Before involving the reader in our lengthy analysis of high-dimensional face counting, we describe three implications of our results. 1.1.1. Convex Hulls of Gaussian Point Clouds. Consider a random point cloud of n points xi, i = 1, . . . , n, sampled independently and identically from a Gaussian distribution in R d with nonsingular covariance. This is a standard model of multivariate data; its properties are increasingly important in a wide range of applications. At the same time, it is an attractive and in some sense timeless object for theoretical study. Properties of the convex hull of the random point cloud X = {xi} have attracted interest for several decades, increasingly so in recent years; there is a nowvoluminous literature on the subject. The results could be significant for understanding outlier detection, or classification problems in machine learning.

Subfields: Applied Mathematics, Computational Mechanics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/a4b855842d9d014aa8a7a804f38b23f46b37195f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Mechanics

In Discrete Mathematics and Combinatorics

Citations in the corpus

Compressive Sensing with structured random matrices (2012, background): “6 Restricted Isometry Property of Gaussian and Bernoulli Random Matrices By now, many papers deal with Gaussian or Bernoulli random matrices in connection with sparse recovery, or more generally, subgaussian random matrices, [5, 23, 38, 42, 87, 114, 116].”
Hypothesis Testing in High-Dimensional Regression Under the Gaussian Random Design Model: Asymptotic Theory (2013, methodology): “They proved that, depending on the values of ( ε, δ ), the unknown vector θ 0 is either recovered exactly with probability converging to one or not recovered with probability converging to one, and characterized the boundary between these regimes.”
Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing (2009, background): “Maleki & Donoho (2009) conducted extensive empirical testing of many such algorithms and observed clear phase-transition-like behaviour, which varies from algorithm to algorithm and from the results presented here.”
Precise Undersampling Theorems (2010, background): “This more stringent condition has also been studied in [5], [10], [11], and [13], and undersampling theorems exist for this case as well.”
Message-passing algorithms for compressed sensing (2009, methodology): “We refer to [4], [5], [7], [6] for proofs and precise definitions of the curves ρCG(·;χ).”
Joint support recovery under high-dimensional scaling: Benefits and perils of ℓ 1,∞ -regularization (2008, methodology): “In order to provide keener insight into th e (dis)advantages associated with using̀1/`∞ block regularization, we specialize the remainder of our an alysis to the case of r = 2 regression problems, where the corresponding design matri cesX, i = 1, 2 are sampled from the standard Gaussian ensemble [2,”
Motion Segmentation in the Presence of Outlying, Incomplete, or Corrupted Trajectories (2010, background): “One choice, recently proposed in the sparse representation community [9], is the sparsity-preserving dimension dsp:”
Sparse subspace clustering (2009, background): “[8, 1] show that if we form Φ by sampling i.”
Compressed Sensing and Redundant Dictionaries (2007, neutral): “A general bound for Gaussian chaos (see [15, p. 65]) gives E|Z|q ≤ (q − 1)q ( E|Z|2 )q/2 (A.2) for all q ≥ 2.”
Enhancing Sparsity by Reweighted ℓ1 Minimization (2007, background): “It has been shown that l1 minimization allows recovery of sparse signals from remarkably few measurements [24,25]: supposing Φ is chosen randomly from a suitable distribution, then with very high probability, all sparse signals x0 for which ‖x0‖l0 ≤ m/α with α = O(log(n/m)) can be perfectly recovere”
Living on the edge: phase transitions in convex programs with random data (2013, background): “Donoho [29] and Donoho & Tanner [35] use the polytope-angle theory to address this question.”
SLOPE is Adaptive to Unknown Sparsity and Asymptotically Minimax (2015, background): “In the high-dimensional setting where p > n , this connects with the literature on compressed sensing, which shows that in the noiseless case, n ≥ 2(1 + o (1)) k log( p/k ) Gaussian samples are necessary for perfect recovery by (cid:96) 1 methods in the regime of interest [31, 32].”
Fast Solution of $\ell _{1}$ -Norm Minimization Problems When the Solution May Be Sparse (2008, background): “In their work on randomly projected polytopes, Donoho and Tanner showed that an upper bound for the value below which minimization recovers the sparsest solution with high probability, asymptotically behaves like as [22].”
Statistical Learning with Sparsity: The Lasso and Generalizations (2015, background): “Following Donoho and Tanner (2009), let us consider the ratios ρ = k/N and α = N/p, in which form the bound (11.”