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 - Ak|F of the input matrix A within a (1+ε)-factor, where Ak is the optimal rank-k approximation. We provide a tight bound of Theta(k2/ε4) on the size of bilinear sketches, which have the form of a matrix product SAT. This improves the previous O(k2/ε6) 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 ℓp-norm for p>2, where the task is to approximate the k-residual |x - xk|p up to a constant factor, where xk 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/poperatornamepoly(log n)) for constant ε on the dimension of a linear sketch for this problem. Our algorithm can be extended to the ℓp sparse recovery problem with the same sketching dimension, which seems to be the first such bound for p > 2. We also show an Omega(k2/pn1-2/p) lower bound for the sparse recovery problem, which is tight up to a poly(log n) factor.