- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies matrix multiplication when input matrices contain missing entries. It proposes M³ to estimate the product directly without reconstructing complete inputs. The method handles four observation patterns separately. It keeps terms where both entries are observed. When one or both entries are missing, it uses Gaussian conditional product expectations.
For each output entry, the method treats the paired row and column coordinates as i.i.d. samples from a bivariate Gaussian distribution. Means and variances are estimated from all available observations. Covariance is estimated jointly from jointly observed pairs, then shrunk and clipped for stability. The method has the same leading arithmetic complexity as conventional dense matrix multiplication. The theory establishes minimum squared error for an oracle using the same local observations. With known Gaussian moments, it also quantifies the benefit of accounting for covariance.
Experiments compare M³ with imputation methods and task-specific estimators. Synthetic experiments cover five distributions and four missing rates, with additional scaling tests. M³ achieves the lowest mean product error in 18 of 20 synthetic settings. Real-data tests examine Gram matrix recovery, the leading PCA eigenvalues, and the leading PLS singular values. A recommendation experiment uses the estimated item–item products for ranking. On Jester, M³ achieves the best Recall@10 and MAP@10, while remaining competitive on NDCG@10.
Critical strengths
S1: The method is interpretable. It estimates the product directly and avoids reconstructing complete inputs.
S2: The reported experiments show a useful balance between accuracy and runtime across several tasks. My partial reproduction of the synthetic setup showed similar trends.
Critical weaknesses
W1: The method relies on correlations estimated from overlapping observations. When the true correlations are weak, estimation noise can make it worse than mean imputation. The main guarantees assume known moments. The paper does not show how well its shrinkage controls this risk in finite samples.
W2: The direct-product and PLS experiments compare only with imputation methods. A simple product baseline using the same estimated moments and shrinkage is missing. This makes it hard to tell how much the proposed product rule adds.
Questions for authors
Q1: The contribution appears to be the combination of existing statistical tools under an i.i.d. Gaussian model. What does this combination add beyond a simple product estimate using the same estimated moments and shrinkage?
Q2: When does the practical estimator improve on mean imputation in finite samples? Can the analysis account for estimation error, especially with limited overlap or weak dependence?
2 comments
Thank you for the detailed response and additional experiments. I appreciate the authors' efforts to address my two main concerns.
Regarding W1 and Q2: The new experiments are helpful and confirm my concern about the practical estimator under weak dependence. In particular, when the dependence is zero or weak, M³ performs worse than mean imputation. I also appreciate the clarification that shrinkage does not guarantee finite-sample improvement.
However, while the proposed condition provides useful insight into the effect of covariance estimation error, it assumes known marginal moments, which must also be estimated in practice. Moreover, the condition depends on quantities that are generally unknown in practical applications. Therefore, it does not fully characterize the finite-sample behavior of the implemented estimator. It would be helpful to explicitly discuss this limitation and examine whether shrinkage can mitigate the failure cases under zero or weak dependence.
Regarding W2 and Q1: The ConstantMoment and NoShrink ablations are useful additions. The comparison with ConstantMoment demonstrates that the conditional-product rule provides benefits beyond simply estimating the moments. I consider this concern substantially addressed.
Overall Assessment: Overall, I believe the rebuttal has substantially addressed W2 and further clarified the limitations raised in W1. However, the additional experiments also reveal that M³ can perform substantially worse than mean imputation under weak dependence and high missingness. Since this practical robustness concern remains insufficiently resolved, I will maintain my original rating.
We appreciate the reviewer's thoughtful comments and suggestions. Below, we provide clarifications and additional experimental evidence to address the concerns raised:
W1 & Q2. [Weak dependence and finite-sample guarantees]. We now provide a precise condition: with known marginal moments, M3 improves over the zero-dependence estimator when $ E[H^2(\hat{\tau}-\tau)^2] < \tau^2 E[H^2]$, where τ is the true covariance between X and Y, τ^ is its estimate, and H is the covariance-dependent correction factor. Thus, the benefit of exploiting dependence must outweigh the covariance estimation error. Our shrinkage aims to reduce this error but does not guarantee improvement in finite samples. Additional experiments confirm this limitation: at zero dependence, M3 performs worse than mean imputation across all missing rates, with the gap increasing as missingness increases. Similar behavior is observed at dependence 0.05. However, as dependence strengthens, M3 benefits from exploiting the covariance structure and outperforms mean imputation at dependence levels of 0.2 and above across all tested missing rates (Table R4.1).
Table R4.1. Relative Frobenius error of M3 and mean imputation under varying dependence strengths. Experiments use synthetic Gaussian matrices with dependence levels of 0, 0.05, 0.2, 0.4, and 0.75, and MCAR missing rates of 20%, 30%, 50%, and 70%. Bold indicates the lowest mean error in each setting.
W2 & Q1. [Contribution beyond estimated moments]. We added two ablations: ConstantMoment, which uses the same estimated moments and covariance shrinkage as M3 but applies a constant covariance correction instead of conditioning on observed values; and NoShrink, which follows M³ without covariance shrinkage. The results are reported in Table R4.2.
The theoretical difference is also clear: when only X is observed and the Gaussian moments are known, the conditional-product rule reduces MSE over the constant-covariance rule by τ2(2+μX2/vX). This shows that M3 contributes beyond moment estimation by using the observed values to estimate each missing product more accurately. However, this theoretical gain does not guarantee improvement when moments are estimated.
Table R4.2. Ablation study of M3 under different data distributions and missing rates. Relative Frobenius error is reported for M³, ConstantMoment (ConstMom), and M3 without covariance shrinkage (NoShrink) across five synthetic distributions and MCAR missing rates of 20%, 30%, 50%, and 70%.