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$?

  • $\begingroup$ The epigraph of the $M$-function is given by a constraint linear in the entries of $M$. The epigraph of the $L$-function is given by a second-order cone constraint in the entries of $L$. Hence both are convex. $\endgroup$ – Michal Adamaszek May 17 '18 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.