🤖 machine learning

Graph-Regularized Low-Rank Matrix Completion by Variable Projection

This paper proposes Graph-Regularized RTRMC (GR-RTRMC), a novel matrix completion method that enhances the accuracy and robustness of the existing Riemannian Trust-Region framework by incorporating graph regularization to exploit inherent row and column correlations within the data.

Original authors: Benoît Loucheur, P. -A. Absil, Michel Journée

Published 2026-07-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Benoît Loucheur, P. -A. Absil, Michel Journée

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, colorful spreadsheet representing the weather across Belgium and France, or the movie ratings of thousands of people. Now, imagine someone took a giant eraser and wiped out huge chunks of this data. Maybe a sensor broke, or a user just forgot to rate a movie. Your goal? To guess what those missing numbers were without making things up.

This is the puzzle of Low-Rank Matrix Completion. The paper argues that the old way of solving this—treating every row and column as a lonely island—is like trying to guess the weather in Paris by looking at a thermometer in London without knowing they are neighbors. It ignores the fact that things are connected.

The authors, Benoît Loucheur, P.-A. Absil, and Michel Journée, propose a new method called Graph-Regularized Riemannian Trust-Region Matrix Completion (GR-RTRMC). Think of this as giving your guessing algorithm a "social network."

The "Social Network" Analogy

In the old methods, if you were trying to guess the temperature at a missing weather station, the computer would just look at the general trend of all stations. It didn't care if the station was right next to a forest or a city.

The new method, GR-RTRMC, builds a "friendship graph" first.

For weather: It draws invisible lines between weather stations that are close to each other. If Station A is friends with Station B, the computer assumes their temperatures should be similar.
For movies: It connects users who like similar movies and movies that are liked by similar people.

By using this map of connections, the algorithm doesn't just guess; it "smooths" its guesses. If a friend's temperature dropped, it's highly likely yours did too. This is called graph regularization.

The "Magic Trick" (The Math Part)

The paper explains that they didn't just add this graph to a standard calculator. They used a fancy mathematical playground called a Grassmann manifold.

Imagine trying to find the best path through a maze. Standard methods walk on flat ground, step by step. The authors' method, however, realizes that the maze is actually a curved surface, like the skin of a balloon. By rolling along the curve (using Riemannian optimization) instead of walking on flat ground, they can find the solution more efficiently and accurately. They call this the Variable Projection technique, which is like solving for one part of the puzzle perfectly before moving on to the next, rather than guessing both at once.

What They Found (The Results)

The team tested their idea on real data:

Weather in Belgium: They looked at 96 stations over four years. In a scenario where big blocks of time were missing (like a sensor going offline for a week), their method guessed the missing temperatures with an error of just 0.45°C. This was better than the previous best method, which had an error of 0.49°C.
Weather in France: They scaled this up to hundreds of stations. Again, their method won, guessing missing temps with an error of 0.54°C when data was scattered randomly, beating the competition.
Movie Ratings: They tried it on the MovieLens 100K dataset (943 users, 1682 movies). Their method predicted ratings with an error of 0.942, beating the next best method (GRALS) which had 0.951.

The Catch: The paper is honest about the cost. This "super-smart" method takes longer to run. On the Belgian data, it took 8.6 to 9.6 seconds, while the standard method took only 3.4 to 3.7 seconds. It's a trade-off: you wait a few extra seconds for a more accurate guess.

The "Oops" Moments (What the Paper Rules Out)

Here is where the paper gets very careful. It explicitly shows that their method isn't a magic wand for every situation.

They found that when a storm hit, the method sometimes went crazy. Because the storm moved across the country, one station might drop in temperature at 2:00 PM, while a station 50km away didn't drop until 4:00 PM. The "friendship graph" assumed they should move together, so the computer tried to force them to match, creating weird, wiggly lines that didn't make sense.

The paper argues that low-rank models alone cannot capture these sudden, localized shifts. If you rely only on the graph and the matrix math, you will get it wrong during extreme, fast-moving weather events. The authors suggest that to fix this, you would need to add more data (like rain or wind) or tell the computer to "trust" the data less during storms. They do not claim to have solved this storm problem yet; they just showed where their current method fails.

The Bottom Line

The paper suggests that adding a "social network" of connections to matrix completion makes it much better at filling in missing weather and movie data, especially when the data is messy or scattered. However, it admits that when nature gets chaotic (like a sudden, localized storm), the method can stumble because it assumes things are too smooth. It's a powerful tool, but it's not a crystal ball.

Technical Summary: Graph-Regularized Low-Rank Matrix Completion by Variable Projection

Problem Statement

The paper addresses the low-rank matrix completion problem, which arises in domains such as recommendation systems, weather forecasting, and network analysis where data is often incomplete due to missing measurements or transmission failures. The goal is to recover a complete target matrix $M \in \mathbb{R}^{m \times n}$ from a subset of observed entries $\Omega$ .

While classical approaches formulate this as a rank minimization problem (NP-hard) or a nuclear norm minimization (convex but computationally expensive for large matrices), factorized representations ($X = UW$) offer a more efficient alternative. However, standard factorization methods treat rows and columns independently, ignoring inherent structural relationships (e.g., spatial proximity in weather data or user similarity in recommendations). Existing graph-regularized methods often rely on alternating minimization schemes. The paper seeks to integrate graph-based structural information into a Riemannian Trust-Region Matrix Completion (RTRMC) framework, which operates on the geometry of low-rank constraints, to improve accuracy and robustness.

Methodology: GR-RTRMC

The authors propose Graph-Regularized Riemannian Trust-Region Matrix Completion (GR-RTRMC). This method extends the RTRMC framework by incorporating Dirichlet semi-norms to enforce smoothness along graph-encoded relationships between rows and columns.

