acceptodds
Withdrawn from ICLR 2027

Beyond Imputation: Rethinking Matrix Multiplication under Missing Data

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Matrix multiplication is a fundamental operation behind machine learning, yet the usual operator becomes undefined when either operand contains missing entries. Existing solutions typically rely on task-specific adaptations or imputation-based pipelines, both of which can introduce additional complexity, computational costs, and task-specific development efforts. To address these limitations, we introduce Missing-aware Matrix Multiplication, denoted M, which estimates unavailable multiplicative contributions directly through conditional moments. Under a pair-local Gaussian working model, four observation patterns admit closed-form contributions, while marginal moments exploit all available observations and estimate dependence only from overlapping entries. We prove pair-local oracle optimality and show that exploiting cross-factor dependence strictly reduces mean-squared error relative to mean imputation. Across direct product recovery, Gram and PCA recovery, cross-view spectral estimation, and recommendation tasks, our method generally improves effectiveness while remaining computationally efficient. These findings suggest that M provides a promising and efficient approach to matrix multiplication in the presence of missing data.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
missing data, imputation, matrix multiplication

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_6Mu2OpenReview ↗
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

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, M3M^3 improves over the zero-dependence estimator when $ E[H^2(\hat{\tau}-\tau)^2] < \tau^2 E[H^2]$, where τ\tau is the true covariance between XX and YY, τ^\hat{\tau} is its estimate, and HH 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, M3M^3 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, M3M^3 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 M3M^3 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.

Missing RateDependenceMeanM³
20%00.113 ± 0.0200.130 ± 0.026
20%0.050.116 ± 0.0210.130 ± 0.026
20%0.20.141 ± 0.0260.126 ± 0.023
20%0.40.189 ± 0.0320.113 ± 0.017
20%0.750.255 ± 0.0330.086 ± 0.009
30%00.139 ± 0.0210.170 ± 0.033
30%0.050.144 ± 0.0220.171 ± 0.033
30%0.20.185 ± 0.0310.165 ± 0.029
30%0.40.260 ± 0.0440.148 ± 0.021
30%0.750.360 ± 0.0470.113 ± 0.010
50%00.187 ± 0.0320.271 ± 0.056
50%0.050.193 ± 0.0310.196 ± 0.055
50%0.20.258 ± 0.0430.250 ± 0.049
50%0.40.373 ± 0.0610.237 ± 0.037
50%0.750.524 ± 0.0670.190 ± 0.023
70%00.247 ± 0.0430.410 ± 0.090
70%0.050.252 ± 0.0410.408 ± 0.087
70%0.20.322 ± 0.0510.318 ± 0.078
70%0.40.455 ± 0.0720.374 ± 0.065
70%0.750.637 ± 0.0780.331 ± 0.047

W2 & Q1. [Contribution beyond estimated moments]. We added two ablations: ConstantMoment, which uses the same estimated moments and covariance shrinkage as M3M^3 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)\tau^2(2+\mu_X^2/v_X). This shows that M3M^3 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 M3M^3 under different data distributions and missing rates. Relative Frobenius error is reported for M³, ConstantMoment (ConstMom), and M3M^3 without covariance shrinkage (NoShrink) across five synthetic distributions and MCAR missing rates of 20%, 30%, 50%, and 70%.

DistributionMissingM³ConstMomNoShrink
Gaussian20%0.086 ± 0.0140.091 ± 0.0110.085 ± 0.010
30%0.116 ± 0.0110.118 ± 0.0140.117 ± 0.013
50%0.188 ± 0.0170.195 ± 0.0240.188 ± 0.022
70%0.346 ± 0.0470.366 ± 0.0480.355 ± 0.044
Student-t520%0.113 ± 0.0320.120 ± 0.0290.114 ± 0.027
30%0.150 ± 0.0380.157 ± 0.0370.151 ± 0.035
50%0.246 ± 0.0540.259 ± 0.0570.247 ± 0.057
70%0.373 ± 0.0740.376 ± 0.0740.424 ± 0.090
Mixture20%0.056 ± 0.0080.068 ± 0.0070.054 ± 0.005
30%0.078 ± 0.0070.088 ± 0.0090.082 ± 0.007
50%0.148 ± 0.0180.156 ± 0.0170.156 ± 0.010
70%0.293 ± 0.0300.299 ± 0.0360.295 ± 0.021
Skewed20%0.104 ± 0.0300.115 ± 0.0260.109 ± 0.019
30%0.138 ± 0.0300.148 ± 0.0300.139 ± 0.022
50%0.218 ± 0.0400.233 ± 0.0460.220 ± 0.039
70%0.385 ± 0.0690.393 ± 0.0660.391 ± 0.071
Laplace20%0.095 ± 0.0140.100 ± 0.0130.095 ± 0.012
30%0.127 ± 0.0180.132 ± 0.0190.129 ± 0.018
50%0.212 ± 0.0290.225 ± 0.0280.219 ± 0.029
70%0.352 ± 0.0540.377 ± 0.0430.370 ± 0.048

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.

