Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms

We study the problem of residual error estimation for matrix and vector norms using a linear sketch. Such estimates can be used, for example, to quickly assess how useful a more expensive low-rank approximation computation will be. The matrix case concerns the Frobenius norm and the task is to approximate the k-residual \|A - Aₖ\|F of the input matrix A within a (1+ε)-factor, where Aₖ is the optimal rank-k approximation. We provide a tight bound of Θ(k²/ε⁴) on the size of bilinear sketches, which have the form of a matrix product $SAT$. This improves the previous O(k²/ε⁶) upper bound in (Andoni et al. SODA 2013) and gives the first non-trivial lower bound, to the best of our knowledge. In our algorithm, our sketching matrices S and T can both be sparse matrices, allowing for a very fast update time. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. For the vector case, we consider the ₚ-norm for $p>2$, where the task is to approximate the k-residual \|x - xₖ\|ₚ up to a constant factor, where xₖ is the optimal k-sparse approximation to x. Such vector norms are frequently studied in the data stream literature and are useful for finding frequent items or so-called heavy hitters. We establish an upper bound of O(k2/pn1-2/ppoly(log n)) for constant ε on the dimension of a linear sketch for this problem. Our algorithm can be extended to the ₚ sparse recovery problem with the same sketching dimension, which seems to be the first such bound for $p > 2$. We also show an Ω(k2/pn1-2/p) lower bound for the sparse recovery problem, which is tight up to a poly(log n) factor.