High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension

Let A be a d by n matrix, d < n. Let C be the regular cross polytope ( octahedron) in R-n. It has recently been shown that properties of the centrosymmetric polytope P = AC are of interest for finding sparse solutions to the underdetermined system of equations y = Ax [ 9]. In particular, it is valuable to know that P is centrally k-neighborly. We study the face numbers of randomly projected cross polytopes in the proportional-dimensional case where d similar to delta n, where 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 = AC is the same as for C, for 0 <= k <= rho d. This implies that P is centrally \rho d\-neighborly, and its skeleton Skel([rho d])(P) is combinatorially equivalent to Skel([rho d])(C). We display graphs of rho(N). Two weaker notions of neighborliness are also important for understanding sparse solutions of linear equations: weak neighborliness and sectional neighborliness [ 9]; we study both. Weak (k, epsilon)- neighborliness asks if the k-faces are all simplicial and if the number of k-dimensional faces f(k) (P) >= f(k) (C)( 1 - epsilon). We characterize and compute the critical proportion rho(W)(delta) > 0 such that weak (k, epsilon) neighborliness holds at k significantly smaller than rho(W) . d and fails for k significantly larger than rho(W) . d. Sectional (k, epsilon)-neighborliness asks whether all, except for a small fraction e, of the k-dimensional intrinsic sections of P are k-dimensional cross polytopes. ( Intrinsic sections intersect P with k-dimensional subspaces spanned by vertices of P.) We characterize and compute a proportion rho(S)(delta) > 0 guaranteeing this property for k/d similar to <rho < rho(S)(delta). We display graphs of rho(S) and rho(W).