• 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]

Abbas Moameni. Invariance properties of the Monge-Kantorovich mass transport problem. Discrete & Continuous Dynamical Systems - A, 2016, 36 (5) : 2653-2671. doi: 10.3934/dcds.2016.36.2653

[2]

Hang-Chin Lai, Jin-Chirng Lee, Shuh-Jye Chern. A variational problem and optimal control. Journal of Industrial & Management Optimization, 2011, 7 (4) : 967-975. doi: 10.3934/jimo.2011.7.967

[3]

Jesus Garcia Azorero, Juan J. Manfredi, I. Peral, Julio D. Rossi. Limits for Monge-Kantorovich mass transport problems. Communications on Pure & Applied Analysis, 2008, 7 (4) : 853-865. doi: 10.3934/cpaa.2008.7.853

[4]

Orlando Lopes. Uniqueness and radial symmetry of minimizers for a nonlocal variational problem. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2265-2282. doi: 10.3934/cpaa.2019102

[5]

Giuseppe Buttazzo, Eugene Stepanov. Transport density in Monge-Kantorovich problems with Dirichlet conditions. Discrete & Continuous Dynamical Systems - A, 2005, 12 (4) : 607-628. doi: 10.3934/dcds.2005.12.607

[6]

Zuo Quan Xu, Jia-An Yan. A note on the Monge-Kantorovich problem in the plane. Communications on Pure & Applied Analysis, 2015, 14 (2) : 517-525. doi: 10.3934/cpaa.2015.14.517

[7]

Sunra J. N. Mosconi. Optimal elliptic regularity: A comparison between local and nonlocal equations. Discrete & Continuous Dynamical Systems - S, 2018, 11 (3) : 547-559. doi: 10.3934/dcdss.2018030

[8]

Christian Léonard. A survey of the Schrödinger problem and some of its connections with optimal transport. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1533-1574. doi: 10.3934/dcds.2014.34.1533

[9]

Cédric Villani. Regularity of optimal transport and cut locus: From nonsmooth analysis to geometry to smooth analysis. Discrete & Continuous Dynamical Systems - A, 2011, 30 (2) : 559-571. doi: 10.3934/dcds.2011.30.559

[10]

Pierluigi Colli, Gianni Gilardi, Jürgen Sprekels. Distributed optimal control of a nonstandard nonlocal phase field system with double obstacle potential. Evolution Equations & Control Theory, 2017, 6 (1) : 35-58. doi: 10.3934/eect.2017003

[11]

Nassif Ghoussoub. A variational principle for nonlinear transport equations. Communications on Pure & Applied Analysis, 2005, 4 (4) : 735-742. doi: 10.3934/cpaa.2005.4.735

[12]

Qiang Du, Jingyan Zhang. Asymptotic analysis of a diffuse interface relaxation to a nonlocal optimal partition problem. Discrete & Continuous Dynamical Systems - A, 2011, 29 (4) : 1443-1461. doi: 10.3934/dcds.2011.29.1443

[13]

Giulia Cavagnari. Regularity results for a time-optimal control problem in the space of probability measures. Mathematical Control & Related Fields, 2017, 7 (2) : 213-233. doi: 10.3934/mcrf.2017007

[14]

Qinglan Xia. An application of optimal transport paths to urban transport networks. Conference Publications, 2005, 2005 (Special) : 904-910. doi: 10.3934/proc.2005.2005.904

[15]

G. Idone, A. Maugeri. Variational inequalities and a transport planning for an elastic and continuum model. Journal of Industrial & Management Optimization, 2005, 1 (1) : 81-86. doi: 10.3934/jimo.2005.1.81

[16]

Wilfrid Gangbo, Andrzej Świech. Optimal transport and large number of particles. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1397-1441. doi: 10.3934/dcds.2014.34.1397

[17]

Dario Cordero-Erausquin, Alessio Figalli. Regularity of monotone transport maps between unbounded domains. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 7101-7112. doi: 10.3934/dcds.2019297

[18]

Yupeng Li, Wuchen Li, Guo Cao. Image segmentation via $ L_1 $ Monge-Kantorovich problem. Inverse Problems & Imaging, 2019, 13 (4) : 805-826. doi: 10.3934/ipi.2019037

[19]

Xiaolong Han, Guozhen Lu. Regularity of solutions to an integral equation associated with Bessel potential. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1111-1119. doi: 10.3934/cpaa.2011.10.1111

[20]

Yan Jin, Jürgen Jost, Guofang Wang. A new nonlocal variational setting for image processing. Inverse Problems & Imaging, 2015, 9 (2) : 415-430. doi: 10.3934/ipi.2015.9.415

2018 Impact Factor: 0.871

Metrics

  • PDF downloads (11)
  • HTML views (2)
  • Cited by (0)

Other articles
by authors

[Back to Top]