# American Institute of Mathematical Sciences

• Previous Article
A destination-preserving model for simulating Wardrop equilibria in traffic flow on networks
• NHM Home
• This Issue
• Next Article
(Almost) Everything you always wanted to know about deterministic control problems in stratified domains
December  2015, 10(4): 837-855. doi: 10.3934/nhm.2015.10.837

## Regularity of densities in relaxed and penalized average distance problem

 1 Department of Mathematical Sciences, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA, 15213, United States

Received  March 2014 Revised  June 2015 Published  October 2015

The average distance problem finds application in data parameterization, which involves representing'' the data using lower dimensional objects. From a computational point of view it is often convenient to restrict the unknown to the family of parameterized curves. The original formulation of the average distance problem exhibits several undesirable properties. In this paper we propose an alternative variant: we minimize the functional \begin{equation*} \int_{{\mathbb{R}}^d\times \Gamma_\gamma} |x-y|^p {\,{d}}\Pi(x,y)+\lambda L_\gamma +\varepsilon\alpha(\nu) +\varepsilon' \eta(\gamma)+\varepsilon''\|\gamma'\|_{TV}, \end{equation*} where $\gamma$ varies among the family of parametrized curves, $\nu$ among probability measures on $\gamma$, and $\Pi$ among transport plans between $\mu$ and $\nu$. Here $\lambda,\varepsilon,\varepsilon',\varepsilon''$ are given parameters, $\alpha$ is a penalization term on $\mu$, $\Gamma_\gamma$ (resp. $L_\gamma$) denotes the graph (resp. length) of $\gamma$, and $\|\cdot\|_{TV}$ denotes the total variation semi-norm. We will use techniques from optimal transport theory and calculus of variations. The main aim is to prove essential boundedness, and Lipschitz continuity for Radon-Nikodym derivative of $\nu$, when $(\gamma,\nu,\Pi)$ is a minimizer.
Citation: Xin Yang Lu. Regularity of densities in relaxed and penalized average distance problem. Networks & Heterogeneous Media, 2015, 10 (4) : 837-855. doi: 10.3934/nhm.2015.10.837
##### References:
 [1] L. Ambrosio, N. Gigli and G. Savaré, Gradient Flow in Metric Spaces and in the Space of Probability Measures,, Second Editon, (2005).   Google Scholar [2] G. Buttazzo, E. Mainini and E. Stepanov, Stationary configurations for the average distance functional and related problems,, Control Cybernet., 38 (2009), 1107.   Google Scholar [3] G. Buttazzo, E. Oudet and E. Stepanov, Optimal transportation problems with free Dirichlet regions,, Progr. Nonlinear Differential Equations Appl., 51 (2002), 41.   Google Scholar [4] G. Buttazzo and F. Santambrogio, A mass transportation model for the optimal planning of an urban region,, SIAM J. Math. Anal., 37 (2005), 514.  doi: 10.1137/S0036141003438313.  Google Scholar [5] G. Buttazzo and E. Stepanov, Minimization problems for average distance functionals,, in Calculus of Variations: Topics from the Mathematical Heritage of Ennio De Giorgi (ed. D. Pallara), 14 (2004), 48.   Google Scholar [6] G. Buttazzo and E. Stepanov, Optimal transportation networks as free Dirichlet regions for the Monge-Kantorovich problem,, Ann. Sc. Norm. Sup. Pisa Cl. Sci., 2 (2003), 631.   Google Scholar [7] P. Drineas, A. Frieze, R. Kannan, S. Vempala and V. Vinay, Clustering large graphs via the singular value decomposition,, Mach. Learn., 56 (2004), 9.  doi: 10.1023/B:MACH.0000033113.59016.96.  Google Scholar [8] T. Duchamp and W. Stuetzle, Extremal properties of principal curves in the plane,, Ann. Statist., 24 (1996), 1511.  doi: 10.1214/aos/1032298280.  Google Scholar [9] T. Duchamp and W. Stuetzle, Geometric properties of principal curves in the plane,, in Robust Statistics, 109 (1996), 135.  doi: 10.1007/978-1-4612-2380-1_9.  Google Scholar [10] A. Fischer, Selecting the length of a principal curve within a Gaussian model,, Electron. J. Statist., 7 (2013), 342.  doi: 10.1214/13-EJS775.  Google Scholar [11] W. Gangbo and R. J. McCann, The geometry of optimal transportation,, Acta Math., (1996), 113.  doi: 10.1007/BF02392620.  Google Scholar [12] T. Hastie, Principal Curves and Surfaces,, Ph. D Thesis, (1984).   Google Scholar [13] T. Hastie and W. Stuetzle, Principal curves,, J. Amer. Statist. Assoc., 84 (1989), 502.  doi: 10.1080/01621459.1989.10478797.  Google Scholar [14] B. Kégl, Principal Curves: Learning, Design, and Applications,, Ph.D thesis, (1999).   Google Scholar [15] K. Kégl and K. Aetal, Learning and design of principal curves,, IEEE Trans. Pattern Anal. Mach. Intell., 22 (2000), 281.   Google Scholar [16] A. Lemenant, A presentation of the average distance minimizing problem,, J. Math. Sci. (N.Y.), 181 (2012), 820.  doi: 10.1007/s10958-012-0717-3.  Google Scholar [17] X. Y. Lu, Example of minimizer of the average distance problem with non closed set of corners,, Rend. Sem. Mat. Univ. Padova, ().   Google Scholar [18] X. Y. Lu and D. Slepčev, Properties of minimizers of average distance problem via discrete approximation of measures,, SIAM J. Math. Anal., 45 (2013), 3114.  doi: 10.1137/130905745.  Google Scholar [19] U. Ozertem and D. Erdogmus, Locally defined principal curves and surfaces,, J. Mach. Learn. Res., 12 (2011), 1249.   Google Scholar [20] E. Paolini and E. Stepanov, Qualitative properties of maximum and average distance minimizers in $\mathbbR^n$,, J. Math. Sci. (N.Y.), 122 (2004), 3290.  doi: 10.1023/B:JOTH.0000031022.10122.f5.  Google Scholar [21] P. Polak and G. Wolanski, The lazy traveling salesman problem in $\mathbbR^2$,, ESAIM: Control Optim. Calc. Var., 13 (2007), 538.  doi: 10.1051/cocv:2007025.  Google Scholar [22] D. Slepčev, Counterexample to regularity in average-distance problem,, Ann. Inst. H. Poincaré (C), 31 (2014), 169.  doi: 10.1016/j.anihpc.2013.02.004.  Google Scholar [23] A. J. Smola, S. Mika, B. Schölkopf and R. C. Williamson, Regularized principal manifolds,, J. Mach. Learn., 1 (2001), 179.  doi: 10.1162/15324430152748227.  Google Scholar [24] R. Tibshirani, Principal curves revisited,, Stat. Comput., 2 (1992), 183.  doi: 10.1007/BF01889678.  Google Scholar [25] C. Villani, Optimal Transport, Old and New,, Grundlehren der mathematischen Wissenschaften, (2009).  doi: 10.1007/978-3-540-71050-9.  Google Scholar

