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 ρ < ρ 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}{\lfloor}{\rho}d{\rfloor}\end{equation*}\end{document} -neighborly, and its skeleton \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}Skel_{{\lfloor}{\rho}d{\rfloor}}{\mathit{(}}P{\mathit{)}}\end{equation*}\end{document} is combinatorially equivalent to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}Skel_{{\lfloor}{\rho}d{\rfloor}}{\mathit{(}}T{\mathit{)}}\end{equation*}\end{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.