Let $G$ be a graph of $n$ arcs and let $x\in \mathbb{R}^n$. I want to compute the orthogonal projection of $x$ onto the set of radial graphs with $k$ roots contained in $G$ (or a forest with $k$ root) i.e. $$\Pi \left( x\right) =\underset{y\in S}{\arg \min }\left\Vert x-y\right\Vert
^{2},$$
where $S$ is the underlying set.


My question is: how is this projection linked to the minimal spanning trees?
I really appreciate any help you can provide.



Minimum spanning tree and projection
I think you mean that $y$ is the characteristic vector. That is, $y\_{ij}=1$ if edge $(i,j)$ is in the forest and $0$ otherwise. Let $E$ be the edge set of $G$. Given $x$, you want to find $y$ to minimize
$$
\sum\_{(i,j)\in E} (x\_{ij}-y\_{ij})^2
= \sum\_{(i,j)\in E} (x\_{ij}^2-2x\_{ij}y\_{ij}+y\_{ij}^2)
= \sum\_{(i,j)\in E} x\_{ij}^2 + \sum\_{(i,j)\in E} (1-2x\_{ij})y\_{ij},
$$
which is equivalent to minimizing
$$\sum\_{(i,j)\in E} (1-2x\_{ij})y\_{ij},$$
which is the objective function for the problem of finding a minimum forest with edge weights $1-2x\_{ij}$.


