Technical Summary: Data Denoising with Self-Consistency, Variance Maximization, and the Kantorovich Dominance

1. Problem Formulation

The paper addresses the fundamental problem of data denoising (or dimensional reduction), defined as inferring an unknown true signal distribution $\mu$ from an observed noisy distribution $\nu$. The authors assume the signal belongs to a structured domain $\mathcal{D}$ of Borel probability measures.

Existing approaches generally fall into two categories:

1. Distance Minimization: Finding $\mu \in \mathcal{D}$ closest to $\nu$ in the Wasserstein metric ($W_2$). This corresponds to a "relaxed" problem (e.g., $k$-means, principal curves).
2. Self-Consistency: Finding $\mu \in \mathcal{D}$ such that the conditional expectation of the noise vanishes (i.e., $\mathbb{E}[Y|X]=X$ for a coupling between $\mu$ and $\nu$). This is equivalent to requiring a martingale coupling, or that $\mu$ is dominated by $\nu$ in the convex order ($\mu \preceq_C \nu$).

The authors identify a gap: while self-consistency is a desirable property (arising as a first-order optimality condition for distance minimization in simple cases), solutions derived solely from self-consistency do not generally minimize the distance to the data. Conversely, distance minimization does not enforce self-consistency. The paper proposes a unified framework that seeks the distribution $\mu \in \mathcal{D}$ which is closest to $\nu$ while simultaneously satisfying self-consistency.

2. Methodology

2.1 The Convex Order Framework

The authors formulate the denoising problem as:
$$\min_{\mu \in \mathcal{D}} \min_{\pi \in \mathcal{M}(\mu, \nu)} \int |x-y|^2 d\pi(x,y)$$
where $\mathcal{M}(\mu, \nu)$ is the set of martingale couplings. By Strassen's theorem, a martingale coupling exists if and only if $\mu \preceq_C \nu$. Since the Wasserstein distance under martingale constraints simplifies to the difference in variances ($\text{Var}(\nu) - \text{Var}(\mu)$), the problem is equivalent to maximizing the variance of $\mu$ within the domain $\mathcal{D}$ subject to the convex order constraint:
$$\max_{\mu \in \mathcal{D}, \mu \preceq_C \nu} \text{Var}(\mu)$$

Key Properties of the Convex Order Problem:

• Existence: Solutions exist for closed domains $\mathcal{D}$ where the intersection with the convex order set is non-empty.
• Robustness: If the noise is small (i.e., $\nu$ is close to a true signal $\rho \in \mathcal{D}$ with $\rho \preceq_C \nu$), the solution $\mu^*$ is quantifiably close to $\rho$.
• Limitations:
  • Computational Difficulty: Checking the convex order condition $\mu \preceq_C \nu$ is non-trivial.
  • Instability: The solution can be unstable with respect to perturbations in the data $\nu$.
  • Triviality: For certain domains, the set $\{\mu \in \mathcal{D} \mid \mu \preceq_C \nu\}$ may be empty or contain only trivial solutions (e.g., Dirac masses), rendering the problem uninformative.

2.2 The Kantorovich Dominance Relation (KDR)

To address the limitations of the convex order, the authors introduce a weaker relation called Kantorovich Dominance ($\mu \preceq_K \nu$).
$\mu \preceq_K \nu$ if there exists a coupling $\pi \in \Pi(\mu, \nu)$ such that:
$$\int \langle x - b_\nu, y - x \rangle d\pi(x,y) = 0$$
where $b_\nu$ is the barycenter of $\nu$. Assuming centered measures, this is equivalent to:
$$\sup_{\pi \in \Pi(\mu, \nu)} \int \langle x, y \rangle d\pi(x,y) \geq \int |x|^2 d\mu(x)$$
This condition implies that the "Kantorovich cost" (maximal correlation) dominates the second moment of $\mu$.

Properties of KDR:

