...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Proceedings of the National Academy of Sciences of the United States of America >Neighborliness of randomly projected simplices in high dimensions
【24h】

Neighborliness of randomly projected simplices in high dimensions

机译：高维随机投影单纯形的邻域

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Let A be a d x n matrix and T=Tn-1 be the standard simplex in R-n. Suppose that d and n are both large and comparable: d approximate to delta n, delta epsilon (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 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 = AT is exactly the same as for T, for 0 <= k <= rho d. This implies that P is vertical bar(-)rho d(-)vertical bar-neighborly, and its skeleton Skel vertical bar(-rho d-)vertical bar(P) is combinatorially equivalent to Skel vertical bar(-rho d-)vertical bar(T). We also study a weaker notion of neighborliness where the numbers of k-dimensional faces f(k)(P) >= f(k)(T)(1-epsilon). Vershik and sporyshev previously showed existence of a threshold rho vs(delta) > 0 at which phase transition occurs in k/d. We compute and display rho vs and compare with rho(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 < rho(N) (d)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 rho vs(d)d(1 + o(1)) nonzeros, linear programming will find that solution.
机译：设A为d x n矩阵，T = Tn-1为R-n中的标准单纯形。假设d和n都很大且可比较：d近似于delta n，delta epsilon（0，1）。当从R-n的d维正投影仪的Grassmann流形中随机选择投影仪A时，我们计算投影的单纯形AT的面。我们推导rho（N）（delta）> 0的性质是，对于任何rho = f（k）（T）（1-epsilon）的较弱的邻居概念。 Vershik和sporyshev先前显示存在阈值rho vs（delta）> 0，在该阈值处发生以k / d表示的相变。我们计算并显示rho vs，并与rho（N）进行比较。推论如下。 （1）对于k

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号