1. Optimization Formulation

The core problem is formulated as a nested optimization over matrix factors $U \in \mathbb{R}^{m \times r}$ and $W \in \mathbb{R}^{r \times n}$ :
$\min_{U, W} \left\{ \frac{1}{2}\|C \odot (UW - M)\|_{\Omega}^2 + \frac{\lambda^2}{2} \|P_{\bar{\Omega}}(UW)\|_F^2 + \frac{\lambda_u}{2} \|U\|_{D,u}^2 + \frac{\lambda_w}{2} \|W\|_{D,w}^2 \right\}$
Where:

$C$ is a confidence matrix weighting observed entries.
$\|U\|_{D,u}^2 = \text{Tr}(U^T L_u U)$ and $\|W\|_{D,w}^2 = \text{Tr}(W L_w W^T)$ are the graph regularization terms using row ( $L_u$ ) and column ( $L_w$ ) Laplacians.
$\lambda, \lambda_u, \lambda_w$ are regularization parameters.

2. Variable Projection and Manifold Optimization

A key insight of the methodology is the use of variable projection. For a fixed $U$ , the optimal $W$ (denoted $W_U$ ) can be computed analytically as a regularized least-squares solution. Substituting $W_U$ back into the objective yields a reduced cost function $f(U)$ that depends only on the column space of $U$ .

Due to the invariance of the product $UW$ under basis changes of $U$ , the optimization is reformulated on the Grassmann manifold $\text{Gr}(m, r)$ , the set of $r$ -dimensional subspaces in $\mathbb{R}^m$ . In practice, this is implemented using orthonormal representations on the Stiefel manifold $\text{St}(m, r)$ .

3. Algorithmic Components

The paper provides a complete theoretical derivation for Riemannian optimization on this manifold:

Gradient Computation: The Euclidean gradient is derived using the envelope theorem, accounting for the dependency of $W_U$ on $U$ . The Riemannian gradient is obtained by projecting this onto the tangent space of the Grassmann manifold.
Hessian Computation: The authors derive the Riemannian Hessian, which involves computing the directional derivative of the optimal $W_U$ (denoted $W_{U,H}$ ). This requires solving a linear system involving a matrix $A$ that includes the graph Laplacian term $\lambda_w(L_w \otimes I_r)$ , introducing coupling between columns of $W$ that was absent in standard RTRMC.
Initialization: The algorithm initializes $U_0$ using the $r$ dominant left singular vectors of the observed data matrix $M_\Omega$ , computed efficiently via sparse SVD.

Key Contributions

Framework Extension: The paper extends the RTRMC framework by incorporating graph regularization terms (Dirichlet semi-norms) directly into the Riemannian optimization formulation.
Theoretical Development: It provides a complete derivation of the gradient and Hessian for the graph-regularized problem on the Grassmann manifold, including the computation of the derivative of the optimal right factor $W_U$ .
Algorithmic Implementation: The method solves the optimization problem using Riemannian trust-region algorithms, leveraging the variable projection technique to reduce the problem dimensionality.
Empirical Validation: The approach is validated on meteorological datasets (Belgium and France) and collaborative filtering datasets (MovieLens 100K and 1M).

Experimental Results

The authors evaluated GR-RTRMC against baselines including IDW, PCA, MissForest, LMaFiT, SoftImpute, RTRMC, and GRALS.

Weather Data (Belgium): In the "Block" missing data scenario (contiguous time intervals), GR-RTRMC achieved the lowest RMSE (0.45°C), outperforming RTRMC (0.49°C) and SoftImpute (0.53°C). In the "Spread" scenario, SoftImpute was slightly better (0.41°C vs 0.43°C), but GR-RTRMC remained competitive.
Weather Data (France): On a larger dataset (272–545 stations), GR-RTRMC consistently outperformed baselines in both Block (0.57°C) and Spread (0.54°C) scenarios, demonstrating that graph regularization scales effectively with larger spatial datasets.
MovieLens: GR-RTRMC achieved the best RMSE on both MovieLens 100K (0.942) and MovieLens 1M (0.913), surpassing GRALS and User-Based KNN.
Computational Cost: The method requires approximately 2–3 times more computation time than standard RTRMC due to the graph regularization terms, but remains practical for real-world applications where accuracy gains are prioritized.

Case Studies and Limitations

The paper includes detailed case analyses of failure modes:

Storm Events: During a convective storm, the model produced spurious oscillations because the low-rank assumption and spatial graph regularization could not capture the spatially heterogeneous timing of temperature drops across stations. The authors noted that reducing the confidence $C_{i,j}$ for entries during the anomalous period restored plausible imputation.
Localized Rain: In cases where nearby stations experienced vastly different precipitation (and thus temperature drops), the graph regularization forced the model to smooth over local anomalies, leading to inaccurate imputations for the affected station.

Significance and Claims

The paper claims that GR-RTRMC successfully leverages structural relationships between rows and columns to improve matrix completion accuracy, particularly in scenarios with strong correlations (e.g., spatial weather data). The authors emphasize that while the method improves upon standard RTRMC and other baselines, it is not a panacea; highly localized phenomena (like scattered precipitation) can violate the spatial coherence assumptions of low-rank models.

The authors modestly conclude that while their method demonstrates superior performance in standard scenarios, future work should focus on incorporating additional meteorological variables (precipitation, humidity) and developing mechanisms to automatically detect and down-weight anomalous periods to handle localized disturbances more robustly. The work extends a previous conference presentation by providing full theoretical development, larger-scale experiments, and detailed failure mode analysis.