Low-Rank Matrix Completion

The fundamental premise of matrix completion is that the data matrix to be recovered has low intrinsic rank. This means the matrix's rows and columns are not independent; they lie in a lower-dimensional subspace. For example, in a user-movie rating matrix, this assumption implies that a small number of latent factors (e.g., genre preferences, actor appeal) explain most of the variation in user preferences. The Eckart–Young theorem guarantees that the truncated SVD provides the optimal low-rank approximation in the Frobenius norm.

Because directly minimizing matrix rank is a combinatorially hard, non-convex problem, a convex relaxation is used. The nuclear norm (or trace norm), defined as the sum of a matrix's singular values, serves as the convex surrogate for rank. Minimizing the nuclear norm, subject to the constraint that the observed entries are fitted, promotes low-rank solutions. This convex formulation enables the use of efficient optimization algorithms like singular value thresholding and the proximal gradient method.

Not all low-rank matrices can be completed from a few random observations. Successful completion requires the matrix to be incoherent. This means its singular vectors are not overly correlated with the standard basis (i.e., they are spread out, not sparse). Incoherence ensures the matrix's information is not concentrated in a few entries, allowing random sampling to capture its structure. Theoretically, an n x n matrix of rank r can be completed from O(r n log^2 n) observed entries with high probability under incoherence conditions.

Several specialized algorithms solve the nuclear norm minimization problem efficiently:

• Singular Value Thresholding (SVT): An iterative algorithm that applies a soft-thresholding operator to the singular values of a matrix constructed from the observed entries.
• Alternating Least Squares (ALS): A non-convex but highly practical approach that alternates between fixing the left and right factor matrices and solving a least-squares problem.
• Iterative Hard Thresholding (IHT): A greedy algorithm that performs a gradient step followed by hard thresholding of singular values to enforce a fixed rank constraint.
• Frank-Wolfe / Conditional Gradient: Iteratively adds rank-one updates to build a low-rank solution.

Real-world data often contains outliers or corruptions. Robust Principal Component Analysis (Robust PCA) extends the completion framework by decomposing the observed matrix M into M = L + S, where L is a low-rank matrix (the true signal) and S is a sparse matrix (the outliers/corruptions). This is solved by minimizing a combined objective: the nuclear norm of L plus the L1-norm of S. This makes the completion process resilient to corrupted or maliciously altered entries.

Low-rank matrix completion is a workhorse for recommendation systems and data imputation:

• Collaborative Filtering: The classic Netflix Prize problem: predicting user ratings for movies based on a sparse matrix of existing ratings.
• Sensor Network Data Recovery: Filling in missing readings from a grid of sensors (e.g., temperature, traffic) where each sensor's data is correlated with its neighbors.
• Image Inpainting: Recovering missing or corrupted pixels in an image by leveraging the fact that image patches often lie in a low-dimensional manifold.
• Genomic Data Imputation: Estimating missing values in gene expression matrices where experiments (columns) and samples (rows) share underlying biological patterns.

The nuclear norm (or trace norm) is the sum of a matrix's singular values. It serves as the convex surrogate for the non-convex rank function, making optimization tractable. In low-rank matrix completion, the nuclear norm is minimized to encourage a low-rank solution.

• Key Property: Convex relaxation of rank.
• Application: Primary regularizer in matrix completion formulations.
• Optimization: Solved via proximal gradient methods or singular value thresholding.

Singular value thresholding is the proximal operator for the nuclear norm. Given a matrix and a threshold parameter, it performs a soft-thresholding operation on the singular values from its SVD. This operation is the core computational step in iterative algorithms like Soft-Impute for nuclear norm minimization.

• Mechanism: Apply shrinkage: max(σ_i - τ, 0) to each singular value σ_i.
• Role: Enforces low-rank structure iteratively during optimization.

Matrix sensing is a related problem where the goal is to recover a low-rank matrix from linear measurements, often of the form y_i = ⟨A_i, X⟩. While matrix completion deals with direct observations of random entries, sensing uses general linear operators. Both rely on the low-rank prior and nuclear norm minimization, but sensing theory often requires the measurement operators to satisfy the Restricted Isometry Property (RIP).

Robust Principal Component Analysis (Robust PCA) decomposes an observed matrix M into a low-rank component L and a sparse component S (M = L + S). This separates the structured signal (low-rank) from corruptions or outliers (sparse). It shares the nuclear norm minimization framework with matrix completion but adds an L1-norm penalty on S to induce sparsity.

• Application: Video background subtraction, anomaly detection.
• Algorithm: Often solved via Principal Component Pursuit.

Alternating Least Squares (ALS) is a fundamental optimization algorithm for factorized models. For matrix completion, if the target matrix X is represented as a product UV^T, ALS alternates between:

1. Fixing V and solving for U via least squares on observed entries.
2. Fixing U and solving for V similarly.

• Advantage: Avoids SVD computations on large matrices.
• Use Case: Basis for many collaborative filtering implementations (e.g., classic Netflix Prize).

The Eckart–Young theorem is the foundational mathematical result for low-rank approximation. It states that for a given matrix A and target rank k, the optimal rank-k approximation under the Frobenius norm (or spectral norm) is obtained by taking the Truncated SVD—keeping only the k largest singular values and their corresponding vectors.

• Significance: Justifies the use of SVD for compression and denoising.
• Limitation: Assumes full matrix is known; completion deals with missing entries.