💻 computer science

Riemannian Optimization for Hadamard Products of Low-Rank Matrices

This paper proposes a Riemannian optimization framework with a novel block-diagonal metric and a tuning-free Gauss-Newton algorithm to efficiently learn low-rank matrices under Hadamard products by addressing their inherent scaling symmetries.

Original authors: Pratik Jawanpuria, Ankish Chandresh, Bamdev Mishra

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pratik Jawanpuria, Ankish Chandresh, Bamdev Mishra

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

The Big Picture: A Two-Person Dance

Imagine you are trying to recreate a complex painting (a large data matrix) using only two simple, low-resolution sketches.

Sketch A captures the broad, general shapes.
Sketch B captures the fine, detailed textures.

The paper argues that the best way to recreate the painting isn't just to stack these sketches on top of each other. Instead, you should multiply them together, pixel by pixel (this is called the "Hadamard product"). This allows the model to be very efficient, using fewer "brushstrokes" (parameters) than a standard method would require.

However, there is a catch. Because you are multiplying two sketches, there are many ways to adjust the brightness of Sketch A and the contrast of Sketch B that result in the exact same final painting. It's like saying, "I can make the painting brighter by turning up the lights on Sketch A," or "I can make it brighter by turning down the lights on Sketch B." There are infinite combinations of these adjustments that lead to the same result.

This creates a confusing landscape for computers trying to learn the model. Standard computer methods get lost in these "infinite loops" of equivalent solutions, wasting time and energy.

The Problem: Getting Lost in the Fog

The authors point out that existing methods (like Alternating Gradient Descent or Block Coordinate Descent) struggle with this specific type of problem:

Standard methods treat the problem like walking on a flat, straight road. But the actual landscape is curved and bumpy. They take steps that are too small or in the wrong direction because they don't understand the shape of the terrain.
Specialized methods work great if the goal is just to minimize simple errors (like "squared error"), but they break down completely if you want to use more complex goals (like predicting user ratings or handling messy data). They are like a car that only works on a racetrack but stalls on a dirt road.

The Solution: A Smart Map (Riemannian Optimization)

The authors propose a new way to navigate this problem using Riemannian Optimization.

Think of the problem space not as a flat sheet of paper, but as a curved, folded surface (a manifold).

The "Folded" Nature: Because of the "infinite loops" mentioned earlier (the symmetry), many different points on the map actually represent the exact same painting.
The Quotient Manifold: The authors create a "quotient manifold." Imagine taking that folded surface and gluing all the points that represent the same painting together. Now, you have a clean, simplified map where every point is unique. You can't get lost in the "infinite loops" anymore because the loops have been glued shut.

The Secret Weapon: A Custom Compass (The Metric)

To walk efficiently on this curved surface, you need a special compass. In math, this is called a Riemannian Metric.

The authors invented a new, custom compass.

The Old Compass: Standard methods use a generic compass that assumes the ground is flat. It gets confused by the curves.
The New Compass: The authors' compass is "block-diagonal." Imagine a compass that has separate, independent sensors for every single row and column of your sketches. It knows exactly how the "texture" of one part of the sketch affects the "shape" of another.
The Magic: This compass is scale-invariant. If you decide to make Sketch A twice as bright and Sketch B half as bright, the compass doesn't care. It knows you haven't changed the painting, so it doesn't get confused. It ignores the "noise" of arbitrary scaling and focuses only on the actual shape of the data.

The Algorithm: The Tuning-Free Hiker

Using this new map and compass, the authors built a hiking algorithm called RGD (Riemannian Gradient Descent).

No Dial-Twisting: Most hiking algorithms require you to manually adjust a "step size" dial (tuning hyperparameters). If you turn it too much, you overshoot; too little, and you move too slow. This new algorithm calculates the perfect step size automatically using a "Gauss-Newton" trick. It's like a hiker who instinctively knows exactly how far to step based on the slope of the hill, requiring no manual adjustments.
Speed: It is incredibly fast. It scales linearly with the amount of data, meaning if you double the size of the painting, it only takes twice as long to paint it, not four times or ten times.

The Results: Winning the Race

The authors tested their hiker against the old methods on real-world data (like movie ratings from MovieLens and network maps).

Accuracy: On the MovieLens dataset (predicting movie ratings), their method achieved the lowest error rate (best accuracy) across all tested configurations. It found better solutions than the specialized "racetrack-only" methods.
Robustness: When they artificially messed up the starting conditions (making one sketch very bright and the other very dim), their method ignored the mess and found the correct answer every time. The old methods got confused and performed worse.
Versatility: Unlike the specialized methods that only work for simple math problems, this new method works for any smooth goal, making it a universal tool for this type of data.

Summary

The paper introduces a smarter way to teach computers how to learn from data that has a "multiplicative" structure. By realizing that the problem lives on a curved, folded surface and building a custom compass that ignores irrelevant scaling tricks, they created an algorithm that is faster, more accurate, and requires less human tuning than previous methods. It's like upgrading from a blindfolded walker to a hiker with a perfect, self-adjusting GPS.

Technical Summary: Riemannian Optimization for Hadamard Products of Low-Rank Matrices

Problem Formulation
The paper addresses the challenge of modeling data with multiplicative structure using the elementwise (Hadamard) product of two low-rank matrices. The target matrix $W \in \mathbb{R}^{m \times n}$ is modeled as:
$W = (GH^\top) \circ (UV^\top)$
where $G, U \in \mathbb{R}^{m \times r_1, r_2}$ and $H, V \in \mathbb{R}^{n \times r_1, r_2}$ . While this formulation offers parameter efficiency compared to a standard rank- $r_1r_2$ factorization (requiring $(m+n)(r_1+r_2)$ parameters versus $(m+n)r_1r_2$ ), it introduces a complex optimization landscape. Specifically, the model exhibits symmetries beyond standard General Linear (GL) reparameterization invariance. The product $W$ remains invariant under coupled row and column scalings between the two factor pairs $(G, H)$ and $(U, V)$ . These additional degrees of freedom create a challenging geometry that standard Euclidean gradient descent methods struggle to navigate efficiently.

Existing solvers face limitations: Alternating Gradient Descent (AGD) ignores the specific geometry and scaling symmetries, while Block Coordinate Descent (BCD) is highly effective for least-squares losses but lacks closed-form solutions for non-quadratic losses (e.g., logistic link prediction or cross-entropy), limiting its applicability in robust statistics and other domains.

Methodology
The authors propose formulating the learning problem as an optimization task on a Riemannian quotient manifold. This approach explicitly accounts for the natural invariances of the Hadamard product.

Manifold Geometry: The authors define the quotient manifold $\mathcal{M}$ by factoring out the full symmetry group $\mathcal{G}$ , which includes:
- Standard GL reparameterization invariance for each factor pair.
- Novel cross-Hadamard scaling symmetries, where invertible diagonal matrices scale rows and columns across the two factor pairs inversely.
  The manifold is constructed from the space of full-column-rank matrices modulo this group action.
Novel Riemannian Metric: A critical contribution is the derivation of a block-diagonal Riemannian metric ( $g_x$ ) derived from the pullback of the Frobenius inner product.
- The full pullback metric couples all four factor blocks, resulting in a dense and computationally expensive linear system.
- The proposed metric retains only the diagonal blocks of the pullback, discarding cross-terms.
- The metric is defined via weight matrices ( $S$ -blocks) for each row/column of the factors. For example, the weight for the $i$ -th row of $G$ is $S^G_i = H^\top \text{Diag}(Y^2_{i,:}) H$ , where $Y = UV^\top$ .
- Invariance: The metric is proven to be invariant under both the GL reparameterization and the cross-Hadamard scaling symmetries. This ensures the optimizer is insensitive to arbitrary magnitude splits between the factors.
- Connection to BCD: The weight matrices in the proposed metric correspond exactly to the normal-equation matrices used in BCD updates. Thus, the Riemannian gradient can be interpreted as performing a "soft" BCD step simultaneously on all rows for arbitrary smooth loss functions.
Optimization Algorithm (RGD): The authors develop a Riemannian Gradient Descent (RGD) algorithm:
- Gradient Computation: The Riemannian gradient is computed by solving independent $r \times r$ linear systems (one per row/column) using the $S$ -blocks.
- Step Size: A tuning-free Gauss–Newton Cauchy step size is derived. This step size is invariant under the symmetry group and requires no hyperparameter tuning.
- Retraction: An additive retraction is used to map updates back to the manifold.
- Complexity: The per-iteration cost scales linearly with the number of observed entries $N$ ($O(Nr)$) and polynomially with the ranks ( $O((m+n)r^4)$ ), making it efficient for large datasets.

Key Contributions

Geometric Characterization: Formal description of the quotient manifold structure for Hadamard products, identifying both GL and cross-Hadamard scaling symmetries.
Scale-Invariant Metric: Proposal of a novel block-diagonal Riemannian metric that respects the full symmetry group and decouples the optimization into independent row/column sub-problems.
Algorithm Development: Derivation of an RGD algorithm with a tuning-free Gauss–Newton step size that supports any smooth loss function, unlike BCD which is restricted to least squares.
Empirical Validation: Demonstration that the method achieves performance comparable to BCD on least-squares tasks while outperforming it on non-quadratic objectives and achieving superior results in specific Hadamard rank configurations.

Experimental Results
The authors evaluated RGD on synthetic and real-world datasets:

Synthetic Stress Tests: On $2,000 \times 1,000$ $2, 000 \times 1, 000$ synthetic targets, RGD demonstrated:
- Scale Invariance: Recovery error remained constant across varying diagonal scale separations ( $\kappa_{scale}$ ), empirically verifying the metric's invariance property. In contrast, AGD showed sensitivity to scaling.
- Conditioning: RGD performed comparably to BCD across varying factor condition numbers, significantly outperforming AGD.
- Noise Robustness: RGD converged to the noise floor at the same rate as BCD, whereas AGD lagged behind.
Real-World Datasets:
- Full Matrix Approximation: On Camera, Football, and Les Misérables datasets, RGD tracked BCD closely in relative error, confirming the metric provides BCD-equivalent preconditioning for quadratic losses.
- MovieLens-1M: In a matrix completion task with a fixed parameter budget ( $r_1+r_2=6$ ), RGD achieved the lowest Held-out RMSE across all tested Hadamard rank configurations. Notably, the balanced configuration $(3,3)$ outperformed the near-vanilla $(1,5)$ , suggesting that Hadamard interaction capacity ( $r_1r_2$ ) contributes to accuracy. RGD consistently outperformed AGD and achieved lower RMSE than BCD in genuinely Hadamard configurations.

Significance and Claims
The paper claims to bridge the gap between the efficiency of BCD for least-squares problems and the flexibility of gradient-based methods for general smooth losses. By elevating the problem to a Riemannian quotient manifold, the authors provide a principled framework that handles the complex symmetries of Hadamard products. The proposed RGD algorithm offers a tuning-free, scale-invariant optimization method that scales linearly with data size. The authors assert that this framework extends naturally to products of $k$ low-rank matrices and is compatible with other Riemannian solvers (e.g., conjugate gradients, trust-region methods), offering a robust alternative to existing solvers for multiplicative low-rank modeling.