Regularity of densities in relaxed and penalized average distance problem

  • Received: 01 March 2014 Revised: 01 June 2015
  • Primary: 49Q20, 49K10, 49Q10, 35B65.

  • 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[J]. Networks and Heterogeneous Media, 2015, 10(4): 837-855. doi: 10.3934/nhm.2015.10.837

    Related Papers:

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


    加载中
    [1] L. Ambrosio, N. Gigli and G. Savaré, Gradient Flow in Metric Spaces and in the Space of Probability Measures, Second Editon, Lectures in Mathematics, ETH Zürich, Birkenhäuser Verlag, Basel, 2005.
    [2] G. Buttazzo, E. Mainini and E. Stepanov, Stationary configurations for the average distance functional and related problems, Control Cybernet., 38 (2009), 1107-1130.
    [3] G. Buttazzo, E. Oudet and E. Stepanov, Optimal transportation problems with free Dirichlet regions, Progr. Nonlinear Differential Equations Appl., 51 (2002), 41-65.
    [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-530. doi: 10.1137/S0036141003438313
    [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), Quaderni di Matematica, Seconda Università di Napoli, 14 (2004), 48-83.
    [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-678.
    [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-33. doi: 10.1023/B:MACH.0000033113.59016.96
    [8] T. Duchamp and W. Stuetzle, Extremal properties of principal curves in the plane, Ann. Statist., 24 (1996), 1511-1520. doi: 10.1214/aos/1032298280
    [9] T. Duchamp and W. Stuetzle, Geometric properties of principal curves in the plane, in Robust Statistics, Data Analysis, and Computer Intensive Methods Lecture Notes in Statistics (ed. H. Rieder), Springer-Verlag, 109 (1996), 135-152. doi: 10.1007/978-1-4612-2380-1_9
    [10] A. Fischer, Selecting the length of a principal curve within a Gaussian model, Electron. J. Statist., 7 (2013), 342-363. doi: 10.1214/13-EJS775
    [11] W. Gangbo and R. J. McCann, The geometry of optimal transportation, Acta Math., {\bf177} (1996), 113-161. doi: 10.1007/BF02392620
    [12] T. Hastie, Principal Curves and Surfaces, Ph. D Thesis, Stanford Univ., 1984.
    [13] T. Hastie and W. Stuetzle, Principal curves, J. Amer. Statist. Assoc., 84 (1989), 502-516. doi: 10.1080/01621459.1989.10478797
    [14] B. Kégl, Principal Curves: Learning, Design, and Applications, Ph.D thesis, Concordia Univ., 1999.
    [15] K. Kégl and K. Aetal, Learning and design of principal curves, IEEE Trans. Pattern Anal. Mach. Intell., 22 (2000), 281-297.
    [16] A. Lemenant, A presentation of the average distance minimizing problem, J. Math. Sci. (N.Y.), 181 (2012), 820-836. doi: 10.1007/s10958-012-0717-3
    [17] Rend. Sem. Mat. Univ. Padova, in press.
    [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-3131. doi: 10.1137/130905745
    [19] U. Ozertem and D. Erdogmus, Locally defined principal curves and surfaces, J. Mach. Learn. Res., 12 (2011), 1249-1286.
    [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-3309. doi: 10.1023/B:JOTH.0000031022.10122.f5
    [21] P. Polak and G. Wolanski, The lazy traveling salesman problem in $\mathbbR^2$, ESAIM: Control Optim. Calc. Var., 13 (2007), 538-552. doi: 10.1051/cocv:2007025
    [22] D. Slepčev, Counterexample to regularity in average-distance problem, Ann. Inst. H. Poincaré (C), 31 (2014), 169-184. doi: 10.1016/j.anihpc.2013.02.004
    [23] A. J. Smola, S. Mika, B. Schölkopf and R. C. Williamson, Regularized principal manifolds, J. Mach. Learn., 1 (2001), 179-209. doi: 10.1162/15324430152748227
    [24] R. Tibshirani, Principal curves revisited, Stat. Comput., 2 (1992), 183-190. doi: 10.1007/BF01889678
    [25] C. Villani, Optimal Transport, Old and New, Grundlehren der mathematischen Wissenschaften, Springer, 2009. doi: 10.1007/978-3-540-71050-9
  • Reader Comments
  • © 2015 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(3493) PDF downloads(75) Cited by(0)

Article outline

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog