Neighborliness of Randomly-Projected Simplices in High Dimensions

Jared Tanner, David Donoho Coders: Jared Tanner, David Donoho

Code and Data Abstract

This code provides graphs of the neighborliness threshold rho computed by Donoho and Tanner relatively to the Vershick-Sporyshev one. It also presents the behavior of the exponents for the combinatorial prefactor, external and internal angle. For more information, please visit the SparseLab (Seeking Sparse Solutions to Linear Systems of Equations) website (http://sparselab.stanford.edu/).

Paper Abstract

Let A be a d by n matrix, d < n. Let T = T^n-1 be the standard regular simplex in R^n. We count the faces of the projected simplex AT in the case where the projection is random, the dimension d is large and n and d are comparable: d ~ dn, d in (0, 1). The projector A is chosen uniformly at random from the Grassmann manifold of d-dimensional orthoprojectors of R^n. We derive ?N( d) > 0 with the property that, for any ? < ? N( deter), with overwhelming probability for large d, the number of k-dimensional faces of P = AT is exactly the same as for T, for 0<=k<= ?d. This implies that P is [?d]-neighborly, and its skeleton Skel[? d] ( P) is combinatorially equivalent to Skel[?d] (T). We display graphs of ?N. We also study a weaker notion of neighborliness it asks if the k-faces are all simplicial and if the numbers of k-dimensional faces fk(P) >= fk(T)(1-e). This was already considered by Vershik and Sporyshev, who obtained qualitative results about the existence of a threshold ? VS(d) > 0 at which phase transition occurs in k/d. We compute and display ?VS and compare to ?N. Our results imply that the convex hull of n Gaussian samples in R^d, with n large and proportional to d, ‘looks like a simplex’ in the following sense. In a typical realization of such a high-dimensional Gaussian point cloud d~ dn, all points are on the boundary of the convex hull, and all pairwise line segments, triangles, quadrangles, …, [?d]-angles are on the boundary, for ?<? N(d/n). Our results also quantify a precise phase transition in the ability of linear programming to find the sparsest nonnegative solution to typical systems of underdetermined linear equations; when there is a solution with fewer than ?VS(d/n)d nonzeros, linear programming will find that solution.

Jared Tanner, David Donoho Coders: Jared Tanner, David Donoho, et al. "Neighborliness of Randomly-Projected Simplices in High Dimensions ." Proceedings of the National Academy of Sciences of the United States of America (2005).     Retrieved 09/15/2019 from researchcompendia.org/compendia/2013.133/

Page Owner

sheila@codersquid.com

created 11/12/2013

modified 01/16/2014

blog comments powered by Disqus

rmc id