Reviewer_4LCHOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies matrix product estimation when the two factor matrices contain missing or unobserved entries. It proposes estimating the product matrix CC directly rather than first completing the two factor matrices. The authors provide a theoretical optimality result in Theorem 4.2 and demonstrate the feasibility of the method through experiments.

Critical strengths
  1. The paper is clearly written and generally easy to follow.
  2. Directly estimating the product is intuitively reasonable in certain settings, and the experimental evaluation is fairly extensive.
Critical weaknesses
  1. The applicability and limitations of the method require further discussion. In terms of the quantities to be recovered, the product matrix contains rsrs entries, whereas the two factor matrices contain d(r+s)d(r+s) entries in total. Direct product estimation may therefore be advantageous when dd is much larger than rr and ss. However, when rr and ss are much larger than dd, estimating AA and BB first and then multiplying them may be more efficient. The experiments in Section 5.2 consider settings where rr and ss are much smaller than dd, but do not examine the opposite regime. The authors should clarify when direct product estimation is preferable and when completing the factor matrices first is more advantageous.
  2. The results in Sections 3.2 and 3.3 rely on the Gaussian assumption for XkX_k and YkY_k. For non-Gaussian data, the authors should clarify whether the method should be interpreted as a Gaussian approximation to the original distribution. Does the optimality guarantee still hold in this case? The relationship between the non-Gaussian experimental results in Section 5.2 and the theoretical guarantees also requires clarification.
  3. In Equation (2), the notation XkX_k and YkY_k suppresses the dependence on ii and jj. This notation should be clarified.
  4. The problem is related to matrix completion. Relevant literature should be cited, and the distinction between the settings should be clarified: matrix completion typically considers a partially observed target matrix, whereas this paper considers missing entries in the factor matrices.
  5. Theorem 4.2 appears to be a general result stating that the conditional expectation is the minimum mean squared error (MMSE) estimator. The contribution of the theorem itself is unclear.
Questions for authors
  1. Please explain why the oracle estimator is defined as C~ij=∑k=1dE[XkYk∣Ok]\widetilde C_{ij}=\sum_{k=1}^{d}\mathbb E[X_kY_k\mid O_k]. Intuitively, the estimator of CijC_{ij} seems to be E[∑k=1dAikBkj∣all observed information]\mathbb E[\sum_{k=1}^{d}A_{ik}B_{kj}\mid\text{all observed information}]. What is the relationship between these two expressions, and why is it sufficient to condition each product term only on its local observed information? Does this equivalence follow from independence of the observed information across different coordinates?
  2. Could the authors provide more explanation and discussion of Equation (8)?
  3. What is the intuitive meaning of Equation (10), and why can it serve as a criterion for selecting the covariance estimate?
  4. Do the clipping bounds in Equation (12) follow from the Cauchy–Schwarz inequality?
  5. In recommendation systems, the estimation of the rating matrix RR is typically of interest. Section 5.5 instead estimates the item–item product. What is the specific significance of this target for the recommendation task?
3 comments

We thank the reviewer for the constructive feedback. We address each point below and clarify the corresponding aspects of our work.

W1. [Applicability and matrix dimensions]. We agree that the relative dimensions affect the efficiency of M3M^3. However, comparing the number of input and output entries does not establish computational efficiency, since impute-then-compute methods still require matrix multiplication, while M3M^3 avoids reconstructing the complete operands. We conducted additional experiments covering the opposite regime, where r,s>dr,s>d. Table R3.1 shows that M3M^3 is still competitive with imputations, and importantly, it is super fast. We will clarify this limitation and the distinction between statistical and computational efficiency.

