论文标题
矩阵规范稀疏的比较
Comparison of Matrix Norm Sparsification
论文作者
论文摘要
在高效算法设计中的一种众所周知的方法，称为矩阵稀疏，近似于矩阵$ a $，带有稀疏矩阵$ a'$。 ACHLIOPTAS和MCSHERRY [2007]在频谱 - 标准稀疏方面发起了一系列工作，旨在确保$ \ | a'-a \ | \ | \ leqleqε\ | a \ | $ for Orror参数参数$ε> 0 $。根据Schatten $ p $ norm的保证，各种形式的矩阵近似动机，将一般$ p $的保证提供，其中包括光谱规范，作为特殊情况$ p = \ infty $。 我们研究了固定但不同的$ p \ neq Q $之间的关系，也就是说，在schatten $ q \ q \ q \ text {-norm} $中，schatten $ p $ -norm中的稀疏性是否暗示（存在和/或算法）稀疏。肯定的答案可能非常有用，因为它将确定要关注的$ p $的价值。我们的主要发现是这个问题与$ \ ell_p $ -norm对矢量的类似情况之间的对比：矢量稀疏：对于矢量，答案对于$ p <q $，对于$ p> q $是肯定的，但是对于矩阵而言，我们几乎对所有足够不同的$ p \ neq q $ neck nater News nater Ansess。此外，我们的明确结构可能具有独立的利益。
A well-known approach in the design of efficient algorithms, called matrix sparsification, approximates a matrix $A$ with a sparse matrix $A'$. Achlioptas and McSherry [2007] initiated a long line of work on spectral-norm sparsification, which aims to guarantee that $\|A'-A\|\leq ε\|A\|$ for error parameter $ε>0$. Various forms of matrix approximation motivate considering this problem with a guarantee according to the Schatten $p$-norm for general $p$, which includes the spectral norm as the special case $p=\infty$. We investigate the relation between fixed but different $p\neq q$, that is, whether sparsification in the Schatten $p$-norm implies (existentially and/or algorithmically) sparsification in the Schatten $q\text{-norm}$ with similar sparsity. An affirmative answer could be tremendously useful, as it will identify which value of $p$ to focus on. Our main finding is a surprising contrast between this question and the analogous case of $\ell_p$-norm sparsification for vectors: For vectors, the answer is affirmative for $p<q$ and negative for $p>q$, but for matrices we answer negatively for almost all sufficiently distinct $p\neq q$. In addition, our explicit constructions may be of independent interest.
