Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-22T06:58:51.708Z Has data issue: false hasContentIssue false
  • English
  • Français

Quantum entropic regularization of matrix-valued optimal transport

Published online by Cambridge University Press:  28 September 2017

GABRIEL PEYRÉ ,
LÉNAÏC CHIZAT ,
FRANÇOIS-XAVIER VIALARD  and
JUSTIN SOLOMON
GABRIEL PEYRÉ
Affiliation:
CNRS and DMA, École Normale Supérieure, 45 rue d'Ulm - F 75230PARIScedex 05 email: [email protected]
LÉNAÏC CHIZAT
Affiliation:
Ceremade, Univ. Paris-Dauphine and INRIA Mokaplan, Place du Maréchal de Lattre de Tassigny, 75016 Paris email: [email protected], [email protected]
FRANÇOIS-XAVIER VIALARD
Affiliation:
Ceremade, Univ. Paris-Dauphine and INRIA Mokaplan, Place du Maréchal de Lattre de Tassigny, 75016 Paris email: [email protected], [email protected]
JUSTIN SOLOMON
Affiliation:
EECS and CSAIL, MIT, 32 Vassar Street, room 32-D460 Cambridge, MA 02139 email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This article introduces a new notion of optimal transport (OT) between tensor fields, which are measures whose values are positive semidefinite (PSD) matrices. This “quantum” formulation of optimal transport (Q-OT) corresponds to a relaxed version of the classical Kantorovich transport problem, where the fidelity between the input PSD-valued measures is captured using the geometry of the Von-Neumann quantum entropy. We propose a quantum-entropic regularization of the resulting convex optimization problem, which can be solved efficiently using an iterative scaling algorithm. This method is a generalization of the celebrated Sinkhorn algorithm to the quantum setting of PSD matrices. We extend this formulation and the quantum Sinkhorn algorithm to compute barycentres within a collection of input tensor fields. We illustrate the usefulness of the proposed approach on applications to procedural noise generation, anisotropic meshing, diffusion tensor imaging and spectral texture synthesis.

Keywords

Optimal transporttensor fieldPSD matricesquantum entropy
Type
Papers
Information
European Journal of Applied Mathematics , Volume 30 , Special Issue 6: Applied Optimal Transport , December 2019 , pp. 1079 - 1102
Copyright
© Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

The work of Gabriel Peyré has been supported by the European Research Council (ERC project SIGMA-Vision). J. Solomon acknowledges support of Army Research Office grant W911NF-12-R-0011 (“Smooth Modeling of Flows on Graphs”).

References

