I'm reading about graph sparsity and I have one problem in a paper I'm reading I don't understand, maybe someone can clarify:
Graph Sparsity:
In graph sparsity, we have a directed acyclic graph $G=(V,E)$ on the index set $I=\{1,2,...,p\}$ of the model parameter $w\in\mathbb{R}^p$, where $V=I$ is the vertex set and $E = \{(i,j)\;|\;i,j\in V\}$ is the edge set. $g$ is a path in the graph of $G$, denoted as $g=(v_1, v_2, ..., v_k)$, where $v_i \in V$, $i=1, ..., k$ and $(v_i, v_{i+1})\in E, i=1, ..., k-1$. Let $\Gamma$ be the set of all paths in the graph $G$. Denote $n_g>0$ as the positive weight of each path $g\in\Gamma$. The graph sparsity regularization is defined as follows:
$$\Omega_{Graph}(w)=\min_{J\subseteq\Gamma} \left\{ \sum_{g\in J} n_g\;s.t.\;Supp(w)\subseteq \bigcup_{g\in J} g \right\}$$
where $Supp(\cdot)$ stands for the nonzero index set of a vector. J is a subset of $\Gamma$ whose union covers the support of $w$.
My problem is understanding $Supp(w)$, what is it? It's not exactly clear to me. What does it contain exactly? A subset of indexes from $I$ such that....what? :)
I understood that we try try to find the subset of paths $J$, such that $\sum_{g\in J} n_g$ is minimized, subject to ...?
Thank you for any help =)
please comment if my questions is unclear
I think that the support ($Supp$) of $w$ are the indices of the nonzero component of $w$.
You can see $w$ as a binary vector identifying a subset of the nodes.
For example, $w=(1,-2,0,34,0,1/2)$ is identifying the set of nodes $\{1,2,4,6\}$
In the definition of sparsity regularization, you are taking the minimum weight over the subsets of path, whose union pass through all the nodes identified by $w$. It's like you're imposing that you have to pass through them.