  We propose two novel extensions of the Wyner common information optimization
problem. Each relaxes one fundamental constraints in Wyner's formulation. The
\textit{Variational Wyner Common Information} relaxes the matching constraint
to the known distribution while imposing conditional independence to the
feasible solution set. We derive a tight surrogate upper bound of the obtained
unconstrained Lagrangian via the theory of variational inference, which can be
minimized efficiently. Our solver caters to problems where conditional
independence holds with significantly reduced computation complexity; On the
other hand, the \textit{Bipartite Wyner Common Information} relaxes the
conditional independence constraint whereas the matching condition is enforced
on the feasible set. By leveraging the difference-of-convex structure of the
formulated optimization problem, we show that our solver is resilient to
conditional dependent sources. Both solvers are provably convergent (local
stationary points), and empirically, they obtain more accurate solutions to
Wyner's formulation with substantially less runtime. Moreover, them can be
extended to unknown distribution settings by parameterizing the common
randomness as a member of the exponential family of distributions. Our
approaches apply to multi-modal clustering problems, where multiple modalities
of observations come from the same cluster. Empirically, our solvers outperform
the state-of-the-art multi-modal clustering algorithms with significantly
improved performance.