Agueh, M. & Carlier, G. (2011) Barycenters in the Wasserstein space. SIAM J. Math. Anal. 43 (2), 904–924.CrossRefGoogle Scholar
Al-Mohy, A. H. & Higham, N. J. (2009) A new scaling and squaring algorithm for the matrix exponential. SIAM J. Sci. Comput. 31 (3), 970–989.Google Scholar
Al-Mohy, A. H. & Higham, N. J. (2012) Improved inverse scaling and squaring algorithms for the matrix logarithm. SIAM J. Sci. Comput. 34 (4), C153–C169.CrossRefGoogle Scholar
Alliez, P., Cohen-Steiner, D., Devillers, O., Lévy, B. & Desbrun, M. (2003) Anisotropic polygonal remeshing. In: ACM Transactions on Graphics (TOG), Vol. 22, ACM, pp. 485–493.Google Scholar
Anderson, D. G. (1965) Iterative procedures for nonlinear integral equations. J. ACM. 12 (4), 547–560.CrossRefGoogle Scholar
Bauschke, H. H. & Lewis, A. S. (2000) Dykstra's algorithm with Bregman projections: a convergence proof. Optimization. 48 (4), 409–427.CrossRefGoogle Scholar
Beck, A. & Teboulle, M. (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2 (1), 183–202.CrossRefGoogle Scholar
Benamou, J.-D. & Brenier, Y. (2000) A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numer. Math. 84 (3), 375–393.CrossRefGoogle Scholar
Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, L. & Peyré, G. (2015) Iterative Bregman projections for regularized transportation problems. SIAM J. Sci. Comp. 37 (2), A1111–A1138.CrossRefGoogle Scholar
Bonneel, N., Van De Panne, M., Paris, S. & Heidrich, W. (2011) Displacement interpolation using Lagrangian mass transport. ACM Trans. Graph. 30 (6), 158:1–158:12.CrossRefGoogle Scholar
Bougleux, S., Peyré, G. & Cohen, L. D. (2009) Image compression with anisotropic geodesic triangulations. In: Proceedings of ICCV'09, pp. 2343–2348.Google Scholar
Bregman, L. M. (1967) The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comp. Math. Math. Phys. 7 (3), 200–217.CrossRefGoogle Scholar
Brenier, Y. (1991) Polar factorization and monotone rearrangement of vector-valued functions. Comm. Pure Appl. Math. 44 (4), 375–417.CrossRefGoogle Scholar
Carlen, E. A. & Maas, J. (2014) An analog of the 2-Wasserstein metric in non-commutative probability under which the fermionic Fokker–Planck equation is gradient flow for the entropy. Commun. Math. Phys. 331 (3), 887–926.CrossRefGoogle Scholar
Carlen, E. A. & Maas, J. (2017) Gradient flow and entropy inequalities for quantum markov semigroups with detailed balance. J. Funct. Anal. 273 (5), 1810–1869.CrossRefGoogle Scholar
Chandrasekaran, V. & Shah, P. (2017) Relative entropy optimization and its applications. Math. Program. 161 (1), 1–32.CrossRefGoogle Scholar
Chen, Y., Gangbo, W., Georgiou, T. T. & Tannenbaum, A. (2017) On the matrix Monge-Kantorovich problem. Preprint arXiv:1701.02826.Google Scholar
Chen, Y., Georgiou, T. T. & Tannenbaum, A. (2016) Matrix optimal mass transport: A quantum mechanical approach. Preprint arXiv:1610.03041.Google Scholar
Chen, Y., Georgiou, T. T. & Tannenbaum, A. (2016) Vector-valued optimal mass transport. Preprint arXiv:1610.03041.Google Scholar
Chizat, L., Peyré, G., Schmitzer, B. & Vialard, F.-X. (2015) Unbalanced optimal transport: Geometry and Kantorovich formulation. Preprint 1508.05216, Arxiv.Google Scholar
Chizat, L., Peyré, G., Schmitzer, B. & Vialard, F.-X. (2016) An interpolating distance between optimal transport and Fisher–Rao metrics. Found. Comput. Math., doi: 10.1007/s10208-016-9331-y.Google Scholar
Chizat, L., Peyré, G., Schmitzer, B. & Vialard, F.-X. (2016) Scaling algorithms for unbalanced transport problems to appear in Mathematics of Computation, 2017. Preprint 1607.05816, Arxiv.Google Scholar
Crane, K., Desbrun, M. & Schröder, P. (2010) Trivial connections on discrete surfaces. In: Computer Graphics Forum, Vol. 29, Wiley Online Library, pp. 1525–1533.Google Scholar
Cuturi, M. (2013) Sinkhorn distances: Lightspeed computation of optimal transportation. In: Proceedings of NIPS, Vol. 26, pp. 2292–2300.Google Scholar
Demaret, L., Dyn, N. & Iske, A. (2006) Image compression by linear splines over adaptive triangulations. Signal Process. 86 (7), 1604–1616.CrossRefGoogle Scholar
Deriche, R., Tschumpelé, D., Lenglet, C. & Rousson, M. (2006) Variational Approaches to the Estimation, Regularizatinn, and Segmentation of Diffusion Tensor Images, Springer US, Boston, MA, pp. 517–530.Google Scholar
Dhillon, I. S. & Tropp, J. A. (2008) Matrix nearness problems with Bregman divergences. SIAM J. Matrix Anal. Appl., 29 (4), 1120–1146.CrossRefGoogle Scholar
Dryden, I. L., Koloydenko, A. & Zhou, D. (2009) Non-Euclidean statistics for covariance matrices, with applications to diffusion tensor imaging. Ann. Appl. Stat. 3 (3), 1102–1123.CrossRefGoogle Scholar
Dykstra, R. L. (1983) An algorithm for restricted least squares regression. J. Amer. Stat. 78 (384), 839–842.CrossRefGoogle Scholar
Frogner, C., Zhang, C., Mobahi, H., Araya, M. & Poggio, T. A. (2015) Learning with a Wasserstein loss. In: Advances in Neural Information Processing Systems, Vol. 28, pp. 2044–2052.Google Scholar
Galerne, B., Gousseau, Y. & Morel, J.-M. (2011) Random phase textures: Theory and synthesis. IEEE Trans. Image Process. 20 (1), 257–267.CrossRefGoogle ScholarPubMed
Georgiou, T. T. & Pavon, M. (2015) Positive contraction mappings for classical and quantum Schrödinger systems. J. Math. Phys. 56 (3), 033301.CrossRefGoogle Scholar
Gurvits, L. (2004) Classical complexity and quantum entanglement. J. Comput. Syst. Sci. 69 (3), 448–484.CrossRefGoogle Scholar
Hotz, I., Feng, L., Hagen, H., Hamann, B., Joy, K. & Jeremic, B. (2004) Physically based methods for tensor field visualization. pages 123–130. IEEE Computer Society.Google Scholar
Jiang, X., Ning, L. & Georgiou, T. T. (2012) Distances and Riemannian metrics for multivariate spectral densities. IEEE Trasn. Autom. Control. 57 (7), 1723–1735, Jul. 2012.CrossRefGoogle Scholar
Kantorovich, L. V. (1942) On the transfer of masses (in Russian). Dokl. Akad. Nauk 37 (2), 227–229.Google Scholar
Kondratyev, S., Monsaingeon, L. & Vorotnikov, D. (2016) A new optimal transport distance on the space of finite radon measures. Adv. Differ. Equ. 21 (11/12), 1117–1164, 11.Google Scholar
Kulis, B., Sustik, M. A. & Dhillon, I. S. (2009) Low-rank kernel learning with Bregman matrix divergences. J. Mach. Learn. Res. 10, 341–376.Google Scholar
Lagae, A., Lefebvre, S., Cook, R., DeRose, T., Drettakis, G., Ebert, D. S., Lewis, J. P., Perlin, K. & Zwicker, M. (2010) A survey of procedural noise functions. In Computer Graphics Forum, Vol. 29, Wiley Online Library, pp. 2579–2600.Google Scholar
Lagae, A., Lefebvre, S. & Dutré, P. (2011) Improving Gabor noise. IEEE Trans. Vis. Comput. Graph. 17 (8), 1096–1107.CrossRefGoogle ScholarPubMed
Liero, M., Mielke, A. & Savaré, G. (2015) Optimal entropy-transport problems and a new Hellinger–Kantorovich distance between positive measures. ArXiv e-prints.Google Scholar
Liero, M., Mielke, A. & Savaré, G. (2016) Optimal transport in competition with reaction: The Hellinger–Kantorovich distance and geodesic curves. SIAM J. Math. Anal. 48 (4), 2869–2911.CrossRefGoogle Scholar
Mittnenzweig, M. & Mielke, A. (2017) An entropic gradient structure for lindblad equations and couplings of quantum systems to macroscopic models. J. Stat. Phys. 167 (2), 205–233.CrossRefGoogle Scholar
Monge, G. Mémoire sur la théorie des déblais et des remblais. Histoire de l'Académie Royale des Sciences. 1781, pp. 666–704.Google Scholar
Nesterov, Y. (1983) A method of solving a convex programming problem with convergence rate o(1/k 2). In: Soviet Mathematics Doklady.27, pp. 372–376.Google Scholar
Ning, L. & Georgiou, T. T. (2014) Metrics for matrix-valued measures via test functions. In: Proceedings of the 53rd IEEE Conference on Decision and Control, IEEE, pp. 2642–2647.Google Scholar
Ning, L., Georgiou, T. T. & Tannenbaum, A. (2015) On matrix-valued Monge–Kantorovich optimal mass transport. IEEE Trans. Autom. Control. 60 (2), 373–382.CrossRefGoogle ScholarPubMed
Pestilli, F., Yeatman, J. D., Rokem, A., Kay, K. N. & Wandell, B. A. (2014) Evaluation and statistical inference for human connectomes. Nature Methods 11 (10), 1058–1063.CrossRefGoogle ScholarPubMed
Polyak, B. T. (1964) Some methods of speeding up the convergence of iteration methods. USSR Comput. Math. Math. Phys. 4 (5), 1–17.CrossRefGoogle Scholar
Rockafellar, R.-T. (1970) Convex Analysis, Princeton University Press, Princeton, New Jersey.CrossRefGoogle Scholar
Rubner, Y., Tomasi, C. & Guibas, L. J. (2000) The earth mover's distance as a metric for image retrieval. Int. J. Comput. Vis. 40 (2), 99–121.CrossRefGoogle Scholar
Santambrogio, F. (2015) Optimal transport for applied mathematicians. In: Birkäuser (editor), Prog. Nonlinear Differ. Equ. Appl. 87, Springer International Publishing AG Switzerland, NY.Google Scholar
Schmitzer, B. (2016) Stabilized sparse scaling algorithms for entropy regularized transport problems. arXiv:1610.06519.Google Scholar
Shewchuk, J. (2002) What is a good linear finite element? Interpolation, conditioning, anisotropy and quality measures (preprint). 73, University of California, Berkeley.Google Scholar
Sinkhorn, R. (1964) A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Statist. 35, 876–879.CrossRefGoogle Scholar
Solomon, J., De Goes, F., Peyré, G., Cuturi, M., Butscher, A., Nguyen, A., Du, T. & Guibas, L. (2015) Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains. TOG. 34 (4), 66:1–66:11.CrossRefGoogle Scholar
Takemura, H., Caiafa, C. F., Wandell, B. A. & Pestilli, F. (2016) Ensemble tractography. PLoS Comput. Biol. 12 (2), e1004692.CrossRefGoogle ScholarPubMed
Vaxman, A., Campen, M., Diamanti, O., Panozzo, D., Bommes, D., Hildebrandt, K. & Ben-Chen, M. (2016) Directional field synthesis, design, and processing. Comput. Graph. Forum 35 (2), 545–572.CrossRefGoogle Scholar
Wandell, B. A. (2016) Clarifying human white matter. Annu. Rev. Neurosci. 8 (39), 103–28.CrossRefGoogle Scholar
Weickert, J. (1998) Anisotropic Diffusion in Image Processing, Vol. 1, Teubner Stuttgart, Stuttgart.Google Scholar