Fast exact recovery of noisy matrix from few entries: the infinity norm approach

Thank you for the through and detailed comments and the evaluation of our paper. We would like to offer our responses to some of your concerns and questions.

1. Comments

1. Regarding the lack of experiments on real datasets: we thank you for pointing it out, and we agree that we should have included a couple. Other reviews also pointed out that our assumption of low rank still does not fully reflect real-life datasets, which are often only approximate low-rank. On the other hand, most breakthrough mathematical works like Candes-Tao's make use of the low rank assumption. Initially, we wanted to focus on the fact our result breaks the two theoretical barriers involving the condition number and large singular value gaps as the main highlight. We will certainly include experiments, paralleling those in other works in the final version. We are also working on an extension of this paper to cover the case when the ground matrix is approximately low rank.

2. Regarding the comparison with Abbe et al. (reference [9] in our paper): We felt that, at least in Section 3.3 of [9], the problems both of us were trying to solve are essentially the same, as we both aimed to provide an infinity norm estimate for the error of our respective recovery methods in terms of $n$, $p$ and other parameters from the underlying matrix $A$, which can then be turned to an estimate on the minimum sampling rate ($p$) needed to make this error within a chosen $\varepsilon$. We only need to look at the precision level of the entries of $A$ if we want to round off the output to achieve exact recovery (one can imagine that the output before rounding off has higher precision level, for example, 64-bit floating point numbers while $A$'s entries are half-integers). As the focus of [9] is a different problem, we appologize for making the comparison with respect to matrix completion. We can omit this comparison and will only have a comparison with Section 3.3, and with respect to the infinity norm bounds.

3. Regarding the inaccuracies on page 1: We thank you for pointing them out, and we will certainly fix them in the final version. We would also like to note that our result holds for a general $r$ that can go to infinity with $m$ and $n$.

4. Regarding the comment about page 3: We refer to our first paragraph, which admits the limit of our current scope to low-rank matrices.

2. Questions

1. Regarding page 4 line 127: We meant to explain that our result guarantees (with high probability) that the method of truncated SVD can now be applied to recover, down to every entry, matrices with large condition numbers, and matrices with some small singular value gaps, which were not guaranteed by previous methods. As mentioned above, we will include experiments with some datasets in the final version.

2. Regarding how to estimate $K_A$ and $K_Z$: We simply assume they will be given along with the dataset. For example, $K_A + K_Z \le 5$ in the Netflix problem. Datasets often come with descriptions about the range of values each cell can take.

3. Regarding page 5 line 160: We meant to explain that if we obtain a recovery within $\varepsilon$ in the infinity norm, meaning $||\hat{A} - A||\_\infty \le \varepsilon$, then this recovery is also within $\varepsilon$ in the root-mean-squared-error sense, namely $\frac{1}{\sqrt{mn}} ||\hat{A} - A||_F \le \varepsilon$, which is a fairly straightforward observation. We apologize for the confusion caused by our word choices, and will add a couple sentences to clarify this in the final version.

We thank you for your comments and the positive evaluation of our paper. We agree with your assessment of the shortcomings of the paper, and we would like to point out that we will try to tackle the case where the underlying matrix is only approximately low-rank in a future paper. We also agree with your suggestion of including experiments on real datasets. We will certainly include experiments, paralleling those in other works in the final version if you deem it necessary.

Regarding your questions, we would like to offer our responses below.

1. Thank you for bringing to our attention these results, as we were not initially aware of them. We have examined the results by Mao et al. and Fan et al. carefully, and we found that their scopes do not cover our use case. We would like to bound $|e_i^TE^kw|$ (this $E$ is $\mathbf{H}$ in Mao et al. and $\mathbf{W}$ in Fan et al.), for all $i\in [n]$ and all $k\le C\log n$ for some large enough constant $C$ like $100$. The probability for the bound to hold must be strong enough to beat the union bounds over all $i\in [n]$ and $k\le C\log n$. This means the probability should be at least $1 - o(n^{-1}\log^{-1}n)$. If we use Lemma 5.4 in Mao et al. for this purpose, we need to choose some $\xi > 1$, and let $t = C\log n$. The factor next to $||v||\_\infty$ in the bound then becomes $(\log n)^{c \log n}$, which grows too fast for our use (our Lemmas D.3 and D.4 has this factor capped at $\log^3 n$). Likewise, Lemmas 4 and 5 in Fan et al. seem to not be directly applicable, since they assume $k$ is a bounded integer. Moreover, in our use case, which is where $E$ has $0$ on its diagonal, we need to involve $||v||_\infty$ in the bound to make it efficient. If we can apply Lemma 4, then Lemma 5 here to arrive at a bound, it will just be $O(\alpha_n^k)$, or $O(n^{k/2})$. This is not much better than the trivial argument $|e_i^TE^kv| \le ||E||^k = O((2n)^{k/2})$ (for our use case only, as theirs also cover the case of non-zero diagonals). We admit that we had not have time to read and analyze their proofs, and it is possible that their techniques can be extended to cover our use case, or help us improve our result even more. We will continue to read their proofs and include a discussion about these results in the final version of the paper.

2. Thank you for pointing out the typo. Indeed we intended to use $\varsigma$ instead $\kappa$ there. Choosing the names of variables has been challenging for us since this paper uses so many, and we want to keep variable names close to their traditional names in literature if possible. The naming clash for the name $\sigma$ between the singular values and the variance of a random variables has been a particular issue. We will certainly fix it in the final version.

We thank you for your comments and the positive evaluation of our paper. We would like to address the following concerns and questions of your review:

1. Weaknesses of the paper:

1. We acknowledge that we did not set aside a separate section to summarize and clarify the advantages and possible disadvantages of our results versus the other works. In an early version of the paper, we had a comparison table, which was cut from the final draft after we restructured the paper and removed the discussions and comparisons with several other papers that we felt not as relevant as the ones we kept. We did this to comply with the page limit. If you prefer, we will try to bring it back, with appropriate adjustments, probably in Section 3.3.

2. Let us respond specifically to clarify your concern about the lack of direct comparisons with "Matrix Completion with Noise" by Candes and Plan (reference [8] in our paper) and "Exact Low-rank Matrix Completion via Convex Optimization" by Candes and Recht (reference [1]).

• The result of [1] is one of most influential works in Matrix Completion that deal with the pure (noiseless) problem. It was followed shortly by the papers of Candes and Tao (reference [2]) and Recht (reference [3]) that direct improved on it. Therefore, it suffices to compare our result with [3]. Ignoring the factors dependent on $\mu_0$ (the coherence) and $r$ (the rank of the original matrix), [3] has achieved near-optimal sampling rate, being off by a $\log(m + n)$ factor from the theoretical limit $(m + n)\log(m + n)$. Our result has a sampling rate off by $\log^9(m + n)$, but otherwise is optimal. Its main advatage is the ability to deal with random, independent noise, which is not addressed in [1, 2, 3]. Our algorithm is also simpler and faster in practice (it basically computes a low rank approximation of the input).

• The result (Theorem 7) in [8] is more general than ours in the sense thay it holds for any type of noise, whereas ours only apply to noises that are independent among entries and universally bounded by a known upper bound. We also need the extra assumption that $||A||$ is large enough (which we have argued is reasonable and perhaps necessary for exact recovery in Remark 2.4). However, their method only achieves recovery in the Frobenius norm, or RMSE, sense, while ours gives recovery in the infinity norm sense, which becomes exact after rounding off. Their method, being convex optimization, runs in time $O(|\Omega|^2(m + n)^2)$, which is at least $O((m + n)^4\log^2(m + n))$ for recovery to be theoretically possible (see the survey [15] in our paper). On the other hand, our method runs in time $O(r|\Omega| + mn)$, being simply a truncated SVD algorithm, making it much faster than [8]. Another point is the effectiveness of the methods. To achieve a RMSE error (which is $||\hat{A} - A||_F / \sqrt{mn}$) within some $\varepsilon$, the method in [8] needs $p \ge \epsilon^{-2} ||Z||_F^2 / (m + n)$, which is not possible even in the simple cases like $Z$ having independent entries in $\{-1, 0, 1\}$ with uniform distribution (setting $p = 1$, which means full observation, is still not enough if $\varepsilon = 0.1$). Our method achieves $||\hat{A} - A||\_\infty \le \varepsilon$, which is stronger, while only needing $m$ and $n$ to be large enough and $p \ge C(r, \mu_0)\max\{\log^4 (m + n), \varepsilon^{-2}\} \log^6(m + n)$, which is much lower and achievable for the aforementioned simple noise model.

3. We also want to offer a brief comparison with the works of Keshavan, Oh and Montanari (references [6] and [7]) that deal with both the noiseless and noisy cases. Our sampling rate is slightly higher than theirs, being off by a few $\log (m + n)$ factors, and we need the extra assumption that $||A||$ is large enough (see the previous item and Remark 2.4 in our paper). On the other hand, we remove the dependence on the condition number that they have, and our method achieves an infinity norm recovery while theirs stop at RMSE recovery.

2. Questions.

1. Although a condition number $\kappa \approx 10.45$ may be small, it can get very large if raised to high powers, making bounds inefficient. For example, the papers [6] and [9] that we discuss throughout Section 1 involve $\kappa^6$ and $\kappa^4$ in their sampling rate bounds. Our result avoids this growth factor by removing $\kappa$ completely.

2. A high-level explanation for our thresholding rule is as follow. We view the observed matrix, rescaled by $p^{-1}$, as a perturbed version of the original matrix, namely $p^{-1}A_{\Omega, Z} = \tilde{A} = A + E$, where $E$ is a random matrix of mean $0$ and independent entries. One can view $E$ as a type of "noise" that includes both the noise $Z$ and the noise caused by the random sampling. We simply want to cut off the singular values of $\tilde{A}$ at a level above $||E||$, as the BBP phenomenon shows that the part of $A$ below that is fully absorbed by $E$ and becomes indistinguishable from noise. Under the assumptions we make, the signal extracted from the spectrum of $\tilde{A}$ above this threshold is close enough to $A$ to allow us to recover it. We use the same argument in Remark 2.4 to show the necessity of the lower bound on $\sigma_1 = ||A||$.

3. Limitations:

1. Thank you for the suggestion of including experiments on real datasets. As pointed out by other reviews, our assumption of low rank still does not fully reflect real-life datasets, which are often only approximate low-rank, so initially we wanted to focus on the fact our result breaks the two theoretical barriers involving the condition number and large singular value gaps as the main highlight. We will certainly include experiments, paralleling those in other works in the final version if you deem it necessary. We are also working on an extension of this paper which would cover the case when the truth matrix is only approximately low rank.

2. We apologize for the potential confusion caused by the word "distortion level". We can revert it back to "discretization unit", for example.

3. We use the word "sparse" simply to point out that, in the worst case that our method can still guarantee recovery with high probability, we allow the sampling rate $p$ (the density of non-zero entries in the observed matrix $A_{\Omega, Z}$) to be very small, being at most $C(\mu_0, r) (m^{-1} + n^{-1}) \log^C(m + n)$. We acknowledge that $A_{\Omega, Z}$ can become dense if $p$ increases. This will increase the time our SVD step takes, but also makes it easier to recovery $A$. As mentioned above, the time complexity $O(r|\Omega| + mn) = O((pr + 1)mn)$ is still substantially better than nuclear norminimzation for any value of $p$.

We thank you for your comments and the positive evaluation of our paper. We agree with your assessment of the shortcomings of the paper, and we would like to point out that we will try to tackle the case where the underlying matrix is only approximately low-rank in a future paper. As a matter of fact, the contour method used in the paper of Tran and Vu (that we follow) applies for the approximately low rank case, when the matrix has few large leading eigenvalues and the rest are small. However, to prove perturbation bound in the infinity norm as in this paper, this method needs to be modified significantly. We are working on the details at this moment, but are pretty positve on the outcomes.