Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms

We thank the reviewer for their thoughtful and detailed comments. We have uploaded a new version of our submission, where we added OSNAP in Lemma 3.5 and replaced the CountSketch matrix with OSNAP in our experiments section.

• The proof of Lemma 3.2: We thank the reviewer for pointing this out. We have added more details to the proof of this lemma. Please check our new version of the submission. At a high level, here we have that $d_{TV}(X,Y)$ is small and wish to prove that $d_{TV}(X+Z,Y+Z)$ is small, where $Z$ is independent of $X$ but not of $Y$. In fact, we can show that $d_{TV}(X+Z,Y+Z) = d_{TV}(X,Y)$ is small when conditioned on a fixed $Z$ (the distribution of $Y$ depends on the choice of $Z$) over an overwhelming number of choices of $Z$. This is enough to conclude that the unconditioned value $d_{TV}(X+Z,Y+Z)$ is small.

• The experiments: the reason we use a plain CountSketch matrix is that we found it has good performance for the two real-world datasets. We agree with the reviewer's point that OSNAP has a better worst-case guarantee. Hence, we have replaced CountSketch with ONSAP in our new version of the experiments. (Note that the new experiments are conducted on a different device, so the runtime is incomparable with that of the previous version.) 

• On use cases: there are natural settings in which we do not necessarily need to compute a low-rank approximation of all of the input matrices $A_1, A_2, \cdots, A_m$. Instead, we only need to compute an $\alpha$-fraction of them, based on which of them has a good low-rank approximation. In the case when $\alpha$ is small (such as $0.1$) and computing an actual low-rank approximation is much more expensive than estimating its cost, our algorithm will achieve a factor of roughly $\alpha$ savings in its resource requirements. In the streaming model, the space we need for our algorithm is $\mathrm{poly}(k)$, while if we want to compute a rank-$k$ approximation in a stream, the space we need would be $\Omega((n + m) \cdot k)$, which is larger than $\mathrm{poly}(k)$ when $k \ll m, n$. Also, the overall runtime of our algorithm for our rank-$k$ residual estimation algorithm is $O(\mathrm{nnz}(A) + \mathrm{poly}(k))$, while for a rank-$k$ approximation, the overall runtime is $O(\mathrm{nnz}(A) + (n + m) \cdot \mathrm{poly}(k))$. Hence, if the matrix $A$ is sparse enough, the second term of $\mathrm{poly}(k)$ will save a factor of $n$ from the latter complexity of $(n + m) \cdot \mathrm{poly}(k)$. For the $\ell_p$ sparse recovery problem, when $p \ge 2$, our algorithm is able to find heavy hitters that are even ``less heavy" than those for $\ell_2$, e.g., imagine a single coordinate $i^*$ has value $n^{1/3}$ while all other coordinates have value $1$. Then $i^*$ must be found by an $\ell_3$ sparse recovery algorithm, but not by an $\ell_2$ sparse recovery algorithm.

“But noting that heavy hitters can detect lighter heavy hitters, by itself, does not provide justification that the residual estimation problem is of interest to machine learning. Is super-constant space cost of $n^{1-2/p}$ acceptable in practice? "

Note that our algorithm indeed also outputs a vector $\hat{x}$ which satisfies the requirements for the $\ell_p$ sparse recovery problem, which was unknown for $p > 2$. We also provide a matching lower bound for the $\ell_p$ recovery problem. As mentioned, our algorithm for $\ell_p$ is able to find heavy hitters that are even ``less heavy" than those for $\ell_2$, which is beneficial to, e.g., the standard Gaussian white noise model in practice for which the underlying vector is a sparse vector plus Gaussian noise (see. e.g., [WHXF11]), where now we can handle a smaller variance on the Gaussians. The ability to detect the existence of a large signal in compressed sensing is also useful, as we can decide to use more measurements only if we notice the existence of such a signal; otherwise we can use fewer. This would make the sensing adaptive, but this is also a common model in compressed sensing (see, e.g., [IPW12, MN13]).

[CW13]: Kenneth L. Clarkson, David P. Woodruff. Low Rank Approximation and Regression in Input Sparsity Time.

[Agg16]: Charu C. Aggarwal. Recommender Systems: The Textbook.

[CGL+19] Yiming Sun et al. Low-Rank Tucker Approximation of a Tensor from Streaming Data.

[WHXF11]: Ning Wan-zheng et al. The Analysis of Noise Reduction Performance in Compressed Sensing.

[IPW12]: Piotr Indyk, Eric Price, David P. Woodruff. On the Power of Adaptivity in Sparse Recovery

[MN13]: Matthew L. Malloy, Robert D. Nowak .Near-Optimal Adaptive Compressed Sensing.

We thank the reviewer for their thoughtful comments. We can provide additional experiments in the next version of our paper.

We thank the reviewer for their thoughtful and detailed comments. We have fixed the typos mentioned and uploaded a new version of the paper. We agree that there is still a bit of a gap between the bounds for the sparse recovery and residual norm estimation problems we study in this paper, and we treat this as an interesting future direction.

• Question 1: Note that the size of $SAT$ is different from that of $A_k$, so they are not comparable as matrices. We have shown though in Theorem 3.7 that the residual error of $SAT$ is a good approximation to the residual error of using $A_k$ for $A$. Note though that $SAT$ is a much smaller sketch of $A$ and so gives a low memory way of approximating the residual that one could have found by using $A_k$. Also, in the low-rank approximation problem, using matrices $SA, AR, SAT$, we can more efficiently (than computing $A_k$ directly) compute two matrices $U$ and $V$ such that $||A - UV||_F^2 \le (1 + \epsilon)||A - A_k||_F^2 \;.$ (See the survey [1] for more details.)

• Question 2: We thank the reviewer for pointing this out. In fact, one can show that $\vert x_i\vert ^p \leq 2 \Vert x_{-k}\Vert_p^p$ for all $x_i \in I \setminus J$. Defining a new magnitude level for coordinates between $\Vert x_{-k} \Vert_p^p$ and $2\Vert x_{-k} \Vert_p^p$ is enough and the remainder of the proof is almost the same. The updated proof has been included in the new version which we have uploaded.

[1] David P. Woodruff. Sketching as a Tool for Numerical Linear Algebra.

We thank the reviewer for their thoughtful comments.

• On our improvement over Andoni and Nguyen: we improve the upper bound of Andoni and Nguyen from $O(k^2/\epsilon^6)$ to $O(k^2/\epsilon^4)$. Note that the $O(k^2/\epsilon^6)$ bound in their work was also only shown to hold for Gaussian matrices. In our work, we give a very different analysis than that in Andoni and Nguyen, and instead directly show that any sketching matrix with the so-called projection cost-preserving (PCP) property suffices, which allows us to directly use extremely sparse sketching matrices with a much faster running time, and also allows us to improve the bound to $O(k^2/\epsilon^4)$ using advances in PCPs. We also show an $\Omega(k^2/\epsilon^4)$ lower bound, which shows that our upper bound is optimal up to a constant factor.

• For the $\ell_p$ sparse recovery problem, when $p \ge 2$, our algorithm is able to find heavy hitters that are even ``less heavy" than those for $\ell_2$, e.g., imagine a single coordinate $i^*$ has value $n^{1/3}$ while all other coordinates have value $1$. Then $i^*$ must be found by an $\ell_3$ sparse recovery algorithm, but not by an $\ell_2$ sparse recovery algorithm.