Table R3.1. Relative Frobenius error and runtime comparison when the outer dimensions exceed the contracted dimension. Experiments use synthetic Gaussian matrices of dimensions 256×64256\times64 and 64×25664\times256, with MCAR missing rates of 20%, 30%, 50%, and 70%, and 10 random seeds.

Missing RateMetricMeanKNNISoftImputeGAINPICAMIWAEM³
20%Error0.267 ± 0.0330.141 ± 0.0040.138 ± 0.0020.170 ± 0.0080.145 ± 0.0030.132 ± 0.0030.130 ± 0.005
Runtime (s)0.002 ± 0.0000.103 ± 0.0090.195 ± 0.0402.116 ± 0.6873.785 ± 0.3262.107 ± 0.5040.034 ± 0.005
30%Error0.361 ± 0.0460.185 ± 0.0080.185 ± 0.0020.256 ± 0.0170.198 ± 0.0050.170 ± 0.0030.180 ± 0.006
Runtime (s)0.004 ± 0.0040.138 ± 0.0480.279 ± 0.1052.073 ± 0.5324.931 ± 1.5332.358 ± 1.2560.035 ± 0.017
50%Error0.518 ± 0.0640.283 ± 0.0160.300 ± 0.0050.757 ± 0.0690.523 ± 0.1360.265 ± 0.0090.260 ± 0.018
Runtime (s)0.004 ± 0.0010.130 ± 0.0700.310 ± 0.0602.140 ± 0.9007.350 ± 3.5601.970 ± 0.4700.037 ± 0.014
70%Error0.651 ± 0.0730.439 ± 0.0250.487 ± 0.0072.792 ± 0.28895.245 ± 83.0740.412 ± 0.0210.460 ± 0.043
Runtime (s)0.004 ± 0.0020.210 ± 0.0800.360 ± 0.1103.420 ± 1.2607.180 ± 2.1802.590 ± 0.7900.050 ± 0.022

W2. [Gaussian assumption and non-Gaussian optimality]. We clarified that M³ uses Gaussianity as a working model. Importantly, Theorem 4.2 does not require Gaussianity: the oracle remains MMSE-optimal under Assumption 4.1, provided the true conditional expectations are used. In contrast, Theorem 4.3 establishes exact error reductions specifically under the Gaussian model. For non-Gaussian data, the practical M³ estimator serves as a Gaussian approximation and is not guaranteed to remain optimal. Our experiments on Student-t5, Gaussian mixture, skewed, and Laplace distributions demonstrate its empirical robustness beyond Gaussianity, rather than extending the theoretical guarantees. We will clarify this distinction in the paper.

W3, W5 & Q1. [Notation and oracle optimality]. For each fixed output pair (i,j)(i,j), we define Xk=AikX_k=A_{ik} and Yk=BkjY_k=B_{kj}, suppressing the indices for simplicity, see Eq. (2) in line 136. We agree that the MMSE property of conditional expectation is classical. Theorem 4.2 applies this principle to our matrix-product setting. Under Assumption 4.1, independence across coordinates ensures that

=\sum_{k=1}^{d}\mathbb E[X_kY_k\mid O_k],$$ where $\mathcal F_{ij}$ contains all pair-local observations. Thus, conditioning on each $O_k$ is sufficient, and the resulting oracle is optimal within this information set. This equivalence need not hold when coordinates are dependent. Our contribution is not the general MMSE principle itself, but its formulation as a missing-aware multiplication operator.

W4. [Relation to matrix completion]. Classical matrix completion aims to reconstruct a partially observed target matrix, often exploiting low-rank structure [1,2]. In contrast, M3M^3 considers missing entries in the two operand matrices and directly estimates their realized product without reconstructing either operand. Moreover, M3M^3 does not require a low-rank assumption. We will clarify this distinction and include the relevant literature in the revised paper.

Q2–Q4. Covariance estimation and numerical stability. Eq. (8) provides a feasible way (via a cubic equation) to estimate the covariance for practical M3M^3. This is obtained by setting the derivative of the Gaussian plug-in log-likelihood w.r.t. the covariance to zero. Eq. (10) then selects the candidate maximizing the likelihood, including the stability boundaries, since multiple feasible roots may exist.

Regarding Eq. (12): Yes, the bounds follow from the Cauchy–Schwarz inequality, which requires ∣τij∣≤viAvjB|\tau_{ij}|\leq\sqrt{v_i^A v_j^B}. The additional factor (1−ϵ)(1-\epsilon) ensures strict positive definiteness and numerical stability. We will clarify these steps in the revised paper.

