Average-distance problem for parameterized curves

Lu, Xin Yang; Slepčev, Dejan

ESAIM: Control, Optimisation and Calculus of Variations, Tome 22 (2016) no. 2, pp. 404-416.

We consider approximating a measure by a parameterized curve subject to length penalization. That is for a given finite compactly supported measure $\mu$, with $\mu \left({ℝ}^d\right)>0$ for $p\ge 1$ and $\lambda >0$ we consider the functional

$$E\left(\right)={\int }_{{ℝ}^d}d{(x,{\Gamma }_{\gamma })}^p\mathrm{d}\mu \left(x\right)+\lambda \text{Length}\left(\gamma \right)$$

where $\gamma :I\to {ℝ}^d$, $I$ is an interval in $ℝ$, $\Gamma {}_{\gamma }=\gamma \left(I\right)$, and $d(x,\Gamma {}_{\gamma })$ is the distance of $x$ to $\Gamma {}_{\gamma }$. The problem is closely related to the average-distance problem, where the admissible class are the connected sets of finite Hausdorff measure ${\mathscr{H}}^1$, and to (regularized) principal curves studied in statistics. We obtain regularity of minimizers in the form of estimates on the total curvature of the minimizers. We prove that for measures $\mu$ supported in two dimensions the minimizing curve is injective if $p\ge 2$ or if $\mu$ has bounded density. This establishes that the minimization over parameterized curves is equivalent to minimizing over embedded curves and thus confirms that the problem has a geometric interpretation.

H. Brézis, Functional Analysis, Sobolev Spaces and Partial Differential Equations. Universitext, Springer (2011). | MR | Zbl

G. Buttazzo, A. Pratelli and E. Stepanov, Optimal pricing policies for public transportation networks. SIAM J. Optimiz. 16 (2006) 826–853. | DOI | MR | Zbl

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. | Numdam | MR | Zbl

G. Buttazzo and E. Stepanov, Minimization Problems for Average Distance Functionals. In vol. 14 of Calculus of Variations; Topics from the Mathematical Heritage of Ennio De Giorgi, edited by D. Pallara. Quaderni di Matematica, Caserta (2004) 47–83. | MR | Zbl

G. Buttazzo and F. Santambrogio, A Model for the Optimal Planning of an Urban Area. SIAM J. Math. Anal. 37 (2005) 514–530. | DOI | MR | Zbl

G. Buttazzo and F. Santambrogio, A Mass Transportation Model for the Optimal Planning of an Urban Region. SIAM Rev. 51 (2009) 593–610. | DOI | MR | Zbl

G. Buttazzo, E. Oudet and E. Stepanov, Optimal transportation problems with free Dirichlet regions. Prog. Nonlinear Differ. Eq. Appl. 51 (2002) 41–65. | MR | Zbl

G. Buttazzo, E. Mainini and E. Stepanov, Stationary configurations for the average distance functional and related problems. Control Cybernet. 38 (2009) 1107–1130. | MR | Zbl

G. Buttazzo, A. Pratelli, S. Solimini and E. Stepanov, Optimal Urban Networks Via Mass Transportation. Springer Lect. Notes Math. (2009). | MR | Zbl

T. Duchamp and W. Stuetzle, Geometric Properties of Principal Curves in the Plane, in vol. 109 of Robust Statistics, Data Analysis, and Computer Intensive Methods, edited by H. Rieder. Springer-Verlag, Berlin (1995) 135–152. | MR | Zbl

E.N. Gilbert and H.O. Pollack, Steiner minimal trees. SIAM J. Appl. Math. 12 (1968) 1–29. | DOI | MR | Zbl

T. Hastie, Principal curves and surfaces. Ph.D. thesis, Stanford University (1984). | MR

T. Hastie and W. Stuetzle, Principal curves. J. Amer. Statist. Assoc. 84 (1989) 502–516. | DOI | MR | Zbl

F.K. Hwang, D.S. Richards and P. Winter, The Steiner tree problem in Ann. Discrete Math. North-Holland Publishing Co., Amsterdam (1992). | MR | Zbl

B. Kégl, A. Krzyzak, T. Linder, and K. Zeger, Learning and design of principal curves. IEEE Trans. Pattern Anal. Mach. Intell. 22 (2000) 281–297. | DOI

A. Lemenant, A presentation of the average distance minimizing problem. Zap. Nauchn. Sem. S.-Petersburg. Otdel. Mat. Inst. Steklov. POMI 390 (2011). Translation in: J. Math. Sci. 181 (2012) 820-836. | MR | Zbl

A. Lemenant, About the regularity of average distance minimizers in $R^2$. J. Convex Anal. 18 (2011) 949-981. | MR | Zbl

G. Leoni, A first course in Sobolev spaces. Grad. Stud. Math. AMS, Providence (2009). | MR | Zbl

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 | MR | Zbl

C. Mantegazza and A. Mennucci, Hamilton-Jacobi equations and distance functions in Riemannian manifolds. Appl. Math. Optim. 47 (2003) 1–25. | DOI | MR | Zbl

E. Paolini and E. Stepanov, Qualitative properties of maximum and average distance minimizers in ${ℝ}^n$. J. Math. Sci. 122 (2004) 3290–3309. | DOI | MR | Zbl

F. Santambrogio and P. Tilli, Blow-up of optimal sets in the irrigation problem. J. Geom. Anal. 15 (2005) 343–362. | DOI | MR | Zbl

D. Slepčev, Counterexample to regularity in average-distance problem. Ann. Inst. Henri Poincaré (C) 31 (2014) 169–184. | DOI | Numdam | MR | Zbl

A.J. Smola, S. Mika, B. Schölkopf and R.C. Williamson, Regularized principal manifolds. J. Mach. Learn. 1 (2001) 179–209. | MR | Zbl

R. Tibshirani, Principal curves revisited. Stat. Comput. 2 (1992) 183–190. | DOI