Matrix Completion

• categories: Linear algebra, Method, Problem

Definition

Matrix completion is the problem of recovering a full matrix from a subset of its observed entries. The task is to fill in the missing entries of a matrix while satisfying certain assumptions, such as low rank or sparsity.

Formally, let $M\in {\mathbb{R}}^{m\times n}$ be the matrix to be completed, and $\Omega$ denote the set of observed indices:

$$\Omega =\{(i,j)\mid M_{ij}\text{ is observed}\}.$$

The goal is to reconstruct $M$ such that:

1. $M_{ij}$ matches the observed values for $(i,j)\in \Omega$, and
2. $M$ satisfies additional assumptions (e.g., low rank).

---

Applications

1. [[Recommender Systems:
   Filling in missing entries in user-item rating matrices (e.g., Netflix or Spotify recommendations).

2. Image Processing:
   Recovering corrupted images by completing the pixel intensity matrix.

3. Sensor Networks:
   Estimating missing sensor measurements using spatial or temporal correlations.

4. Collaborative Filtering:
   Predicting preferences in social networks.

Key Assumptions

1. Low Rank:
   Many matrix completion problems assume that the underlying matrix $M$ has a low rank. This means:

   $$\text{rank}(M)\ll \min (m,n).$$

2. Sufficient Observations:
   For exact recovery, the number of observed entries must satisfy:

   $$|\Omega |\ge O(r(m+n))\text{(for rank r)}.$$

3. Incoherence:
   The observed entries should be uniformly distributed across the matrix.

---

Mathematical Formulation

Optimization Problem

The matrix completion problem is often posed as:

$$\text{minimize }\text{rank}(M),\text{subject to }{M}_{ij}=O_{ij},\forall (i,j)\in \Omega ,$$

where $O$ is the observed matrix with entries $O_{ij}$.

Relaxation Using Nuclear Norm

Since rank minimization is NP-hard, it is relaxed using the nuclear norm $\Vert M{\Vert }_{\ast }$:

$$\text{minimize }\Vert M{\Vert }_{\ast },\text{subject to }{M}_{ij}=O_{ij},\forall (i,j)\in \Omega .$$

Here, $\Vert M{\Vert }_{\ast }$ is the sum of singular values of $M$.

---

Algorithms

1. Singular Value Thresholding (SVT)

• Iteratively approximates the matrix by applying singular value decomposition (SVD) and thresholding the singular values.
• Steps:
  1. Initialize a guess for $M$.
  2. Perform SVD: $M_k=U_k{\Sigma }_k{V}_k^T$.
  3. Threshold the singular values in ${\Sigma }_k$.
  4. Update $M$ to satisfy observed constraints.

2. Alternating Least Squares (ALS)

• Assumes $M=U{V}^T$, where $U\in {\mathbb{R}}^{m\times r}$ and $V\in {\mathbb{R}}^{n\times r}$.
• Iteratively solves:

$$U={\text{argmin}}_U\Vert P_{\Omega }(U{V}^T-O){\Vert }_F^2,V={\text{argmin}}_V\Vert P_{\Omega }(U{V}^T-O){\Vert }_F^2,$$

where $P_{\Omega }$ projects onto the observed entries.

3. Gradient Descent

• Optimizes a loss function directly: $$\underset{M}{\min }\frac{1}{2}\Vert P_{\Omega }(M-O){\Vert }_F^2+\lambda \Vert M{\Vert }_{\ast }.$$
• Uses gradient-based methods to minimize the objective.

4. Probabilistic Matrix Factorization (PMF)

• Models the matrix as a probabilistic model and uses Bayesian inference for completion.