RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees

We thank the referee for the positive feedback and constructive comments.
We first address the concerns raised, and then respond to the specific questions.

Weaknesses

Definition of failure:

To avoid repetitions in the captions of all figures we defined failure in Line 60 of the manuscript. As this seems to have been missed, in the revision, we will add this to the caption of the figure as well.

Remark 2.1:

We agree with the referee that Remark 2.1 should be made clearer and we will do so in the revision. Yes, the small increase in runtime is far outweighted by the improved convergence.

Intuition to Equation (2):

Thanks for the suggestion. We will add an intuitive explanation for why Eq. (2) is an effective approach to detect outliers, and does not miss signal directions.

Questions

Q1:[Remark after equation 2]

We will add such a remark in the revision.

Q2+Q3: [Parameter selection]

Our practical algorithm is parameter free and so these are not practical issues. A way to select the number of corrupted entries is discussed in Section 2.1 of the manuscript. The parameter $\mu$ can also be estimated [1].

[1] R. Sun and Z.-Q. Luo, Guaranteed matrix completion via non-convex factorization, IEEE Trans. Inform. Theory, 62 (2016)

We thank the referee for the constructive feedback and valuable suggestions. We first address the concerns raised, followed by responses to the specific questions.

Weaknesses

No Significant novelty in the work:

We respectfully disagree with the refeee's assessment that our manuscript has no significant novelty. On the methodological side, we agree that the proposed method $`RGNMR`$, can be viewed as a relatively simple combination of outlier removal with the existing scheme $`GNMR`$. However, our manuscript contains at least two significant results: (i) a non-trivial method to estimate the number of corrupted entries; and (ii) a theoretical recovery guarantee, which improves the state of the art for factorization based methods. Deriving these recovery guarantees for $`RGNMR`$, does not directly follow from the existing guarantees for $`GNMR`$, which hold only without outliers. Furthermore, the recovery guarantees we were able to derive for $`RGNMR`$ improve upon those of other RMC factorization based methods in terms of the fraction of corrupted entries. We view this as a significant theoretical contribution.

Comparison to $`GNMR`$:

$`GNMR`$ is a non robust method. Like many vanilla matrix completion methods it may fail completely in the presence of even a small fraction of corrupted entries. We will illustrate this in the revision.

Overparameterization:

The referee is correct that overparameterization is an important issue when employing factorization based methods.
For this reason we discuss overparameterization in several places in the manuscript, see for example Figurew 2 as well as Lines 50-67 "Limitations of existing RMC methods". Specifically, Fig.2 illustrates the performance of $`RGNMR`$ under overparameterization and show that it is in fact the only method, out of those tested, that succeeds in this case.

Initialization:

Indeed, the proposed initialization procedure yields a highly inaccurate initial guess when the data is highly corrupted. However, this does not pose a major problem for $`RGNMR`$, as empirically $`RGNMR`$ succeeds even from a random initialization.

Additional notes:

The square is not crucial but we will add it for clarity, thank you for noting that.

Questions:

Q1: [Rank estimation]

First, we note that in various applications in computer vision, the rank of the underlying matrix is known [1]. That said, the referee is correct that in many applications the rank of the underlying matrix is unknown. This does not pose a significant challenge for our approach, since as illustrated in Figure 2, $`RGNMR`$ continues to work well even under overparametrization. For example, for an underlying matrix of rank $r=5$, $`RGNMR`$ succeeds if its input rank is $r=10$. In short, our method only needs a reasonably tight upper bound on the rank. Another option is to simply run our algorithm with several input ranks. We will discuss this in the revision.

[1] Okatani, Takayuki, Takahiro Yoshida, and Koichiro Deguchi. "Efficient algorithm for low-rank matrix factorization with missing components and performance comparison of latest algorithms." 2011 International Conference on Computer Vision. IEEE, 2011.

Q2:[$`RGNMR`$ VS $`RGNMR-BS`$]

There are indeed settings where accurately estimating $k^*$ is difficult. In such cases, $`RGNMR-BS`$ may fail to recover the matrix, whereas $`RGNMR`$ (given the exact number of outliers) may still succeed. This occurs, for example, when the fraction of corrupted entries is quite large, as illustrated in Fig.5 in the Appendix. The difference in runtime between $`RGNMR`$ and $`RGNMR`$-BS is illustrated in Fig.10 in the Appendix.