show all references

##### References:
 [1] L. Ambrosio, N. Gigli and G. Savaré, Gradient Flow in Metric Spaces and in the Space of Probability Measures,, Second Editon, (2005).   Google Scholar [2] G. Buttazzo, E. Mainini and E. Stepanov, Stationary configurations for the average distance functional and related problems,, Control Cybernet., 38 (2009), 1107.   Google Scholar [3] G. Buttazzo, E. Oudet and E. Stepanov, Optimal transportation problems with free Dirichlet regions,, Progr. Nonlinear Differential Equations Appl., 51 (2002), 41.   Google Scholar [4] G. Buttazzo and F. Santambrogio, A mass transportation model for the optimal planning of an urban region,, SIAM J. Math. Anal., 37 (2005), 514.  doi: 10.1137/S0036141003438313.  Google Scholar [5] G. Buttazzo and E. Stepanov, Minimization problems for average distance functionals,, in Calculus of Variations: Topics from the Mathematical Heritage of Ennio De Giorgi (ed. D. Pallara), 14 (2004), 48.   Google Scholar [6] G. Buttazzo and E. Stepanov, Optimal transportation networks as free Dirichlet regions for the Monge-Kantorovich problem,, Ann. Sc. Norm. Sup. Pisa Cl. Sci., 2 (2003), 631.   Google Scholar [7] P. Drineas, A. Frieze, R. Kannan, S. Vempala and V. Vinay, Clustering large graphs via the singular value decomposition,, Mach. Learn., 56 (2004), 9.  doi: 10.1023/B:MACH.0000033113.59016.96.  Google Scholar [8] T. Duchamp and W. Stuetzle, Extremal properties of principal curves in the plane,, Ann. Statist., 24 (1996), 1511.  doi: 10.1214/aos/1032298280.  Google Scholar [9] T. Duchamp and W. Stuetzle, Geometric properties of principal curves in the plane,, in Robust Statistics, 109 (1996), 135.  doi: 10.1007/978-1-4612-2380-1_9.  Google Scholar [10] A. Fischer, Selecting the length of a principal curve within a Gaussian model,, Electron. J. Statist., 7 (2013), 342.  doi: 10.1214/13-EJS775.  Google Scholar [11] W. Gangbo and R. J. McCann, The geometry of optimal transportation,, Acta Math., (1996), 113.  doi: 10.1007/BF02392620.  Google Scholar [12] T. Hastie, Principal Curves and Surfaces,, Ph. D Thesis, (1984).   Google Scholar [13] T. Hastie and W. Stuetzle, Principal curves,, J. Amer. Statist. Assoc., 84 (1989), 502.  doi: 10.1080/01621459.1989.10478797.  Google Scholar [14] B. Kégl, Principal Curves: Learning, Design, and Applications,, Ph.D thesis, (1999).   Google Scholar [15] K. Kégl and K. Aetal, Learning and design of principal curves,, IEEE Trans. Pattern Anal. Mach. Intell., 22 (2000), 281.   Google Scholar [16] A. Lemenant, A presentation of the average distance minimizing problem,, J. Math. Sci. (N.Y.), 181 (2012), 820.  doi: 10.1007/s10958-012-0717-3.  Google Scholar [17] X. Y. Lu, Example of minimizer of the average distance problem with non closed set of corners,, Rend. Sem. Mat. Univ. Padova, ().   Google Scholar [18] X. Y. Lu and D. Slepčev, Properties of minimizers of average distance problem via discrete approximation of measures,, SIAM J. Math. Anal., 45 (2013), 3114.  doi: 10.1137/130905745.  Google Scholar [19] U. Ozertem and D. Erdogmus, Locally defined principal curves and surfaces,, J. Mach. Learn. Res., 12 (2011), 1249.   Google Scholar [20] E. Paolini and E. Stepanov, Qualitative properties of maximum and average distance minimizers in $\mathbbR^n$,, J. Math. Sci. (N.Y.), 122 (2004), 3290.  doi: 10.1023/B:JOTH.0000031022.10122.f5.  Google Scholar [21] P. Polak and G. Wolanski, The lazy traveling salesman problem in $\mathbbR^2$,, ESAIM: Control Optim. Calc. Var., 13 (2007), 538.  doi: 10.1051/cocv:2007025.  Google Scholar [22] D. Slepčev, Counterexample to regularity in average-distance problem,, Ann. Inst. H. Poincaré (C), 31 (2014), 169.  doi: 10.1016/j.anihpc.2013.02.004.  Google Scholar [23] A. J. Smola, S. Mika, B. Schölkopf and R. C. Williamson, Regularized principal manifolds,, J. Mach. Learn., 1 (2001), 179.  doi: 10.1162/15324430152748227.  Google Scholar [24] R. Tibshirani, Principal curves revisited,, Stat. Comput., 2 (1992), 183.  doi: 10.1007/BF01889678.  Google Scholar [25] C. Villani, Optimal Transport, Old and New,, Grundlehren der mathematischen Wissenschaften, (2009).  doi: 10.1007/978-3-540-71050-9.  Google Scholar
 [1] Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253 [2] Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070 [3] Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012 [4] Andrew D. Lewis. Erratum for "nonholonomic and constrained variational mechanics". Journal of Geometric Mechanics, 2020, 12 (4) : 671-675. doi: 10.3934/jgm.2020033 [5] Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020  doi: 10.3934/fods.2020017 [6] Monia Capanna, Jean C. Nakasato, Marcone C. Pereira, Julio D. Rossi. Homogenization for nonlocal problems with smooth kernels. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020385 [7] Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170 [8] José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, 2021, 20 (1) : 369-388. doi: 10.3934/cpaa.2020271 [9] Kihoon Seong. Low regularity a priori estimates for the fourth order cubic nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5437-5473. doi: 10.3934/cpaa.2020247 [10] Mengni Li. Global regularity for a class of Monge-Ampère type equations with nonzero boundary conditions. Communications on Pure & Applied Analysis, 2021, 20 (1) : 301-317. doi: 10.3934/cpaa.2020267 [11] Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019 [12] Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076 [13] Noriyoshi Fukaya. Uniqueness and nondegeneracy of ground states for nonlinear Schrödinger equations with attractive inverse-power potential. Communications on Pure & Applied Analysis, 2021, 20 (1) : 121-143. doi: 10.3934/cpaa.2020260 [14] Kai Yang. Scattering of the focusing energy-critical NLS with inverse square potential in the radial case. Communications on Pure & Applied Analysis, 2021, 20 (1) : 77-99. doi: 10.3934/cpaa.2020258 [15] Weiwei Liu, Jinliang Wang, Yuming Chen. Threshold dynamics of a delayed nonlocal reaction-diffusion cholera model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020316 [16] Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462 [17] Shao-Xia Qiao, Li-Jun Du. Propagation dynamics of nonlocal dispersal equations with inhomogeneous bistable nonlinearity. Electronic Research Archive, , () : -. doi: 10.3934/era.2020116 [18] Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251 [19] Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044 [20] Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

2019 Impact Factor: 1.053