Neighborliness of randomly projected simplices in high dimensions

Let A be a d x n matrix and T = [T.sup.n-1] be the standard simplex in [R.sup.n]. Suppose that d and n are both large and comparable: d [approximately equal to] [delta]n, [delta] [member of] (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 [R.sup.n]. We derive [rho]N([delta]) > 0 with the property that, for any [rho] < [rho]N([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 [less than or equal to] k [less than or equal to] [rho]d. This implies that P = is [??][rho]d[??]-neighborly, and its skeleton Skel[??][rho]d[??](P) is combinatorially equivalent to Skel[??][rho]d[??](T). We also study a weaker notion of neighborliness where the numbers of k-dimensional faces [f.sub.k](P) [greater than or equal to] [f.sub.k](T)(1 - [epsilon]). Vershik and Sporyshev previously showed existence of a threshold [rho]vs([delta]) > 0 at which phase transition occurs in k/d. We compute and display [rho]vs and compare with [rho]N. Corollaries are as follows. (1) The convex hull of n Gaussian samples in [R.sup.d], with n large and proportional to d, has the same k-skeleton as the (n - 1) simplex, for k < [rho]N (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 [rho]vs(d/ n)d(1 + o(1)) nonzeros, linear programming will find that solution. neighborly polytopes | convex hull of Gaussian sample | underdetermined systems of linear equations | uniformly distributed random projections | phase transitions