Neighborliness of randomly projected simplices in high dimensions

Let A be a d × n matrix and T = T n -1 be the standard simplex in R n . Suppose that d and n are both large and comparable: d ≈ δ n, δ ∈ (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 ρ N ( δ ) > 0 with the property that, for any ρ 0 at which phase transition occurs in k / d. We compute and display ρ VS and compare with ρ 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 < ρ 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 ρ VS ( d / n ) d (1 + o (1)) nonzeros, linear programming will find that solution.