论文标题
椭圆形与随机点的接近最佳拟合
Near-optimal fitting of ellipsoids to random points
论文作者
论文摘要
给定尺寸$ d $中的独立标准高斯点$ v_1，\ ldots，v_n $，对于$（n，d）$的值，是否存在很高的概率是一个同时通过所有点的来源对称椭圆形的？将椭圆形拟合到随机点的基本问题与低级别基质分解，独立组件分析和主成分分析有连接。基于有力的数值证据，桑德森，帕里洛和威尔斯基[Proc。关于决策和控制大会，第6031-6036页，2013年]猜想，椭圆形拟合问题的问题从可行的到不可行的差异$ n $的增加，并在$ n \ sim d^2/4 $上急剧阈值。我们通过为某些$ n =ω（\，d^2/\ mathrm {polylog}（d）\，）$构建拟合椭圆形来解决这个猜想，从而改善了Ghosh等人的先前工作。 [Proc。关于计算机科学基础的研讨会，第954-965、2020页]，需要$ n = o（d^{3/2}）$。我们的证明证明了Saunderson等人的最小二乘结构的可行性。使用特定非标准随机矩阵的方便分解，并通过图矩阵理论对其Neumann扩展进行仔细分析。
Given independent standard Gaussian points $v_1, \ldots, v_n$ in dimension $d$, for what values of $(n, d)$ does there exist with high probability an origin-symmetric ellipsoid that simultaneously passes through all of the points? This basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. Based on strong numerical evidence, Saunderson, Parrilo, and Willsky [Proc. of Conference on Decision and Control, pp. 6031-6036, 2013] conjecture that the ellipsoid fitting problem transitions from feasible to infeasible as the number of points $n$ increases, with a sharp threshold at $n \sim d^2/4$. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Ω( \, d^2/\mathrm{polylog}(d) \,)$, improving prior work of Ghosh et al. [Proc. of Symposium on Foundations of Computer Science, pp. 954-965, 2020] that requires $n = o(d^{3/2})$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix and a careful analysis of its Neumann expansion via the theory of graph matrices.
