论文标题
通过随机一量测试阳性半定义性
Testing Positive Semi-Definiteness via Random Submatrices
论文作者
论文摘要
我们研究测试是否具有有界条目的矩阵$ \ mathbf {a} \ in \ mathbb {r}^{n \ times n} $（$ \ | \ | \ | \ | \ | \ | \ mathbf {a} \ | _ \ | _ \ | _ \ | _ \ fly \ leq 1 $）这意味着$ \ min _ {\ MathBf {b} \ succeq 0} \ | \ | \ | \ Mathbf {a} - \ Mathbf {b} \ | _f^2>εn^2 $，$ \ Mathbf {b} \ succeq 0 $ demotes $ demotes $ demotes $ demotes $ \ thit $ \ m m iassbf is pst $ pst $ pst us} $。我们的主要算法贡献是一种非自动测试仪，它仅使用$ \ tilde {o}（1/ε^4）$查询$ \ mathbf {a a} $的条目。如果我们考虑了光谱规范中的距离，则获得了“ $ \ ell_ \ infty $ -gap问题”，其中$ \ mathbf {a} $是psd或满足$ \ min _ {\ mathbf {\ mathbf {b} εn$。对于此相关问题，我们给出了一个$ \ tilde {o}（1/ε^2）$ QUERY TESTER，我们显示的是最佳的$ \ log（1/ε）$。我们的测试人员随机对主要子膜片进行采样，并检查这些子膜是否为PSD。因此，我们的算法达到了单方面的错误：每当他们输出$ \ mathbf {a} $不是psd时，他们会返回$ \ mathbf {a} $的证书。 我们通过给出$ \tildeΩ（1/ε^2）$下限的上限与欧几里得规范距离进行补充PSD测试。我们的下限结构是一般的，可用于为许多光谱测试问题得出下限。作为我们建筑的适用性的一个例子，我们获得了一个新的$ \tildeΩ（1/ε^4）$采样下限，用于测试Schatten- $ 1 $ NORM，并使用$εn^{1.5} $差距，扩展了Balcan，Li，Woodruff和Zhang [Soda'19]的结果。此外，它可以产生新的采样界限，以估计ky-fan规范，以及最佳排名$ k $ $近似的成本。
We study the problem of testing whether a matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$ with bounded entries ($\|\mathbf{A}\|_\infty \leq 1$) is positive semi-definite (PSD), or $ε$-far in Euclidean distance from the PSD cone, meaning that $\min_{\mathbf{B} \succeq 0} \|\mathbf{A} - \mathbf{B}\|_F^2 > εn^2$, where $\mathbf{B} \succeq 0$ denotes that $\mathbf{B}$ is PSD. Our main algorithmic contribution is a non-adaptive tester which distinguishes between these cases using only $\tilde{O}(1/ε^4)$ queries to the entries of $\mathbf{A}$. If instead of the Euclidean norm we considered the distance in spectral norm, we obtain the "$\ell_\infty$-gap problem", where $\mathbf{A}$ is either PSD or satisfies $\min_{\mathbf{B}\succeq 0} \|\mathbf{A}- \mathbf{B}\|_2 > εn$. For this related problem, we give a $\tilde{O}(1/ε^2)$ query tester, which we show is optimal up to $\log(1/ε)$ factors. Our testers randomly sample a collection of principal submatrices and check whether these submatrices are PSD. Consequentially, our algorithms achieve one-sided error: whenever they output that $\mathbf{A}$ is not PSD, they return a certificate that $\mathbf{A}$ has negative eigenvalues. We complement our upper bound for PSD testing with Euclidean norm distance by giving a $\tildeΩ(1/ε^2)$ lower bound for any non-adaptive algorithm. Our lower bound construction is general, and can be used to derive lower bounds for a number of spectral testing problems. As an example of the applicability of our construction, we obtain a new $\tildeΩ(1/ε^4)$ sampling lower bound for testing the Schatten-$1$ norm with a $εn^{1.5}$ gap, extending a result of Balcan, Li, Woodruff, and Zhang [SODA'19]. In addition, it yields new sampling lower bounds for estimating the Ky-Fan Norm, and the cost of the best rank-$k$ approximation.
