Answers are grounded in this paper and cite their sources.
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 ρ < ρ N ( δ ) , 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 ≤ ρ d. This implies that P is [12pt]{minimal} {amsmath} {wasysym} {amsfonts} {amssymb} {amsbsy} {mathrsfs} {}{-69pt} {document} {equation*}{}{ρ}d{}{equation*}{document} -neighborly, and its skeleton [12pt]{minimal} {amsmath} {wasysym} {amsfonts} {amssymb} {amsbsy} {mathrsfs} {}{-69pt} {document} {equation*}Skel_{{}{ρ}d{}}{(}P{)}{equation*}{document} is combinatorially equivalent to [12pt]{minimal} {amsmath} {wasysym} {amsfonts} {amssymb} {amsbsy} {mathrsfs} {}{-69pt} {document} {equation*}Skel_{{}{ρ}d{}}{(}T{)}{equation*}{document} . We also study a weaker notion of neighborliness where the numbers of k -dimensional faces f k (P) ≥ f k ( T )(1 - ε). Vershik and Sporyshev previously showed existence of a threshold ρ VS ( δ ) > 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.
No takes yet. Share an insight, caveat, or question.
Donoho et al. (2005) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: