Fixed-rank matrix factorizations and Riemannian low-rank optimization

1 Introduction

• Scalability matters because growing datasets demand algorithms that can handle large matrices.Source: §1 · p. 2
• The framework treats fixed-rank non-symmetric matrix learning as smooth optimization on a Riemannian manifold in bijection with the matrix search space.The rank is of particular interest when it is much smaller than the matrix dimensions.Source: §1 · p. 2
• The product-space construction supports systematic geometric derivations and flexibility in choosing the metric.The paper develops first- and second-order optimization ingredients and details two algorithms used in its numerical tests.Source: §1 · p. 2
• The paper emphasizes a common Riemannian optimization framework, with the subspace-projection factorization as a new application of that framework.It also classifies existing algorithms by geometry and connects their common structure.Source: §1 · p. 2

2 Motivation and applications

• Modern machine-learning applications are cast as optimization problems over fixed-rank non-symmetric matrices.Source: §2 · p. 3

2.1 Low-rank matrix completion

• Fixed-rank matrix completion estimates missing entries from observed entries, with the rank constraint tying known and unknown values together.The number of observations can be O(d1r+d2r−r^2), much smaller than d1d2 when r is small relative to the dimensions.Source: §2.1 · p. 3

2.2 Learning on data pairs

• Learning on data pairs uses a low-rank bilinear predictor x^T Wz to map two types of samples to a scalar observation.Applications include bipartite or directed-graph edge inference and image-domain adaptation; the rank constraint may address high-dimensional features and reduce dimensionality in both domains.Source: §2.2 · pp. 3–4

2.3 Multivariate linear regression

• Multivariate linear regression can seek a low-rank coefficient matrix when related responses can be represented with fewer coefficients.The illustrated quadratic loss is not required; the setup also extends to other smooth loss functions.Source: §2.3 · p. 4

3 Matrix factorization and quotient spaces

• Three popular factorizations parameterize fixed-rank matrices and lead to search spaces with quotient geometry.They arise from the thin singular value decomposition.Source: §3 · p. 4

3.1 Full-rank factorization (beyond Cholesky-type decomposition)

• Full-rank factorization is non-unique because an invertible change of coordinates leaves the represented matrix unchanged.The framework encodes this invariance through equivalence classes rather than imposing triangular structure as in Cholesky- or LU-type remedies.Source: §3.1 · p. 5, Figure 1 · p. 5

3.2 Polar factorization (beyond SVD)

• Polar factorization uses a symmetric positive-definite middle factor, allowing more flexibility than a diagonal factor and removing singular-value ordering symmetries.Its factors are equivalent under a shared orthogonal transformation.Source: §3.2 · p. 6

3.3 Subspace-projection factorization (beyond QR decomposition)

• Subspace-projection factorization represents the column subspace with U and the projection or coefficient matrix with Y, with orthogonal transformations defining equivalent representations.The resulting search space is the quotient by the orthogonal group.Source: §3.3 · p. 6, Figure 2 · p. 7

4 Fixed-rank matrix spaces as Riemannian submersions

• The framework supplies matrix representations of the geometric operations needed to optimize on the quotient spaces; the corresponding geometric notions for subspace-projection factorization are new here.The other factorizations are full-rank and polar factorization.Source: §4 · p. 7

4.1 Quotient manifold representation

• The three factorization spaces become smooth quotient manifolds through the actions of GL(r) and O(r).The actions encode the equivalence relationships between factor representations.Source: §4 · p. 7, §4.1 · p. 8, Table 1 · p. 8

4.2 Tangent vector representation as horizontal lifts

• Vertical directions lie along an equivalence class, while their horizontal complement represents tangent vectors on the quotient manifold.The table gives matrix representations of these tangent-space components.Source: §4.2 · p. 9, Table 2 · p. 9
• The metric and horizontal distribution give each quotient tangent vector a unique horizontal lift in the total space.The total-space metric induces a valid Riemannian metric on the quotient.Source: §4.2 · pp. 9, 11

4.3 Retractions from the Tangent Space to the Manifold

• Retractions approximate geodesic updates, and the factorization-specific matrix computations are linear in dimensions d1 and d2.The product structure combines retractions on the component manifolds.Source: §4.3 · p. 11

4.4 Gradient and Hessian in Riemannian Submersions