Q3: [$`GNMR`$ VS $`RGNMR`$]

We will include such simulations in the revised version.

Q4: [$`GNMR`$ variants]

In $`RGNMR`$ we employ an optimization step similar to that of the setting variant of $`GNMR`$. This variant worked best. We will mention this in the revision.

We thank the referee for their constructive feedback and suggestions. We first answer their three questions and then reply to other issues raised.

Q1 : [Connections between Alg.1 and Alg. 2]: In both Alg. 1 and Alg. 2 the estimation procedure of the corrupted entries is based on the magnitude of the residual entries. The method employed in Alg. 2 is based on the assumptions made on the corrupted entries, which facilitate deriving theoretical guarantees. Specifically, under Assumption 3, the fraction of corrupted entries in each row and column is bounded. Hence, it makes sense to remove only a bounded number of entries from each row and column. Accordingly, Alg.2 removes the largest $\gamma \alpha$ residual entries in each row and column. However, without any assumptions on the corruption pattern, a more general approach is to remove the largest residual entries across the entire matrix, as employed in Alg.1. We will clarify this in the revision.

Q2 : [Alg.2 in practice] This is a great question. As mentioned above it make sense to use the scheme of Algorith 2 to detect the outlier entries only under Assumption 3. Following the referee's question we tested the performance of RGNMR combined with the scheme of Alg. 2. Though this method is far less successful than our proposed one it still works decently. Specifically, it successfully recovers a $500\times 500$ matrix of rank $5$ and a condition number of $10$, with an oversampling ratio of $12$ and 1% fraction of corrupted entries. This makes it competitive with other RMC methods, which fail to recover such ill-conditioned matrices. We will discuss this in the revision.

Q3: [ Properties of $`RGNMR`$] The fact that $`RGNMR`$ performs well on ill-conditioned matrices, with a small number of observed entries and under overparameterization should be attributed to the optimization step, which updates $U$ and $V$ simultaneously and globally. Other optimization schemes, such as gradient based schemes, have been shown to perform poorly under these conditions even when no entries are corrupted. However, we would like to clarify that $`GNMR`$, as well as many other low-rank matrix completion methods, is not robust to the presence of outliers. It may fail miserably even in the presence of very few corrupted entries. Therefore, the estimation procedure of the corrupted entries is crucial for the method success. We will clarify this in the revision, and also add a figure showing the failure of GNMR in the presence of outliers.

Other issues:

• Novelty/Estimating number of outliers: We agree that our scheme to estimate the number of outlier entries is an important and novel component of $`RGNMR`$. However, accurately estimating the number of outliers is not sufficient. Specifically, as mentioned in P9 L297-301 of our manuscript, and illustrated in the simulations, even though we provided $`AOP`$ and $`RPCA-GD`$ with the exact number of corrupted entries, they still perform poorly in comparison to $`RGNMR`$ and $`RGNMR-BS`$. We will clarify this in the revision.

We thank the referee for their constructive feedback and suggestions. We first address the weaknesses raised, and then answer the referee's questions.

Weaknesses:

Motivation:

We agree with the referee that in recommender systems, matrix completion methods are not state of the art. We will mention this in the revision. Despite having been considered for more than 20 years, matrix completion and its robust variant are still important problems in data science. Beyond classical applications in computer vision, they are still applicable and used in several contemporary fields, including single-cell analysis in biology [1] and sensor networks [2], for example. In addition, as noted by numerous recent citations in the manuscript, robust matrix completion is an active field of research in statistics and machine learning. We will include a clearer motivation for low rank matrix completion in the revision.

[1] Lejun et al, SeqBMC: Single‐cell data processing using iterative block matrix completion algorithm based on matrix factorization, IET Systems Biology, 2025.

[2] Wu, Di, et al. "Robust low-rank latent feature analysis for spatiotemporal signal recovery." IEEE Transactions on Neural Networks and Learning Systems (2023).

Novelty:

We agree with the referee that the proposed method $`R$\texttt{GNMR$}$, can be viewed as a relatively simple combination of outlier removal with the existing scheme $GNMR`$. Two major novelties are: (i) a non-trivial method to estimate the number of corrupted entries; and (ii) a theoretical recovery guarantee, which improves the state of the art for factorization based methods. We will clarify these points in the revision.

