Grouped penalty for undirected graphs

1

Please help. I am trying to use CVX to solve this problem with respect to \alpha, a p \times 1 vector:

minimize \sum_{i \sim j}\left(\frac{|\alpha_{i}|^{\gamma}}{w_{i}}+ \frac{|\alpha_{j}|^{\gamma}}{w_{j}}\right)^{1/\gamma} + \lambda\|\alpha\|_{1}

where i \sim j means nodes i and j are connected in a graph, and 1 \leq \gamma \leq \infty. Thank you.

How can I write this in CVX especially the first term.

Thank you.

2

What are the possible ranges of \gamma?

3

1 \leq \gamma \leq \infty. Thank you.

4

I would probably do something like this. Let’s assume ij is an N\times 2 vector containing the indices of the connected notes. That is, ij(1,1) is connected to ij(1,2), ij(2,1) is connected to ij(2,2), etc. Let’s also assume that w is a vector of the weights.

Then you can do this:

cvx_begin
    variable alpha(n)
    alpha_w = alpha ./ w .^ (1/gamma);
    accum = 0;
    for k = 1 : size(ij,1),
        accum = accum + norm(alpha_w(ij(k,:)),gamma);
    end
    minimize(accum+lambda*norm(alpha,1))
cvx_end
5

Thanks mcg. I have a follow up question. Suppose \alpha is p \times 1, ij is 3 \times 2 with entries [1 2; 1 3 ;1 4] so that 1\sim 2 , 1 \sim 3 and 1 \sim 4,hence nodes 5:p are not connected to any node, and thus will have zero weights. Here, alpha/w in alpha_w will not exist.

6

Well, you’ll have to modify my code to take that into account then. CVX won’t permit division by zero. Why not just set the weights of the unconnected nodes to 1? It’s not like they will ever be seen.

7

Thanks mcg. I thought so too. You’ve been helpful.