• The quotient gradient and Hessian are represented through horizontal lifts, with the Hessian defined using the Riemannian connection.Table 5 gives the corresponding matrix expressions.Source: §4.4 · pp. 12, 14, Table 5 · p. 13

5.1 Gradient descent algorithm

• Gradient descent follows the negative Riemannian gradient and uses Armijo backtracking; its adaptive initial step-size heuristic aims to keep average line searches near one when optimal step-sizes vary little.The heuristic uses the previous iteration's initial and accepted step-sizes and backtracking count.Source: §5.1 · pp. 14–15

5.2 Riemannian trust-region algorithm

• The Riemannian trust-region method minimizes a locally quadratic model and uses truncated conjugate gradients without inverting the Hessian.With θ = 1, the method seeks quadratic convergence near the minimum.Source: §5.2 · pp. 15–16

5.3 Numerical complexity

• Geometry-related operations are linear in d1 and d2 and cubic or quadratic in rank r, making them efficient when r ≪ min(d1, d2).Cost-function and derivative evaluations remain problem-dependent.Source: §5.3 · pp. 16–17

6.1 Matrix completion as a benchmark for numerical comparisons

• The benchmark is low-rank matrix completion: recover a rank-r matrix from a sparse subset of its entries, comparing Riemannian methods with available algorithms.The experiments use five random instances of a 32000 × 32000 rank-5 matrix with oversampling ratio 8, revealing 0.25% of entries.Source: §6.1 · pp. 17, 18, 20, §6 · p. 17

6.2 Full-rank factorization W = GHT, MMMF, and LMaFit

• For full-rank factorization, trust-region convergence is better asymptotically than gradient descent or MMMF, while LMaFit reaches its 200-iteration limit.MMMF and the proposed gradient descent perform similarly; trust-region has a slow start but later converges better in iterations and computational complexity.Source: §6.2 · p. 22, Figure 4 · p. 22

6.3 Polar factorization W = UBVT and SVP

• For polar factorization, the proposed framework competes with SVP, and trust-region performs better asymptotically on the large-scale benchmark.Constraining B to be diagonal generally harms convergence; the scale-invariant metric avoids the factor-weight imbalance issue observed with MMMF. The authors could not compare OptSpace on large-scale instances because of unoptimized MATLAB operations in its supplied code.Source: §6.2 · p. 21, §6.3 · pp. 23–24, Figure 6 · p. 24

6.4 Subspace-projection factorization W = UYT and RTRMC

• For subspace-projection factorization, the proposed method compares favorably with RTRMC on square problems, with similar asymptotic trust-region performance and better gradient-descent timing.The proposed scale-invariant metric also prevents numerical ill-conditioning from unbalanced U and Y factors, whereas the Euclidean-metric algorithm converges very slowly.Source: §6.4 · pp. 25–26, Figure 7 · p. 25, Figure 8 · p. 26

6.5 Quotient and embedded viewpoints

• On the reported completion benchmark, quotient and embedded geometries have indistinguishable gradient-descent behavior and similar trust-region behavior.The embedded view offers straightforward geometric interpretations and a linearized step-size guess; the quotient product-space view offers flexibility in metric choice and factor regularization.Source: Figure 9 · p. 28, §6.5 · p. 28
• On 5 random instances, Riemannian quotient algorithms are competitive with LRGeom, with quotient trust-region schemes matching LRGeom RTR asymptotically.LRGeom RTR performs better during the initial phase, while quotient trust-region schemes spend more time transitioning to rapid convergence.Source: §6.5 · p. 28
• The gradient-descent schemes have inseparable behaviors in the comparison with LRGeom.Parameters were set by a linearized search; LRGeom used the step-size search proposed in.Source: §6.5 · p. 28

• All involved matrix-operation costs are linear in the original dimensions, making the computational framework amenable to large-scale applications.Source: §7 · p. 29
• Factorization choices matter: allowing B to be positive definite rather than diagonal yields good convergence, and balancing GHT updates is advantageous.Source: §7 · p. 29
• On low-rank matrix completion, the framework compares favorably with most state-of-the-art algorithms while maintaining complete generality.Source: §7 · p. 29
• The three geometries perform comparably on simple examples, but differing metrics and invariances let users choose for a problem; their numerical complexity and convergence guarantees are equivalent.Source: §7 · p. 29
• Optimizing geometry and metric for particular problems and datasets is left for future research.Source: §7 · p. 29