Matrix Completion (Imputing Data)

Preface

Imagine the setting where the entire dataset was peppered with missing values, as opposed to if only one feature had its entire column missing.

Definition

The goal is to impute (fill in) the missing values.

A standard approach is to use a matrix factorization technique, like PCA. The idea is that if we find the latent vector \(\mathbf{h}\) for the input vector \(\mathbf{x}\), then we can estimate the missing values in \(\mathbf{x}\) by using the predicted \(\mathbf{\hat{x}}\):

\[ \mathbf{x} \approx \hat{\mathbf{x}} = \mathbf{hD} \]

Thus, we solve for the minimization problem to find \(\mathbf{h}, \mathbf{D}\):

\[ \min_{\mathbf{h_{1}, \dots, h_{n}}\in \mathbb{R}^{1\times p}, \mathbf{D}\in \mathbb{R}^{p \times d}} \sum_{i=1}^n \sum_{j \in \mathcal{ A_{i}}}(x_{ij} - \mathbf{h_{i}D_{:j}})^2 \]

Which basically says: we want to first find the best \(\mathbf{D}\) and then find the best \(\mathbf{h}\) across all of the available (\(\mathcal{A_i}\)) data points such that \(\mathbf{x - hD}\) is minimized.

References

Principal Component Analysis (PCA)