Q5. Significance of the item–item product in recommendation. Our experiment uses item-based collaborative filtering, which needs an item-item matrix to capture the similarities among items to improve the final recommendation. Here, computing item-item matrix is a computational intermediate of the recommendation models, not the final prediction but strength the prediction process [3]. M3M^3 replaces only the impute-then-multiply step; all methods share the same downstream scoring procedure and are evaluated using held-out recommendation metrics. Our approach can also strengthen the recommendation process via similar methods (e.g., user-user matrix estimation). We will clarify this motivation and scope in Section 5.5.


References: [1] Candes, E., & Recht, B. (2012). Exact matrix completion via convex optimization. Communications of the ACM, 55(6), 111-119.

[2] Mazumder, R., Hastie, T., & Tibshirani, R. (2010). Spectral regularization algorithms for learning large incomplete matrices. The Journal of Machine Learning Research, 11, 2287-2322.

[3] Shi, Y., Larson, M., & Hanjalic, A. (2014). Collaborative filtering beyond the user-item matrix: A survey of the state of the art and future challenges. ACM Computing Surveys (CSUR), 47(1), 1-45.

Thank you for your response and clarification. As I understand it, the method characterizes the product distribution under a Gaussian prior model, using Gaussian approximations and parameter estimation for XkX_k and YkY_k, and estimates the product through conditional expectation. This appears to follow a standard MMSE estimation procedure, while the optimality stated in Theorem 4.2 follows from the general MMSE property of conditional expectation. From my side, the contribution and theoretical novelty of the paper are limited. I therefore maintain my original score.

Reviewer_3u7rOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes M3, an operator for estimating C = AB when both A and B have missing entries. For each output entry (i, j), it treats the pairs (A_ik, B_kj) over k as i.i.d. draws from a bivariate Gaussian, with masks independent of the values (MCAR). Each missing contribution A_ik·B_kj is replaced by its conditional expectation given what is observed, in closed form for the four observed/missing patterns. Means and variances are estimated from all observed entries in the row or column. The covariance is the root of a cubic likelihood equation over jointly observed entries, then shrunk and clipped. The cost is O(rds). Theorem 4.2 shows the oracle rule is the MSE-optimal estimator given pair-local information. Theorem 4.3 gives the exact MSE gain over mean imputation per pattern. Experiments use synthetic 16×256 by 256×16 products, Gram and PCA-eigenvalue recovery on five small real datasets, PLS singular values on four datasets, and item–item products on a 1000×100 Jester subset. All use MCAR at 20–70% missingness. M3 is best in most settings, with growing margins as missingness rises.

