About the convexity of distance metrc problems.

175 Views Asked by At

Suppose that we consider a pseudo-distance in $\mathbb{R}^n$ (so we admit that different points can have zero distance between them) that comes from a dot product. It is known that these distances always are determined by a positive semidefinite matrix $M$, so that $d_M(x,y)^2 = (x-y)^TM(x-y)$, for $x,y \in \mathbb{R}^n$.

It is also known, because of Cholesky factorization, that $M$ can be decomposed in the form $L^TL$, where $L$ is a linear map, so that $d_M(x,y)^2 = \|L(x-y)\|^2$, where $\|\cdot\|$ denotes the euclidean norm. And also, from $L$ we can obtain the matrix $M$ which produces the same distance. So we can also represent every distance in terms of a linear application $L$, and in this case we denote the distance by $d^L(x,y)$.

Suppose now that we fix $x,y \in \mathbb{R}^n$ and consider the functions $L \mapsto d^L(x,y)^2$ and $M \mapsto d_M(x,y)^2$. Both functions have the same image, but what can we say about the convexity of each one? Furthermore, some articles about machine learning consider functions in $L$ or $M$ that are sums of distances in different pairs of points, and they assure that the function in $M$ is convex, but the function in $L$ is not. How can this be shown in general problems in this form? Thanks in advance.

Edit: About the last question asked, can someone show me examples of functions that depend of a distance and that are convex in $M$ but not in $L$?