Technical Summary: Bayesian Matrix Completion Under Geometric Constraints

1. Problem Statement

The paper addresses the challenge of Euclidean Distance Matrix (EDM) completion, a specific instance of matrix completion where the goal is to infer missing entries in a matrix representing squared pairwise distances between points in a low-dimensional space. This problem is fundamental to applications such as sensor network localization, acoustic room reconstruction, and molecular conformation.

The core difficulty lies in the fact that EDM completion is an ill-posed problem when observations are sparse and noisy. While traditional methods (e.g., rank-constrained optimization, semidefinite programming) enforce geometric constraints, they often rely on manual regularization parameters and produce only point estimates, failing to quantify the uncertainty of the recovered distances. Furthermore, existing probabilistic approaches often struggle to explicitly capture the non-linear geometric constraints inherent to EDMs without compromising tractability.

2. Methodology

The authors propose a hierarchical Bayesian framework (BMC-GC) that models the EDM completion problem by placing structured priors directly on the latent point set $P$ that generates the distance matrix, rather than on the matrix entries themselves.

2.1. Generative Model

The EDM $D$ is defined by a latent point set $P \in \mathbb{R}^{n \times d}$, where $D_{ij} = \|P_i - P_j\|^2$. The observation model assumes that a subset of entries $\Omega$ is observed with additive white Gaussian noise:
$$D_{ij} = \|P_i - P_j\|^2 + \epsilon_{ij}, \quad \epsilon_{ij} \sim \mathcal{N}(0, \sigma^2)$$

2.2. Prior Structures

The paper explores two prior formulations:

1. Gaussian Prior: An independent zero-mean Gaussian prior on each point $P_i$. Maximizing the posterior (MAP) under this prior is shown to be equivalent to the nuclear norm minimization approach for EDMs, establishing a probabilistic link to convex optimization. However, this approach requires manual tuning of the regularization parameter.
2. Hierarchical Gaussian Prior: To enable automatic regularization and uncertainty quantification, the authors introduce a hierarchical structure where the latent points are drawn from a Gaussian distribution with unknown mean $u_p$ and precision matrix $\Delta_p$. A conjugate Normal-Wishart hyperprior is placed on these hyperparameters. This allows the model to learn the level of regularization and noise precision ($\alpha = \sigma^{-2}$) directly from the data.

2.3. Posterior Inference

Due to the non-linear relationship between the latent points $P$ and the observed distances $D$, the joint posterior distribution is analytically intractable. The authors employ a Markov Chain Monte Carlo (MCMC) approach using a Metropolis-Hastings within Gibbs sampler:

• Gibbs Steps: The hyperparameters ($u_p, \Delta_p$) and the noise precision ($\alpha$) are sampled exactly because of the conjugacy of the Normal-Wishart and Gamma priors.
• Metropolis-Hastings (MH) Step: The conditional posterior for the latent points $P$ is non-standard (non-Gaussian) due to the quadratic distance term. Therefore, an MH step is used to propose and accept/reject new positions for each point $P_i$.

The final estimate of the EDM is obtained by averaging samples from the posterior distribution after a burn-in period.

3. Key Contributions

The paper outlines three primary contributions:

1. Bayesian Formulation: A probabilistic framework for EDM completion that incorporates Euclidean geometric constraints, explicitly linking the problem to nuclear norm minimization via a Gaussian prior assumption.
2. Hierarchical Modeling: The introduction of a hierarchical model with Normal-Wishart priors that enables adaptive regularization. This removes the need for manual selection of regularization parameters and allows the model to infer noise levels.
3. Inference Algorithm: A tailored Metropolis-Hastings within Gibbs sampler designed to handle the coupled latent point posterior and the non-linear geometric constraints, providing a full posterior distribution rather than a single point estimate.

4. Experimental Results

The authors evaluated BMC-GC against deterministic baselines (OptSpace, Alternating Descent, and Augmented Lagrangian) using synthetic data with varying sparsity and noise levels.

• Sparse Regimes: In scenarios with high sparsity (low fraction of observed entries) and noisy data, BMC-GC demonstrated improved reconstruction accuracy compared to deterministic baselines. The performance gain is attributed to the adaptive regularization provided by the hierarchical priors.
• Convergence: The sampler showed convergence in relative reconstruction error over MCMC iterations. Convergence was observed to occur earlier with larger numbers of available entries, though the final error level remained dependent on the Signal-to-Noise Ratio (SNR).
• Uncertainty Quantification: The method successfully generated posterior distributions for missing entries. In noiseless, high-sparsity scenarios, the posterior mean closely matched true values, and the distribution width provided a meaningful quantification of reconstruction uncertainty.
• Noiseless vs. Noisy: In noiseless setups with high sparsity, BMC-GC outperformed deterministic methods. However, as the number of observed entries increased, deterministic methods became increasingly effective, suggesting the Bayesian approach is particularly valuable when data is scarce or noisy.

5. Significance and Claims

The paper claims that its primary significance lies in addressing the limitations of traditional EDM completion methods:

• Robustness: By integrating out hyperparameters, the model avoids the inflexibility of manual regularization, making it more robust to sparse and noisy conditions.
• Uncertainty Quantification: Unlike methods that produce a single point estimate, the Bayesian framework provides a full posterior distribution, allowing users to assess the confidence in recovered distances—a critical feature for scientific and signal processing applications.
• Geometric Validity: By modeling the generation process from latent points directly, the approach naturally embeds geometric constraints, ensuring the recovered matrix is a valid EDM.

The authors conclude that the proposed hierarchical Bayesian framework is an effective tool for EDM denoising and completion, particularly in regimes where data is highly incomplete.