Critical strengths
  1. Estimating the product rather than the operands is a sensible idea, and the four-pattern decomposition is easy to follow. I believe using one-sided observations (patterns 10 and 01) that complete-pair estimators throw away is the right intuition.
  2. Simple, training-free, and cheap. The method has no learned parameters, a fixed configuration, and the same asymptotic cost as dense multiplication.
  3. It reduces exactly to mean imputation when tau=0, which is a nice sanity check.
  4. I checked Proposition 3.2 and Theorem 4.3, and they seemed correct from what I can tell.
  5. The paper is upfront that optimality is pair-local and asymptotic.
  6. M3 stays accurate at 70% missingness, where imputers such as GAIN degrade sharply, and it holds up under non-Gaussian synthetic data. This shows it is quite robust at high missingness regimes.
  7. Full tables with standard deviations are in the appendix.
  8. Code is included in the supplement (though I admit I didn't check it)
Critical weaknesses
  1. I'm not so clear on what is the main novelty w.r.t. DPER. Am I correct that the main difference lies in estimating the realized sum rather than the population moment, which matters little for large d? The paper should state precisely what is new relative to DPER, and DPER should be compared in every setting where it applies, not just Gram recovery
  2. Matrix multiplication is broader than what the model supports. Assumption 3.1 requires the k-th entries of a row of A and a column of B to be exchangeable draws with a constant mean and covariance. That is reasonable when k indexes samples (Gram, covariance, cross-covariance, item–item similarity), but not for typical ML products like XW with a weight matrix, attention, or features with column-specific scales. The title and the claim of being "the first operator designed to directly estimate a matrix product AB" suggest generality that the experiments never test. Every experiment is a second-moment product over samples.
  3. The generator in Appendix B.4 builds A_ik and B_kj from a shared latent Z_k with constant covariance a_i·b_j across k, which is exactly the pair-local bivariate model that the assumptions require. Only the marginal shape varies. It would be interesting to see a test where the assumption fails (k-dependent means or variances, heteroskedastic columns, low-rank structure that cross-row methods can exploit).
  4. Everything relies on masks independent of values, and every experiment injects MCAR noise, including on top of Jester, whose real missingness is not at random. There are no MAR or MNAR experiments, and no discussion of how biased M3 becomes under them.
  5. The cross-view tasks are tiny: Gapminder and Seals are 2-by-2 feature views, Diamonds is 4-by-3, so leading singular values of 2×2 matrices are being recovered. The synthetic products are 16×256. The recommendation gains are small and NDCG is not improved. Baselines run with defaults and no tuning, and natural competitors are missing: EM-based Gaussian imputation (global conditional means), MICE or IterativeImputer with a linear model, and the inverse-probability-weighted complete-pair estimator for the cross-product tasks.
Questions for authors

See weaknesses.

2 comments

We appreciate the reviewer recognizing our strength. We also agree that there are some limitations, but we would like to clarify these to avoid making them critical weaknesses.

W1. [Novelty relative to DPER]. DPER estimates population moments, whereas M3M^3 estimates the realized matrix product directly, i.e., DPER(X)=Σ^DPER(X) = \widehat{\Sigma} while M3(X,Y)=XY^M^3(X,Y) = \widehat{XY}. Moreover, the difference does not vanish as dd increases. For example, consider independent standard Gaussian pairs (Xk,Yk)(X_k,Y_k), where P(observed) = 0.5 for each entry. A population-moment predictor estimates the realized sum as zero, with MSE of dd. In contrast, the oracle M3M^3 estimator retains observed products and achieves MSE 0.75d0.75d, a 25% reduction regardless of dd. We will make it clear in the revision.

Possible comparison. DPER is a task-specific method for gram recovery only.

W2. [Generality of matrix multiplication]. We will clarify that the theoretical scope of M3M^3 primarily covers products formed from paired observations, rather than claiming guarantees for all matrix multiplication tasks, which may be impossible. We agree that we overstated this point.

W3. [Synthetic data and model assumptions]. The Gaussian generator follows our pair-local model; however, the four non-Gaussian generators do not satisfy the bivariate Gaussian assumption, so the experiments already test some distributional misspecification. Please see W3. Gaussian assumption/Reviewer UDUV for more information about this strategy.

Additionally, to further address this concern, we test two violations of the i.i.d. assumption: Mean Shift, adding αsin⁡(2kπ/d)\alpha \sin(2k\pi/d) to both matrices, and Heteroskedasticity, scaling centered entries by a normalized factor exp⁡(βcos⁡(2kπ/d))\exp(\beta \cos(2k\pi/d)). We vary α,β∈0,0.5,1,2\alpha,\beta \in \\{0,0.5,1,2\\}, using 50% MCAR missingness and 10 seeds (See Table R2.1). Interestingly, M3M^3 outperforms mean imputation across all settings, although its error increases with variance heterogeneity while decreasing under mean shifts.

Table R2.1. Relative Frobenius error of M3M^3 and mean imputation under violations of the i.i.d. assumption. Experiments use synthetic Gaussian matrices of dimensions $16 \times 256$ and 256×16256 \times 16.

Assumption ViolationLevelM³Mean
Mean Shift00.182 ± 0.0240.496 ± 0.082
Mean Shift0.50.179 ± 0.0200.563 ± 0.073
Mean Shift10.162 ± 0.0160.665 ± 0.044
Mean Shift20.133 ± 0.0130.739 ± 0.010
Heteroskedasticity00.182 ± 0.0240.496 ± 0.082
Heteroskedasticity0.50.203 ± 0.0270.498 ± 0.085
Heteroskedasticity10.238 ± 0.0340.502 ± 0.089
Heteroskedasticity20.288 ± 0.0450.505 ± 0.097

W4. [MAR and MNAR mechanism]. Our research focuses on MCAR, extending M3M^3 to MAR and MNAR is beyond the scope of this work, as already acknowledged in our Discussion section. We believe that it should be viewed as a limitation rather than a critical weakness. Nevertheless, we respect the review and conducted additional MAR and MNAR experiments (See Table R2.2). Generally, the error of M3M^3 and mean imputation increases across these mechanisms compared to the MCAR mechanism; however, M3M^3 is still better than mean imputation.

Table R2.2. Relative Frobenius error of M3M^3 and mean imputation under MAR and MNAR missingness. Experiments use synthetic Gaussian matrices of dimensions 16×25616 \times 256 and 256×16256 \times 16, with missing rates of 20%, 30%, 50%, and 70%. Results are averaged over 10 random seeds.

Missingness MechanismMissing RateM³Mean
MAR20%0.178 ± 0.0380.321 ± 0.066
MAR30%0.251 ± 0.0490.414 ± 0.081
MAR50%0.405 ± 0.0660.561 ± 0.103
MAR70%0.622 ± 0.0970.703 ± 0.116
MNAR20%0.430 ± 0.0680.508 ± 0.086
MNAR30%0.542 ± 0.0750.605 ± 0.102
MNAR50%0.702 ± 0.0560.790 ± 0.078
MNAR70%1.196 ± 0.2051.199 ± 0.166

W5. [Experimental scale and missing baselines]. We agree that some cross-view tasks involve small output matrices and that the recommendation gains are modest, particularly for NDCG@10. However, the inner dimension is larger than the output dimension, and Appendix D already evaluates products up to 128×2048×128128 \times 2048 \times 128. Importantly, we do not aim to develop an omnipotent method; we show that our method can be competitive with task-specific methods, not to replace them.

Our experiments already cover 8 imputation methods and 7 task-specific baselines. In particular, PICA (2026), which is already based on the global conditional mean, a recent state-of-the-art method, is highly competitive with existing imputation methods. We therefore believe that our current baselines are sufficiently representative, and adding more methods would not necessarily provide further insights, but could make the experimental analysis unnecessarily complex. Nevertheless, we report the results for IPW for the cross-product task in Table R2.3, where M3M^3 still outperforms IPW for all settings.

Table R2.3. Relative Frobenius error of M3M^3 and IPW for cross-product recovery on four real-world datasets. Results are reported under MCAR missingness at rates of 20%, 30%, 50%, and 70%, averaged over 10 independent runs.

DatasetMissing RateM³IPW
Diamonds20%0.011 ± 0.0060.035 ± 0.003
Diamonds30%0.011 ± 0.0080.036 ± 0.003
Diamonds50%0.030 ± 0.0040.057 ± 0.003
Diamonds70%0.104 ± 0.0350.213 ± 0.008
Breast Cancer20%0.016 ± 0.0060.018 ± 0.010
Breast Cancer30%0.036 ± 0.0070.052 ± 0.013
Breast Cancer50%0.084 ± 0.0380.192 ± 0.039
Breast Cancer70%0.234 ± 0.0340.593 ± 0.058
Gapminder20%0.069 ± 0.0550.154 ± 0.018
Gapminder30%0.083 ± 0.0720.155 ± 0.022
Gapminder50%0.097 ± 0.0100.190 ± 0.043
Gapminder70%0.142 ± 0.1130.240 ± 0.057
Seals20%0.029 ± 0.0070.091 ± 0.010
Seals30%0.009 ± 0.0040.039 ± 0.019
Seals50%0.033 ± 0.0220.177 ± 0.039
Seals70%0.084 ± 0.0080.219 ± 0.053
Reviewer_UDUFOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This works proposes M3, which computes matrix-multiplication with missing values.

The contributions are summarized clearly by the authors: the proposed M3 estimator; an analysis for the oracle estimator; the empirical verifications.

Critical strengths
  1. This writeup is very friendly to human readers. I can understand the claims and the derivations by following the writings.
  2. The raised question can be very interesting: estimating the product directly can be more important than estimating individual matrices.
  3. The empirical results on real data can be interesting; unfortunately I am not familiar with what a good baseline on these benchmarks should be.
Critical weaknesses
  1. The proposed estimator is almost (regularized) the MLE of the assumed distribution. This makes: a. the estimator to be non-robust to real distributions. b. the idea to be relatively straightforward.
  2. The theory analyses in Section 4 is done for the oracle MLE, which is also quite straightforward for MSE loss. The role of regularization and the estimation error of the practical estimator is not studied. There is also no explicit quantitative error bound.
  3. The proposed Gaussian assumption can use some justification / empirical evidence. Why is this a good assumption? It seems to fail if A, B have some underlying structure (e.g., sparsity, low rank, etc) which is often the case in imputation setups.

Minor: The authors should claim the achieved complexity to be computation complexity.

Questions for authors

See weaknesses.

3 comments

We thank the reviewer for constructive feedback, but there are still some misunderstandings and unclear points, which could lead to inappropriate reviews. We would like to clarify these as follows:

W1. [Our method and MLE]. We confirm that M3M^3 is NOT itself an MLE of the product, and the shrinkage in Eq. (11) is also NOT a penalized likelihood solution. Proposition 3.3 estimates the moments via MLE, whereas Eq. (9) defines the final estimate of M3M^3. In addition, Eq. (11) is a post-estimation shrinkage for stabilization.

Regarding robustness, to the best of our knowledge, MLE does not necessarily imply poor robustness to non-Gaussian distributions [1]. Empirically, our experiments provide empirical evidence that the proposed Gaussian working approximation remains effective across several non-Gaussian distributions (Student, Gaussian mixtures, skewed distributions, and Laplace).

W2. [Theoretical analysis]. We try our best to provide useful insights for readers, not to cover everything. More specifically, M3M^3 uses pair-local and dependence information, so the natural questions are about its optimality among methods that use the same information and how much it achieves in exact error reduction without dependence (this is a quantitative error). Therefore, we agree that the current version does not fully capture the properties of the practical estimator, yet still offers useful insights.

W3. [Gaussian assumption]. We chose Gaussian as a familiar and mathematically feasible starting point, allowing closed-form estimators. Starting with a Gaussian model and evaluating its performance under non-Gaussian distributions is also common in the literature [2,3,4,5]. Importantly, in M3M^3, we use a mild assumption because we assume Gaussianity only for each pair of operands, not for the whole matrix. Moreover, the linear conditional expectations used by M³ also hold for certain non-Gaussian elliptical distributions [6].

Moreover, could you please elaborate on your review: "It seems to fail if A, B have some underlying structure"? This is because, from our side, low-rank structure and Gaussian modeling are not incompatible. Moreover, sparsity in the imputation setup means a high missing rate, which is not really a major problem for M3M^3; we studied up to 70% missingness.

Minor comment. We agree and will use the term “computational complexity” to avoid ambiguity.


References:

[1] Arminger, G., & Schoenberg, R. J. (1989). Pseudo maximum likelihood estimation and a test for misspecification in mean and covariance structure models. Psychometrika, 54(3), 409-425.

[2] Demirtas, H., Freels, S. A., & Yucel, R. M. (2008). Plausibility of multivariate normality assumption when multiply imputing non-Gaussian continuous outcomes: a simulation assessment. Journal of Statistical Computation and Simulation, 78(1), 69-84.

[3] Yucel, R. M., & Demirtas, H. (2010). Impact of non-normal random effects on inference by multiple imputation: A simulation assessment. Computational statistics & data analysis, 54(3), 790-801.

[4] Lee, K. J., & Carlin, J. B. (2017). Multiple imputation in the presence of non‐normal data. Statistics in medicine, 36(4), 606-617.

[5] Nguyen, T., Nguyen-Duy, K. M., Nguyen, D. H. M., Nguyen, B. T., & Wade, B. A. (2022). Dper: Direct parameter estimation for randomly missing data. Knowledge-Based Systems, 240, 108082.

[6] Landsman, Z., Vanduffel, S., & Yao, J. (2013). A note on Stein's lemma for multivariate elliptical distributions. Journal of Statistical Planning and Inference, 143(11), 2016-2022.

Reviewer_UDUFOpenReview ↗

Thanks

I thank the authors for the response. I would like to clarify what I meant,

  1. The justified equations (mostly in section 3.2) comes from MLE.
  2. Eq 9 plugin the estimated moments, and I am not sure if it is a significant contribution to support a submission.
  3. I appreciate the honesty in analyses, but still the analyses is trivial (to me) and does not apply to the proposed M3.
  4. "It seems to fail if A, B have some underlying structure": For example, if A, B are generated as the basis for random low-rank subspaces, then the Gaussian assumption fails.

Hence, I will keep my score.

We would like to clarify the last point: the Gaussian assumption can fail, as we have already tested with non-Gaussian distributions, but that does not mean that M3M^3 will fail. However, we understand your concern. The paper will benefit from including some experiments on this kind of distribution. We will update in the revision.

Thank you again for your feedback.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.