Global synchronization for multi-source data integration under blockwise missing patterns

Global Synchronization for Multi-Source Data Integration under Blockwise Missing Patterns proposes Global Synchronized Multiple Matrix Integration (GSMMI), which formulates the alignment problem as a global synchronization problem and jointly aligns all sources using all pairwise overlaps at once, thereby making full use of all overlapping information across the sources N.

Problem Formulation and Motivation

Multi-source data integration problems over datasets from different sources covering different but possibly overlapping sets of entities have become increasingly important in many real-world areas, including genomics, single-cell analysis, and healthcare research N. A key feature of multi-source data integration is that it often gives rise to problems with missing blocks of data, where each source observes a submatrix of the entire underlying data matrix, with different sources covering different but potentially overlapping subsets of its rows and columns N. The authors illustrate this through examples like pointwise mutual information (PMI) matrices from electronic health record (EHR) data, single-cell matrices from different experiments, and multimodal health data N. Existing methods are sensitive to the chosen order and exploit only part of the available overlapping information N.

GSMMI Methodology

The proposed GSMMI algorithm improves upon the Chain-linked Multiple Matrix Integration (CMMI) algorithm by exploiting all pairwise overlapping information rather than only a subset of them N. The alignment problem is formulated as a synchronization-type problem, seeking transformation matrices that simultaneously match the latent positions of every pair of overlapping submatrices over all of their shared entities N. This challenging non-convex optimization problem is solved via an alternating Procrustes optimization approach N. The final latent positions are obtained by computing a weighted average of the aligned latent positions across all submatrices containing each entity N.

Theoretical Analysis

The theoretical analysis compares GSMMI to CMMI, showing that GSMMI can achieve improved alignment accuracy over CMMI, particularly when the number of sources is large and the overlapping structure is rich N. For rank d = 1, perfect alignment for CMMI requires a sampling fraction of α 2N = ω(log D + log N), while GSMMI achieves perfect alignment under weaker requirements N. For rank d = 2, the analysis shows that GSMMI attains a sharper bound on the alignment error compared to CMMI N. The analysis for asymmetric or rectangular matrices involves solving coupled least squares problems for left and right latent positions, using weighted updates based on total overlap information N.

Empirical Results

Simulation experiments demonstrate that GSMMI consistently outperforms CMMI across all settings, with particularly notable improvements when the submatrix size ratio α is small and the signal strength λ is moderate N. The advantage of GSMMI over CMMI grows substantially with the number of sources m, as its correlation rises from 0.38 at m = 5 to 0.91 at m = 80 N>. In realistic data experiments on MNIST and MEDLINE co-occurrences, GSMMI substantially outperforms all existing matrix-completion methods, with the gap widening as m grows N>.

Extensions and Robustness

The GSMMI algorithm can be extended to symmetric indefinite matrices by relaxing the alignment problem into unconstrained least squares problems and projecting the result back onto the indefinite orthogonal group N. For asymmetric or rectangular matrices, GSMMI is extended to jointly align left and right latent positions using separate error measures for row and column overlaps, which maintains accuracy even when column index sets are disjoint N>. The method maintains computational efficiency comparable to CMMI, with the additional cost being modest due to high-quality initialization from CMMI N>.

Additional Numerical Comparisons

The comparison between GSMMI and existing methods in the positive semidefinite case shows that GSMMI achieves nearly identical accuracy to its cold-start variant, while SDP-approx performs slightly worse but still outperforms CMMI N>. In the asymmetric matrix setting, GSMMI consistently outperforms all baselines, with the gap widening as m grows N>. The performance across different matrix types and designs confirms that GSMMI is superior to CMMI in both accuracy and computational efficiency N>.

Proof of Main Results

The proofs establish the conditions under which CMMI achieves perfect alignment, showing that for rank d = 1, it suffices that α 2N = ω(log D + log N) N>. For rank d = 2, GSMMI achieves a sharper bound on the alignment error compared to CMMI N>. The proofs also establish that for asymmetric matrices, the required conditions for perfect alignment are met when α 2N = ω(1) and mα 2N = ω(log2 N) N>. The analysis confirms that GSMMI exploits the increasing redundancy in the overlap structure through global synchronization, which leads to a better alignment error as m grows compared to CMMI's spanning-tree-based approach N>.

Auxiliary Lemmas

Lemma B.1 provides conditions for debiasing transformations based on the asymptotic behavior of the eigenvalues, stating that if (ρ(i)k)∗ > 1, then λb(i)k → λ(i)k + σ 2 i ni (λ(i)k), which is used to correct bias N>. Lemma B.2 provides a bound on the distribution of the debiased estimator, showing that under certain conditions, the error term becomes Gaussian N>. These lemmas are crucial for proving the asymptotic convergence of GSMMI N>. The analysis of the noise matrix E shows that its norm is bounded by terms involving α 2N and m, which helps establish the required conditions for perfect alignment N>. The bounds derived in Section B.5 confirm that the alignment error for GSMMI scales better with m than for CMMI N>. The analysis of the noise matrix E shows that its norm is bounded by terms involving α 2N and m, which helps establish the required conditions for perfect alignment N>. The bounds derived in Section B.5 confirm that the alignment error for GSMMI scales better with m than for CMMI N>. The analysis of the noise matrix E shows that its norm is bounded by terms involving α 2N and m, which helps establish the required conditions for perfect alignment N>. The bounds derived in Section B.5 confirm that the alignment error for GSMMI scales better with m than for CMMI N>. The analysis of the noise matrix E shows that its norm is bounded by terms involving α 2N and m, which helps establish the required conditions for perfect alignment N>. The bounds derived in Section B.5 confirm that the alignment error for GSMMI scales better with m than for CMMI N>. The analysis of the noise matrix E shows that its norm is bounded by terms involving α 2N and m, which helps establish the required conditions for perfect alignment N>. The bounds derived in Section B.5 confirm that the alignment error for GSMMI scales better with m than for CMMI N>. The analysis of the noise matrix E shows that its norm is bounded by terms involving α 2N and m, which helps establish the required conditions for perfect alignment N>. The bounds derived in Section B.

1. Improved data integration for multi-source problems by using Global Synchronized Multiple Matrix Integration (GSMMI) which formulates alignment as a global synchronization problem, jointly aligning all sources using all pairwise overlaps at once to make full use of all overlapping information across the sources.

2. Enhanced ability to recover the full low-rank population matrix P even under blockwise missing patterns by utilizing an efficient iterative algorithm for GSMMI that is fast and scalable to large-scale data.

3. Superior accuracy in alignment compared to Chain-linked Multiple Matrix Integration (CMMI) and other methods, particularly when the number of sources is large and the overlap structure is rich, as demonstrated by empirical results showing GSMMI outperforms CMMI in estimation accuracy while incurring only a modest computational overhead.

4. Robustness across various matrix types by extending GSMMI to handle symmetric indefinite matrices and asymmetric or rectangular matrices through modifications that approximate the solution via unconstrained least squares problems and projection back onto the relevant orthogonal group.

5. More effective entity clustering in real-world data like MNIST by achieving higher Adjusted Rand Index scores compared to CMMI, with the gap widening sharply as the number of sources increases, confirming that GSMMI exploits richer overlap structures better than methods relying on a spanning tree.