Practicality of the experimental settings:

In the main text, indeed results were presented for matrices of size $3200\times 400$. However, please note that in Fig. 10 in supplementary of our original submission, we applied $`RGNMR`$ to matrices of size up to $16,000 \times 16,000$. Namely, $`RGNMR`$ can be successfully applied to much larger matrices. In the revised version, we will add simulations comparing $`RGNMR`$ to other methods for such large matrices.

Additive Noise:

Fig. 7 compares the reconstruction error of various algorithms in the presence of both outliers and small additive noise. However, the setting here was chosen so that other methods will succeed, specifically a small condition number $\kappa=2$, a high oversampling ratio $\frac{|\Omega|}{r\cdot(n_1+n_2-r)} = 12$, a small fraction of outliers $\alpha = 5\%$ and all methods were given the correct rank. Changing one of these parameters, for example increasing the condition number to 10, causes most other methods to have an $O(1)$ error, at any noise level. In contrast, $`RGNMR`$ and $`RGNMR-BS`$ maintain an error proportional to the standard deviation of the noise. Therefore, $`RGNMR`$ is a competitive method even in the presence of additive noise. We will add figures to illustrate this in the revised version.

Runtime and/or algorithmic complexity:

Thanks for raising this important issue. Some matrix completion methods, such as those based on gradient descent are very fast. In comparison to such methods, $`RGNMR`$ is indeed more computationally demanding. Please note that in Figure 10, we did study the runtime of our method as a function of matrix size. As mentioned in the main text P9, L309, the compleixity of $`RGNMR`$ emprically scales as $O(n^2)$. Moreover, as illustrated in Fig.10 its runtime on a standard PC remains reasonable even for large matrices (several minutes for a $16k\times 16k$ sized matrix). Improving $`RGNMR`$ runtime is an interesting problem for future research. We will add a discussion of these issues in the revised version.

Missing connections to other literature:

We thank the referee for pointing this out and we will discuss it in revision.

Missing essential results from the main text:

In revision, with an additional allowed page, we will make the manuscript more self contained, in particular moving some of the figures from supplementary to the main text.

Questions

Q1:[Additive noise]

Indeed, Figures 1 to 3 correspond to simulations with outliers but otherwise no additive noise. In the revision, we will clarify this issue and add figures with a small amount of additive noise (beyond the outliers).

Q2: [non-uniform sampling pattern of observed entries]

Thanks for raising this interesting issue. Following the referee's question, we ran $`RGNMR`$ and several other methods mentioned in our paper, in a setting where the observed entries are concentrated in a diagonal-band pattern as in [1]. In this setting, all tested methods require a higher number of observed entries to succeed. Yet, $`RGNMR`$ still significantly outperformed the tested competing methods even in this case. In the revision, We will add a comparison between the different methods under this non-uniform sampling pattern.

[1] Okatani, Takayuki, Takahiro Yoshida, and Koichiro Deguchi. "Efficient algorithm for low-rank matrix factorization with missing components and performance comparison of latest algorithms." 2011 International Conference on Computer Vision. IEEE, 2011.

Q3: [graduated non-convexity approaches]

One of our initial attempts to solve robust low rank matrix completion was to develop a method that iteratively reweighted the effect of potential outliers. Specifically, we replaced the least squares objective to update the factor matrices by an IRLS scheme. Since this requires employing an IRLS algorithm for every update of $U$ and $V$ it is very computationally demanding. In addition, the performance of this approach was not promising. Hence, we developed the method presented in our manuscript, that detects outliers and removes them completely.

Q4: [Initialization]

To randomly initialize $U_0$ and $V_0$ we generated two random matrices $Z_1\in\mathbb{R}^{n_1\times r}, Z_2\in \mathbb{R}^{n_2\times r}$ with i.i.d. entries distributed as $N(0,1)$. We then set $(U_0, V_0) = (\tilde{U_1},\tilde{U_2})$ where $\tilde{U_i}\tilde{\Sigma_i}\tilde{V_i}$ is the SVD of $Z_i$. We set $\Lambda_0$ as the $k$ largest residual entries in $U_0 V_0^\top - X$. We will add these details in the revision.