Curve based approximation of measures on manifolds by discrepancy minimization. (English) Zbl 1491.65048
Summary: The approximation of probability measures on compact metric spaces and in particular on Riemannian manifolds by atomic or empirical ones is a classical task in approximation and complexity theory with a wide range of applications. Instead of point measures we are concerned with the approximation by measures supported on Lipschitz curves. Special attention is paid to push-forward measures of Lebesgue measures on the unit interval by such curves. Using the discrepancy as distance between measures, we prove optimal approximation rates in terms of the curve’s length and Lipschitz constant. Having established the theoretical convergence rates, we are interested in the numerical minimization of the discrepancy between a given probability measure and the set of push-forward measures of Lebesgue measures on the unit interval by Lipschitz curves. We present numerical examples for measures on the \(2\)- and \(3\)-dimensional torus, the \(2\)-sphere, the rotation group on \(\mathbb{R}^3\) and the Grassmannian of all \(2\)-dimensional linear subspaces of \(\mathbb{R}^4\). Our algorithm of choice is a conjugate gradient method on these manifolds, which incorporates second-order information. For efficient gradient and Hessian evaluations within the algorithm, we approximate the given measures by truncated Fourier series and use fast Fourier transform techniques on these manifolds.
MSC:
| 65K10 | Numerical optimization and variational techniques |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
approximation of measures; curves; Fourier methods; manifolds; non-convex optimization; quadrature rules; sampling theorySoftware:
NFFT3References:
| [1] | Absil, PA; Mahony, R.; Sepulchre, R., Optimization Algorithms on Matrix Manifolds (2008), Princeton: Princeton University Press, Princeton · Zbl 1147.65043 |
| [2] | Akleman, E.; Xing, Q.; Garigipati, P.; Taubin, G.; Chen, J.; Hu, S., Hamiltonian cycle art: Surface covering wire sculptures and duotone surfaces, Comput. Graph., 37, 5, 316-332 (2013) |
| [3] | Ambrosio, L.; Fusco, N.; Pallara, D., Functions of Bounded Variation and Free Discontinuity Problems (2000), New York: Oxford University Press, New York · Zbl 0957.49001 |
| [4] | Ambrosio, L.; Gigli, N.; Savaré, G., Gradient Flows in Metric Spaces and in the Space of Probability Measures (2005), Basel: Birkhäuser, Basel · Zbl 1090.35002 |
| [5] | Asimov, D., The Grand Tour: A tool for viewing multidimensional data, SIAM J. Sci. Stat. Comput., 6, 1, 28-143 (1985) · Zbl 0552.62052 |
| [6] | Bachoc, C., Linear programming bounds for codes in Grassmannian spaces, IEEE Trans. Inf. Th., 52, 5, 2111-2125 (2006) · Zbl 1282.94106 |
| [7] | Bachoc, C.; Bannai, E.; Coulangeon, R., Codes and designs in Grassmannian spaces, Discrete Math., 277, 1-3, 15-28 (2004) · Zbl 1040.05005 |
| [8] | Bachoc, C.; Coulangeon, R.; Nebe, G., Designs in Grassmannian spaces and lattices, J. Algebr. Comb., 16, 1, 5-19 (2002) · Zbl 1035.05027 |
| [9] | Bondarenko, A.; Radchenko, D.; Viazovska, M., Optimal asymptotic bounds for spherical designs, Ann. Math., 178, 2, 443-452 (2013) · Zbl 1270.05026 |
| [10] | Bondarenko, A.; Radchenko, D.; Viazovska, M., Well-separated spherical designs, Constr. Approx., 41, 1, 93-112 (2015) · Zbl 1314.52020 |
| [11] | Boyer, C.; Chauffert, N.; Ciuciu, P.; Kahn, J.; Weiss, P., On the generation of sampling schemes for magnetic resonance imaging, SIAM J. Imaging Sci., 9, 4, 2039-2072 (2016) · Zbl 1439.94003 |
| [12] | Braides, A., \( \Gamma \)-Convergence for Beginners (2002), Oxford: Oxford University Press, Oxford · Zbl 1198.49001 |
| [13] | Brandolini, L., Choirat, C., Colzani, L., Gigante, G., Seri, R., Travaglini, G.: Quadrature rules and distribution of points on manifolds. Ann. Scuola Norm.-Sci. 13(4), 889-923 (2014) · Zbl 1312.41040 |
| [14] | Breger, A., Ehler, M., Gräf, M.: Quasi Monte Carlo integration and kernel-based function approximation on Grassmannians. In: Frames and Other Bases in Abstract and Function Spaces: Novel Methods in Harmonic Analysis, pp. 333-353. Birkhäuser, Basel (2017) · Zbl 1453.65007 |
| [15] | Bridson, M.; Häfliger, A., Metric Spaces of Non-Positive Curvature, A Series of Comprehensive Studies in Mathematics (1999), Berlin: Springer, Berlin · Zbl 0988.53001 |
| [16] | Burago, D.; Burago, Y.; Ivanov, S., A Course in Metric Geometry, Graduate Studies in Mathematics (2001), Providence: Amer. Math. Soc, Providence · Zbl 0981.51016 |
| [17] | Chauffert, N.; Ciuciu, P.; Kahn, J.; Weiss, P., Variable density sampling with continuous trajectories, SIAM J. Imaging Sci., 7, 4, 1962-1992 (2014) · Zbl 1308.94047 |
| [18] | Chauffert, N.; Ciuciu, P.; Kahn, J.; Weiss, P., A projection method on measures sets, Constr. Approx., 45, 1, 83-111 (2017) · Zbl 1362.41003 |
| [19] | Chavel, I., Eigenvalues in Riemannian Geometry (1984), Orlando: Academic Press, Orlando · Zbl 0551.53001 |
| [20] | Chen, Z.; Shen, Z.; Guo, J.; Cao, J.; Zeng, X., Line drawing for 3D printing, Comput. Graph., 66, 85-92 (2017) |
| [21] | Chevallier, J., Uniform decomposition of probability measures: Quantization, clustering and rate of convergence, J. Appl. Probab., 55, 4, 1037-1045 (2018) · Zbl 1405.60025 |
| [22] | Coulhon, T.; Russ, E.; Tardivel-Nachef, V., Sobolev algebras on Lie groups and Riemannian manifolds, Amer. J. Math., 123, 2, 283-342 (2001) · Zbl 0990.43003 |
| [23] | Cucker, F.; Smale, S., On the mathematical foundations of learning, Bull. Amer. Math. Soc., 39, 1, 1-49 (2002) · Zbl 0983.68162 |
| [24] | Cuturi, M.; Peyré, G., Computational optimal transport, Found. Trends Mach. Learn., 11, 5-6, 355-607 (2019) · Zbl 1475.68011 |
| [25] | Daniel, JW, The conjugate gradient method for linear and nonlinear operator equations, SIAM J. Numer. Anal., 4, 1, 10-26 (1967) · Zbl 0154.40302 |
| [26] | Dick, J., Ehler, M., Gräf, M., Krattenthaler, C.: Spectral decomposition of discrepancy kernels on the Euclidean ball, the special orthogonal group, and the Grassmannian manifold. arXiv:1909.12334 (2019) |
| [27] | Duchamp, T.; Stuetzle, W., Extremal properties of principal curves in the plane, Ann. Stat., 24, 4, 1511-1520 (1996) · Zbl 0867.62025 |
| [28] | Dziugaite, G.K., Roy, D.M., Ghahramani, Z.: Training generative neural networks via maximum mean discrepancy optimization. In: Proc. of the 31st Conference on Uncertainty in Artificial Intelligence, pp. 258-267 (2015) |
| [29] | Ehler, M.; Gräf, M., Reproducing kernels for the irreducible components of polynomial spaces on unions of Grassmannians, Constr. Approx., 49, 1, 29-58 (2018) · Zbl 1440.42128 |
| [30] | Feydy, J., Séjourné, T., Vialard, F.X., Amari, S., Trouvé, A., Peyré, G.: Interpolating between optimal transport and MMD using Sinkhorn divergences. In: Proc. of Machine Learning Research, vol. 89, pp. 2681-2690. PMLR (2019) |
| [31] | Filbir, F.; Mhaskar, HN, Marcinkiewicz-Zygmund measures on manifolds, J. Complex., 27, 6, 568-596 (2011) · Zbl 1235.58007 |
| [32] | Fonseca, I.; Leoni, G., Modern Methods in the Calculus of Variations: \(L^p\) Spaces (2007), New York: Springer, New York · Zbl 1153.49001 |
| [33] | Fornasier, M.; Haskovec, J.; Steidl, G., Consistency of variational continuous-domain quantization via kinetic theory, Appl. Anal., 92, 6, 1283-1298 (2013) · Zbl 1273.82030 |
| [34] | Förster, KJ; Petras, K., On estimates for the weights in Gaussian quadrature in the ultraspherical case, Math. Comp., 55, 191, 243-264 (1990) · Zbl 0705.65015 |
| [35] | Fulton, W.; Harris, J., Representation Theory: A First Course (1991), New York: Springer, New York · Zbl 0744.22001 |
| [36] | Fuselier, E.; Wright, GB, Scattered data interpolation on embedded submanifolds with restricted positive definite kernels: Sobolev error estimates, SIAM J. Numer. Anal., 50, 3, 1753-1776 (2012) · Zbl 1251.41004 |
| [37] | Genevay, A., Chizat, L., Bach, F., Cuturi, M., Peyré, G.: Sample complexity of Sinkhorn divergences. In: Proc. of Machine Learning Research, vol. 89, pp. 1574-1583. PMLR (2019) |
| [38] | Gerber, S.; Whitaker, R., Regularization-free principal curve estimation, J. Mach. Learn. Res., 14, 1, 1285-1302 (2013) · Zbl 1317.68159 |
| [39] | Gigante, G.; Leopardi, P., Diameter bounded equal measure partitions of Ahlfors regular metric measure spaces, Discrete Comput. Geom., 57, 2, 419-430 (2017) · Zbl 1366.52020 |
| [40] | Gnewuch, M., Weighted geometric discrepancies and numerical integration on reproducing kernel Hilbert spaces, J. Complex., 28, 1, 2-17 (2012) · Zbl 1333.11073 |
| [41] | de Gournay, F.; Kahn, J.; Lebrat, L., Differentiation and regularity of semi-discrete optimal transport with respect to the parameters of the discrete measure, Numer. Math., 141, 2, 429-453 (2019) · Zbl 1475.49055 |
| [42] | Gräf, M., A unified approach to scattered data approximation on \({\mathbb{S}}^3\) and \(\rm SO(3)\), Adv. Comput. Math., 37, 3, 379-392 (2012) · Zbl 1257.41001 |
| [43] | Gräf, M.: Efficient algorithms for the computation of optimal quadrature points on Riemannian manifolds. PhD thesis, TU Chemnitz (2013) |
| [44] | Gräf, M.; Potts, D., Sampling sets and quadrature formulae on the rotation group, Numer. Funct. Anal. Optim., 30, 7-8, 665-688 (2009) · Zbl 1177.65043 |
| [45] | Gräf, M.; Potts, D., On the computation of spherical designs by a new optimization approach based on fast spherical Fourier transforms, Numer. Math., 119, 4, 699-724 (2011) · Zbl 1232.65045 |
| [46] | Gräf, M.; Potts, M.; Steidl, G., Quadrature errors, discrepancies and their relations to halftoning on the torus and the sphere, SIAM J. Sci. Comput., 34, 5, 2760-2791 (2013) · Zbl 1261.65066 |
| [47] | Gröchenig, K.; Romero, JL; Unnikrishnan, J.; Vetterli, M., On minimal trajectories for mobile sampling of bandlimited fields, Appl. Comput. Harmon. Anal., 39, 3, 487-510 (2015) · Zbl 1339.94028 |
| [48] | Hajlasz, P.: Sobolev spaces on metric-measure spaces. In: Heat Kernels and Analysis on Manifolds, Graphs, and Metric Spaces, Contemp. Math., vol. 338, pp. 173-218. Amer. Math. Soc., Providence (2003) · Zbl 1048.46033 |
| [49] | Hastie, T.; Stuetzle, W., Principal curves, J. Am. Stat. Assoc., 84, 406, 502-516 (1989) · Zbl 0679.62048 |
| [50] | Hauberg, S., Principal curves on Riemannian manifolds, IEEE Trans. Pattern Anal. Mach. Intell., 38, 9, 1915-1921 (2015) |
| [51] | Hesse, K.; Mhaskar, HN; Sloan, IH, Quadrature in Besov spaces on the Euclidean sphere, J. Complex., 23, 4-6, 528-552 (2007) · Zbl 1134.41013 |
| [52] | Hörmander, L., The Analysis of Linear Partial Differential Operators I (1983), Berlin: Springer, Berlin · Zbl 0521.35001 |
| [53] | James, AT; Constantine, AG, Generalized Jacobi polynomials as spherical functions of the Grassmann manifold, Proc. London Math. Soc., 29, 3, 174-192 (1974) · Zbl 0289.33031 |
| [54] | Kaplan, C.S., Bosch, R.: TSP art. In: Renaissance Banff: Mathematics, Music, Art, Culture, pp. 301-308. Bridges Conference (2005) |
| [55] | Kégl, B.; Krzyzak, A.; Linder, T.; Zeger, K., Learning and design of principal curves, IEEE Trans. Pattern Anal. Mach. Intell., 22, 3, 281-297 (2000) |
| [56] | Keiner, J.; Kunis, S.; Potts, D., Using NFFT3 - a software library for various nonequispaced fast Fourier transforms, ACM Trans. Math. Software, 36, 4, 1-30 (2009) · Zbl 1364.65303 |
| [57] | Kim, J.H., Lee, J., Oh, H.S.: Spherical principal curves. arXiv:2003.02578 (2020) |
| [58] | Kloeckner, B., Approximation by finitely supported measures, ESAIM Control Opt. Calc. Var., 18, 2, 343-359 (2012) · Zbl 1246.49040 |
| [59] | Kuipers, L.; Niederreiter, H., Uniform Distribution of Sequences (1974), New York: Wiley, New York · Zbl 0281.10001 |
| [60] | Lazarus, C.; Weiss, P.; Chauffert, N.; Mauconduit, F.; El Gueddari, L.; Destrieux, C.; Zemmoura, I.; Vignaud, A.; Ciuciu, P., SPARKLING: Variable-density k-space filling curves for accelerated \({T}_2^*\)-weighted MRI, Magn. Reson. Med., 81, 6, 3643-3661 (2019) |
| [61] | Lebrat, L.; de Gournay, F.; Kahn, J.; Weiss, P., Optimal transport approximation of 2-dimensional measures, SIAM J. Imaging Sci., 12, 2, 762-787 (2019) · Zbl 1524.65097 |
| [62] | Matousek, J., Geometric Discrepancy, Algorithms and Combinatorics (2010), Berlin: Springer, Berlin |
| [63] | Mercer, J.: Functions of positive and negative type and their connection with the theory of integral equations. Philos. Trans. Roy. Soc. London Ser. A 209(441-458), 415-446 (1909) · JFM 40.0408.02 |
| [64] | Mhaskar, HN, Eignets for function approximation on manifolds, Appl. Comput. Harmon. Anal., 29, 1, 63-87 (2010) · Zbl 1201.41003 |
| [65] | Mhaskar, H.N.: Approximate quadrature measures on data-defined spaces. In: Contemporary Computational Mathematics - A Celebration of the 80th Birthday of Ian Sloan. Springer, Cham (2018) · Zbl 1405.65030 |
| [66] | Müller, C.: Spherical Harmonics, Lecture Notes in Mathematics, vol. 17. Springer, Berlin (1992) · Zbl 0138.05101 |
| [67] | Novak, E., Wozniakowski, H.: Tractability of Multivariate Problems. Volume II, EMS Tracts in Mathematics, vol. 12. EMS Publishing House, Zürich (2010) · Zbl 1241.65025 |
| [68] | Plonka, G.; Potts, D.; Steidl, G.; Tasche, M., Numerical Fourier Analysis (2019), Basel: Birkhäuser, Basel · Zbl 1412.65001 |
| [69] | Ring, W.; Wirth, B., Optimization methods on Riemannian manifolds and their application to shape space, SIAM J. Optim., 22, 2, 596-627 (2012) · Zbl 1250.90111 |
| [70] | Roe, J., Elliptic Operators, Topology and Asymptotic Methods (1998), Harlow: Longman, Harlow · Zbl 0919.58060 |
| [71] | Roy, A., Bounds for codes and designs in complex subspaces, J. Algebr. Comb., 31, 1, 1-32 (2010) · Zbl 1226.05078 |
| [72] | Schmaltz, C.; Gwosdek, P.; Bruhn, A.; Weickert, J., Electrostatic halftoning., Comp. Graph. For., 29, 8, 2313-2327 (2010) |
| [73] | Smith, S.T.: Optimization techniques on Riemannian manifolds. In: Hamiltonian and Gradient Flows, Algorithms and Control, Fields Inst. Commun., vol. 3, pp. 113-136. Amer. Math. Soc., Providence (1994) · Zbl 0816.49032 |
| [74] | Steele, JM, Growth rates of Euclidean minimum spanning trees with power weighted edges, Ann. Probab., 16, 4, 1767-1787 (1988) · Zbl 0655.60023 |
| [75] | Steele, JM; Snyder, TL, Worst-case growth rates of some classical problems of combinatorial optimization, SIAM J. Comput., 18, 2, 278-287 (1989) · Zbl 0674.90080 |
| [76] | Steinwart, I.; Scovel, C., Mercer’s theorem on general domains: On the interaction between measures, kernels, and RKHSs, Constr. Approx., 35, 3, 363-417 (2011) · Zbl 1252.46018 |
| [77] | Teuber, T.; Steidl, G.; Gwosdek, P.; Schmaltz, C.; Weickert, J., Dithering by differences of convex functions, SIAM J. Imaging Sci., 4, 1, 79-108 (2011) · Zbl 1214.49017 |
| [78] | Triebel, H., Theory of Function Spaces II (1992), Basel: Birkhäuser, Basel · Zbl 0763.46025 |
| [79] | Udrişte, C., Convex Functions and Optimization Methods on Riemannian Manifolds, Mathematics and its Applications (1994), Dordrecht: Springer, Dordrecht · Zbl 0932.53003 |
| [80] | Varshalovich, D.; Moskalev, A.; Khersonskii, V., Quantum Theory of Angular Momentum (1988), Singapore: World Scientific, Singapore |
| [81] | Villani, C., Topics in Optimal Transportation (2003), Providence: Amer. Math. Soc, Providence · Zbl 1106.90001 |
| [82] | Wagner, G., On means of distances on the surface of a sphere II (upper bounds), Pacific J. Math., 154, 2, 381-396 (1992) · Zbl 0767.11033 |
| [83] | Wagner, G.; Volkmann, B., On averaging sets, Monatsh. Math., 111, 1, 69-78 (1991) · Zbl 0721.65011 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
