Abstract
Let A be a d by n matrix, d < n. Let C be the regular cross polytope (octahedron) in Rn. 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 ∼ δn, where the projector A is chosen uniformly at random from the Grassmann manifold of d-dimensional orthoprojectors of Rn. We derive ρN(δ) > 0 with the property that, for any ρ < ρN(δ), with overwhelming probability for large d, the number of k-dimensional faces of P = AC is the same as for C, for 0 ≤ k ≤ ρd. This implies that P is centrally ⌊ ρ d ⌋-neighborly, and its skeleton Skel⌊ ρ d ⌋(P) is combinatorially equivalent to Skel⌊ ρ d⌋(C). We display graphs of ρ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,ε)-neighborliness asks if the k-faces are all simplicial and if the number of k-dimensional faces fk(P) ≥ fk(C)(1 – ε). We characterize and compute the critical proportion ρW(δ) > 0 such that weak (k,ε) neighborliness holds at k significantly smaller than ρW · d and fails for k significantly larger than ρW · d. Sectional (k,ε)-neighborliness asks whether all, except for a small fraction ε, 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 ρS(δ) > 0 guaranteeing this property for k/d ∼ ρ < ρS(δ). We display graphs of ρS and ρW.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Donoho, D. High-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to Dimension. Discrete Comput Geom 35, 617–652 (2006). https://doi.org/10.1007/s00454-005-1220-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-005-1220-0