Linear Size Sparsifier and the Geometry of the Operator Norm Ball
Linear Size Sparsifier and the Geometry of the Operator Norm Ball
复制标题
线性尺寸稀疏器和算子规范球的几何形状
DOI：
10.1137/1.9781611975994.143
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Rothvoss, Thomas
中科院分区：
文献类型：
--
作者：
Reis, Victor;Rothvoss, Thomas
矩阵斯宾塞猜想问的是给定的特征值为1的对称矩阵是否总能找到符号，使得它们的有符号和具有奇异值。差异的标准方法要求证明所有好的分数符号的凸体都足够大。然而，由于缺乏工具来证明相当小的非多面体凸集的度量下界，这个问题仍然是广泛开放的。Batson， Spielman和Srivastava在2008年的一个开创性的结果表明，任何无向图都承认线性大小的谱稀疏器。同样，我们可以定义所有好的分数符号的凸体。我们确实可以证明这个物体接近高斯测度的大部分。这意味着第二作者的差异算法可以用来对线性大小的稀疏器进行采样。与以前的方法相比，我们只需要对数级的采样相位。
The Matrix Spencer Conjecture asks whether givensymmetric matrices inwith eigenvalues inone can always find signs so that their signed sum has singular values bounded by. The standard approach in discrepancy requires proving that the convex body of all good fractional signings is large enough. However, this question has remained wide open due to the lack of tools to certify measure lower bounds for rather small non-polyhedral convex sets. A seminal result by Batson, Spielman and Srivastava from 2008 shows that any undirected graph admits a linear size spectral sparsifier. Again, one can define a convex body of all good fractional signings. We can indeed prove that this body is close to most of the Gaussian measure. This implies that a discrepancy algorithm by the second author can be used to sample a linear size sparsifer. In contrast to previous methods, we require only a logarithmic number of sampling phases.
登录
查看更多内容
DOI：
10.1137/141000282
发表时间：
2014
期刊：
2014 IEEE 55th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
T. Rothvoss
通讯作者：
T. Rothvoss
影响因子：
1.6
作者：
Lovett, Shachar;Meka, Raghu
通讯作者：
Meka, Raghu
影响因子：
1
作者：
Ronen Eldan;Mohit Singh
通讯作者：
Mohit Singh
高维现象：L₁ 的膨胀、张量积和几何
DOI：
--
发表时间：
2015
期刊：
影响因子：
--
作者：
T. Tkocz
通讯作者：
T. Tkocz
关于一些向量平衡问题
影响因子：
0.8
作者：
A. Giannopoulos
通讯作者：
A. Giannopoulos