Source-linked AI summary
Transposable regularized covariance models with an application to missing data imputation
Genevera I. Allen, Robert Tibshirani
TL;DR
Missing-value estimation in matrix data is challenging, especially when relationships across rows and columns matter. The paper develops regularized transposable covariance models and EM-type imputation methods. Its simulations report competitive performance against common single-imputation methods, while the approach has computational and modeling boundaries.
Problem
Missing ratings and other matrix entries are difficult to estimate when relationships among both rows and columns matter, while one-axis or SVD approaches may miss complex cross-cell relationships.
Source: §1 · pp. 1–2Method
Results
In simulations, TRCMAimpute is competitive with SVD and k-nearest neighbor imputation, and its one-step approximation performs comparably or slightly better than MCECM across missing-value percentages.
Source: §4.2.3 · p. 18, §5.1 · p. 20Takeaways & Limitations
The transposable model and computational methods provide a parametric approach to missing-value estimation in high-dimensional matrices with complex row and column correlations.
Source: §6 · p. 26Direct inversion can be computationally expensive even for medium-sized matrices; a 100 × 50 example is reported to cost around O(10^10).
Source: §4.1.2 · p. 14
Abstract
from arXiv · showhide
Missing data estimation is an important challenge with high-dimensional data arranged in the form of a matrix. Typically this data matrix is transposable, meaning that either the rows, columns or both can be treated as features. To model transposable data, we present a modification of the matrix-variate normal, the mean-restricted matrix-variate normal, in which the rows and columns each have a separate mean vector and covariance matrix. By placing additive penalties on the inverse covariance matrices of the rows and columns, these so-called transposable regularized covariance models allow for maximum likelihood estimation of the mean and nonsingular covariance matrices. Using these models, we formulate EM-type algorithms for missing data imputation in both the multivariate and transposable frameworks. We present theoretical results exploiting the structure of our transposable models that allow these models and imputation methods to be applied to high-dimensional data. Simulations and results on microarray data and the Netflix data show that these imputation techniques often outperform existing methods and offer a greater degree of flexibility.
1. Introduction.
Sparse matrix data make missing-value estimation difficult, and many existing methods focus on only rows, columns, or linear combinations of ratings. The paper proposes a transposable covariance model and computational methods for fitting it to one matrix and imputing missing values.
1. Introduction.
- The Netflix example has about 18,000 movies, several hundred thousand customers, and only a small percentage of ratings observed, motivating prediction of unrated movies.The ratings may reflect relationships among both customers and movies.Source: §1 · p. 1
- Movie-centric and user-centric methods, as well as SVD, can miss more complex relationships between customers and movies [Troyanskaya et al. (2001); Bell, Koren and Volinsky (2007)].The introduction notes that one customer's rating of one movie can relate to another customer's rating of a different movie beyond the separate customer or movie connections.Source: §1 · p. 2
- The proposed matrix-variate normal model treats rows and columns as features, modeling their separate covariances and cross-cell relationships through a Kronecker product.This directly represents interactions between pairs of customers and pairs of movies.Source: §1 · p. 2
- Restrictions on means and penalties on inverse covariances enable fitting the transposable model to one matrix, with nonsingular covariance estimates and computationally efficient EM-type imputation.The paper also develops efficient calculations for conditional distributions and expectations of scattered missing values.Source: §1 · p. 2
2. Regularized covariance models and imputation with multivariate data.
Regularized covariance models penalize the inverse covariance to obtain nonsingular estimates, including when features outnumber observations. The paper uses this model in an EM imputation algorithm by substituting a regularized covariance estimate in the maximization step.
2. Regularized covariance models and imputation with multivariate data.
- Nonsingular regularized covariance estimates enable covariance estimation when the number of features exceeds the number of observations.This is the stated motivation for using regularized covariance models in high-dimensional settings.Source: §2 · p. 3
- The regularized covariance model estimates covariance from i.i.d. multivariate normal observations and adds a penalty to the inverse covariance matrix.The penalty can be L1 or L2; L1 estimates can be sparse and support undirected graph estimation.Source: §2 · p. 3
- With an L2 penalty, regularization acts on covariance eigenvalues and retains all nonzero eigenvalues, unlike a rank-k SVD approximation.The passage states that when p > n, the final n − r values of θ are constant and equal to 2pρ/n.Source: §2 · p. 4
- RCMimpute maximizes the observed penalized log-likelihood by EM, using the regularized covariance MLE in the M step to produce nonsingular estimates.The paper describes this as a penalized EM algorithm that can be used when p > n.Source: §2 · p. 4
3. Transposable regularized covariance models.
The section builds a transposable covariance model with additive row and column means and covariances, then regularizes and estimates those covariances. Separate penalties provide flexibility, while estimation guarantees depend on the penalty choice.
3.1. Mean-restricted matrix-variate normal distribution.
- The mean-restricted matrix-variate normal represents the mean matrix as additive row and column effects and uses a Kronecker-product covariance structure.This restriction reduces the mean parameters for a single observed matrix and gives multivariate normal marginals.Source: §3.1 · pp. 4–6
3.2. Transposable Regularized Covariance Model (TRCM).
- TRCM separately penalizes the inverse row and column covariance matrices, allowing different penalty types and parameters for the two dimensions.Separate penalties are not equivalent to penalizing the Kronecker-product covariance and also yield simple parameter-estimation strategies.Source: §3.2 · p. 6
3.3. Parameter estimation.
- Block coordinate-wise maximization converges to a stationary point for L1 or L2 penalties, but is not guaranteed to reach the global maximum.Iterations monotonically increase the penalized log-likelihood; potential multiple stationary points are especially noted for L1 penalties.Source: §3.3 · pp. 7–8
3.3.1. Covariance estimation for L2 penalties.
- With L2 penalties on both covariance matrices, estimation has a unique global solution, and the covariance eigenvectors are the left and right singular vectors of X.The covariance-estimation problem reduces to an eigenvalue minimization with a unique analytical solution.Source: §3.3.1 · pp. 8–9, §3.3 · p. 8
- L2 TRCM and rank-reduced SVD share similarities but differ in covariance structure and use of singular vectors.TRCM uses all singular vectors and a common row covariance matrix, whereas rank-reduced SVD uses only the leading vectors and allows row covariances to vary with them.Source: §3.3.1 · pp. 9–10
4. Imputation for transposable data.
The section develops an MCECM imputation algorithm for transposable regularized covariance models and a one-step approximation for high-dimensional data. It also gives structured conditional-expectation calculations and reports that the approximation performs comparably to the fully iterated method in simulations.
4.1.1. Algorithm.
- MCECM alternates conditional-expectation and conditional-maximization steps, updating row and column inverse covariances in turn to maximize the observed penalized log-likelihood.The E step has equivalent forms that enable maximization with respect to either covariance block.Source: §4 · p. 10, §4.1.1 · pp. 11–12
4.2. One-step approximation to TRCMimpute.
- For high-dimensional data, the fully iterated MCECM is computationally infeasible, motivating a one-step approximation and new structured conditional-distribution methods.The section also notes a Gibbs-sampling Bayesian variation in the Supplementary Materials.Source: §4 · p. 10
4.1.2. Computational considerations.
- For a 100 × 50 matrix, directly inverting the Kronecker covariance can cost around O(10^10), making the approach computationally expensive even at medium dimensions.The stated inversion cost is of order O(n^3p^3), depending on the amount of missing data.Source: §4.1.2 · p. 14
4.2.1. One-step algorithm.
- The one-step method initializes from row- and column-marginal RCM imputations, averages them, estimates TRCM parameters with missing values fixed, then takes a conditional-expectation imputation.It omits the covariance-correction part of the E step because its goal is imputation rather than parameter estimation.Source: §4.2.1 · p. 15
- Saving the marginal imputations also gives three candidate estimates, letting cross-validation select whether to penalize row covariances, column covariances, or both.This addresses uncertainty about whether rows or columns are independent.Source: §4.2.1 · p. 15
4.2.2. Conditional expectations.
- Conditional expectations can be computed iteratively from row and column distributions, avoiding the full Kronecker inversion and reducing operation order from O(n^3p^3) to O(n^3 + p^3).The alternating conditional-expectations algorithm converges to E(X_m|X_o).Source: §4.2.2 · p. 17
4.2.3. Numerical comparisons.
- Across all missing-value percentages, one-step TRCMAimpute is comparable to or slightly better than MCECM in imputation error; at 25% missingness, its first-step observed log-likelihood is higher and very close to the fully iterated maximum.Source: §4.2.3 · p. 18
5. Results and simulations.
The simulations compare one-step TRCM imputation with common single-imputation methods across covariance structures and missingness levels; microarray and Netflix analyses assess performance on real data. Overall, TRCM-based methods compare favorably in simulations and often outperform competitors in the reported real-data settings.
5.1. Simulations.
- The simulations cover multivariate and matrix-variate distributions, dimensions 50 × 50 and 100 × 10, missingness from 10% to 75%, and nonnormal Chi-square and Poisson data.Comparisons include SVD and KNN imputation; parameters are selected by five-fold cross-validation.Source: §5.1 · pp. 19–20, Table 1 · p. 21, Table 2 · p. 22
- TRCMAimpute is competitive with SVD and k-nearest-neighbor imputation across simulations, performs best against them for full equal-off-diagonal covariances, and appears robust to nonnormality and outliers.The simulations also report that L2 penalties outperform other TRCM penalty types; the authors suggest the globally unique covariance solution may explain this.Source: §5.1 · p. 20
5.2. Microarray data.
- The microarray analysis uses a kidney cancer dataset with 14,814 genes and 178 samples, evaluating randomly deleted values and deletions matching the original missingness pattern.Cross-validation selected the marginal multivariate model for TRCMAimpute in this dataset.Source: §5.2 · pp. 22–23
- On kidney cancer microarray data, TRCMAimpute outperforms competing methods in imputation error across missingness proportions, and has mean absolute error 0.37 versus 0.46 for SVDimpute.With values deleted in the original missingness pattern, TRCMAimpute also has lower absolute errors at each reported quantile and fewer outliers than competing methods.Source: §5.2 · pp. 23–24, Figure 2 · p. 23
5.3. Netflix data.
- The Netflix evaluation uses the top 250 customers and movies, rather than the full dataset, because assessing the full data was not feasible; the subset omits potentially predictive correlated customers or movies.The authors caution that subset RMSE is expected to be higher than RMSE on the full dataset.Source: §5.3 · pp. 24–25
- On the tested Netflix subset with 95% missing ratings, TRCMAimpute has RMSE 1.049 versus 1.084 for SVD and 1.354 for movie averages.For entries missing in the original pattern at 74% missing, L2:L2 has RMSE 1.005, followed by L1:L1 at 1.029, SVD at 1.032, and KNN at 1.184.Source: Figure 3 · p. 25, §5.3 · pp. 25–26
6. Discussion.
The discussion presents TRCMs as a framework for nonsingular row and column covariance estimation from a single matrix, with efficient conditional calculations supporting applications to high-dimensional data. It also notes limits involving overlap requirements, computational cost, model structure, and downstream use of imputed data.
6. Discussion.
- The authors present the model and imputation methods as a foundation for applications to high-dimensional data with potentially complex row and column correlations.The discussion describes the framework as a parametric model for matrix data.Source: §6 · p. 26
- MCECM and one-step imputation require every row pair and every column pair to share at least one jointly observed entry.TRCMAimpute also has a stated cost involving sums of cubed smaller observed/missing counts, plus n^3+p^3.Source: §6 · p. 26
- The paper distinguishes missing-value imputation from matrix completion, which focuses on matrix reconstruction, and notes that its single-imputation procedure can be extended to multiple imputation.The extension uses posterior samples with a Bayesian one-step approximation described in the Supplementary Materials.Source: §6 · pp. 26–27
- The discussion leaves the ultimate use and analysis of imputed data unaddressed, noting that these can dictate the imputation approach.The authors present their methods as a foundation for extending work on these issues.Source: §6 · p. 27
- The model does not assume the Kronecker covariance structure suits every dataset; it treats element locations within rows and columns as determining their distributions.If either row or column covariance is the identity matrix, the model reduces to the familiar multivariate normal.Source: §6 · p. 27
- TRCMs provide nonsingular estimation of row and column covariances from a single observed matrix, with potential uses in hypothesis testing, classification, prediction, and data mining.The discussion also identifies efficient conditional-distribution and expectation calculations as making the model computationally feasible for many applications.Source: §6 · p. 27
SUPPLEMENTARY MATERIAL
The supplementary materials collect methods, numerical results, algorithmic discussions, and proofs supporting the paper.
SUPPLEMENTARY MATERIAL
- The supplement includes the multivariate RCMimpute method, numerical results on TRCM covariance estimation, and discussion of MCECM imputation properties.Source: SUPPLEMENTARY MATERIAL · p. 27
- It provides computations for the Alternating Conditional Expectations algorithm and a Bayesian one-step approximation to TRCMimpute, along with a Gibbs sampling algorithm.Source: SUPPLEMENTARY MATERIAL · pp. 27–28
- The supplement also discusses cross-validation for penalty parameters and contains proofs of theorems and propositions.Source: SUPPLEMENTARY MATERIAL · p. 28