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 (k^2/pn^1-2/ppoly (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 (k^2/pn^1-2/p) lower bound for the sparse recovery problem, which is tight up to a poly (n) factor.