Comparison of Matrix Norm Sparsification
share
Matrix sparsification is a well-known approach in the design of efficient algorithms, where one 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≤ϵ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=∞. We investigate the relation between fixed but different p≠ q, that is, whether sparsification in Schatten p-norm implies (existentially and/or algorithmically) sparsification in Schatten q-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 ℓ_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 p≠ q.
READ FULL TEXT