• Relaxation: It is a relaxation of the convex order ($\mu \preceq_C \nu \implies \mu \preceq_K \nu$).
• Optimality Condition: For a class of domains called cones (closed under scaling), the KDR condition arises naturally as an optimality condition for the relaxed distance minimization problem.
• Stability: Unlike the convex order problem, the KDR-based denoising problem is stable with respect to perturbations in the data $\nu$.
• Compactness: While the set of measures dominated by $\nu$ in convex order is compact, the set under KDR is not necessarily compact in the $W_2$ metric unless restricted to a compact support $\Omega$.

2.3 The KDR Variational Problem

The authors propose the following denoising problem using KDR:
$$\max_{\mu \in \mathcal{D} \cap \mathcal{M}^K_{\nu, \Omega}} \text{Var}(\mu)$$
where $\mathcal{M}^K_{\nu, \Omega}$ is the set of measures in a compact set $\Omega$ dominated by $\nu$ in KDR.

Key Theoretical Results:

1. Equivalence for Cones: If $\mathcal{D}$ is a cone and translation invariant (or contained in centered measures), the KDR problem is equivalent to the fully relaxed Wasserstein distance minimization problem ($\min_{\mu \in \mathcal{D}} W_2^2(\mu, \nu)$).
2. Equivalence for Weak Optimizers: If $\mathcal{D}$ is closed under "weak optimizers" (a condition related to barycentric recentering), the KDR solution satisfies the full self-consistency condition ($\mu \preceq_C \nu$).
3. Recovery of PCA: When $\mathcal{D}$ is the set of measures supported on $m$-dimensional subspaces, the KDR problem recovers Principal Component Analysis (PCA). Crucially, unlike the convex order formulation, the KDR formulation allows for non-trivial solutions even when the data is discrete (e.g., empirical measures), where the convex order constraint would force the solution to be a Dirac mass.

3. Key Contributions

1. Unified Framework: The paper introduces a framework that unifies distance minimization and self-consistency by formulating denoising as a variance maximization problem under a distributional dominance constraint.
2. Kantorovich Dominance: The introduction of a new, weaker dominance relation that retains the spirit of martingale couplings (self-consistency) but offers superior computational tractability and stability.
3. Theoretical Guarantees: Proof of existence, robustness, and stability for the proposed problems. The paper demonstrates that for specific domains (cones), the complex self-consistency requirement collapses to standard distance minimization, while for others, it provides a meaningful intermediate solution.
4. Connection to Classical Methods: The authors rigorously show how Principal Component Analysis (PCA), $k$-means clustering, and principal curves emerge as special cases of their framework under appropriate domain choices.

4. Numerical Results

The authors provide numerical examples solving the KDR problem using a generalized Lloyd algorithm and the Sinkhorn algorithm for efficient coupling computation.

• Principal Curves: The method successfully fits curves to noisy data, outperforming or matching existing principal curve definitions (Hastie-Stuetzle, Kegl et al., Tibshirani) in capturing underlying structures.
• Stability Comparison: Numerical experiments illustrate that while the self-consistency (convex order) solution can be unstable or fail to exist for discrete data, the KDR solution remains stable and informative.
• Scalability: The KDR approach allows for the processing of larger datasets (e.g., 5000 points) where the convex order formulation fails due to memory constraints or lack of feasible solutions.

5. Significance and Claims

The paper claims to provide a "general paradigm for data denoising" that captures key features of both distance minimization and self-consistency. Its primary significance lies in:

• Resolving Instability: It offers a stable alternative to the self-consistency approach, which is prone to instability and trivial solutions.
• Bridging Theory and Practice: By introducing Kantorovich dominance, the authors create a bridge between the theoretical elegance of martingale optimal transport and the practical requirements of denoising algorithms (computational efficiency and stability).
• Generalization of PCA: The work frames PCA not just as a linear projection, but as a specific instance of a broader variance maximization problem under distributional dominance, extending its applicability to non-linear and constrained settings.

The authors remain modest regarding the quantitative stability of the KDR solution, noting that while qualitative stability is proven, a quantitative version of the stability bound remains an open and challenging direction for future research.