Neighborliness of randomly projected simplices in high dimensions

Let A be a d x n matrix and T=Tn-1 be the standard simplex in R-n. Suppose that d and n are both large and comparable: d approximate to delta n, delta epsilon (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-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 <= k <= rho d. This implies that P is vertical bar(-)rho d(-)vertical bar-neighborly, and its skeleton Skel vertical bar(-rho d-)vertical bar(P) is combinatorially equivalent to Skel vertical bar(-rho d-)vertical bar(T). We also study a weaker notion of neighborliness where the numbers of k-dimensional faces f(k)(P) >= f(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-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 + o(p)(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.