Graph-Based Correlation Matrix Generation: A Convex Optimization Approach
Authors: Ali Fakhar, K{é}vin Polisano, Ir{è}ne Gannaz, Sophie Achard
Organizations: UGA · Univ. Grenoble Alpes, CNRS, Grenoble INP, Inria, LJK, F-38000 Grenoble, France · G-SCOP\_GROG, G-SCOP, Grenoble INP, UGA · Univ. Grenoble Alpes, CNRS, Grenoble INP, G-SCOP, 38000 Grenoble, France · STATIFY, LJK, UGA
Abstract
This work addresses the generation of theoretical correlation matrices with prescribed sparsity patterns associated to graph structures. We propose a novel convex optimization framework in which an initial matrix is projected onto an elliptope under a positive semidefiniteness constraint. Several numerical schemes are implemented and compared. The problem falls within the broader class of matrix completion, where off-diagonal entries corresponding to absent edges are fixed to zero and diagonal entries are fixed to one. Beyond this structural constraint, the approach offers greater flexibility than existing methods by allowing control over the mean of the off-diagonal entry distribution, enabling the generation of correlation matrices that better reflect realistic data. This procedure is not designed to yield a uniform distribution over the feasible set; rather, it provides a principled and tunable way to construct correlation matrices suitable for benchmarking statistical methods for graphical model inference. Theoretical guarantees on the existence of solutions are established, both in the general setting and under the additional mean constraint. Simulation studies illustrate the properties of the generated matrices with respect to graph structure. The methodology is applied to two real-world datasets from neuroscience and finance, and a comparison with GAN-based correlation matrix generation is provided.
We address the low-rank matrix completion problem by incorporating graph regularization into the existing Riemannian Trust-Region Matrix Completion (RTRMC) framework. The latter uses the geometry of the low-rank constraint to remodel the problem as an unconstrained optimization problem on a single Grassmann manifold. Our approach, named Graph-Regularized RTRMC (GR-RTRMC), exploits the inherent relationships between rows and columns of the matrix. By using these relationships, we aim to improve the accuracy and robustness of matrix completion, particularly in scenarios where the underlying data exhibits strong correlations between rows or columns.
We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an n×n matrix of rank r with incoherence parameter μ and condition number κ, the two methods achieve exact recovery with high probability from O(μnrlognlog(nκ)) and O(μnrlognlog(2μrκ)) observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.
We study the graph alignment problem for correlated Gaussian Orthogonal Ensemble (GOE) matrices, where the goal is to recover a hidden vertex permutation given two correlated symmetric Gaussian matrices (A,B) with correlation 1/1+σ2. While the maximum likelihood estimator is information-theoretically optimal, its computation, which reduces to a quadratic assignment problem, is intractable. Motivated by this, we analyze convex relaxations based on minimizing ∥AX−XB∥F over the set of doubly stochastic matrices and the unit hypercube. We show that when the correlation parameter satisfies σ=o(n−1/2/log4n), the solution of either relaxation (X⋆) concentrates around the ground-truth permutation matrix (Π⋆), i.e., ∥X⋆−Π⋆∥F2=o(n), implying recovery of all but a vanishing fraction of vertices after simple post-processing. Combined with existing lower bounds, our results precisely characterize that ∥X⋆−Π⋆∥F2 transitions from o(n) for σ=o~(n−1/2) to Ω(n) for σ=Ω~(n−1/2). In doing so, our analysis significantly tightens prior results and extends them beyond doubly stochastic relaxations.
Laurent Massoulié, Sushil Mahavir Varma, Louis Vassaux +1