Group sparsity and the -norm trick
Group sparsity problem
The -norm heuristic
Group sparsity problem
In many applications, such as image annotation, we would like to encourage the occurrences of whole blocks of zeros in the decision vector. Assume for example that the decision vector is partitioned into two disjoint groups , with , , with . We seek to minimize the number of non-zero blocks , while satisfying some constraint, say , with a given polytope.
The -norm heuristic
We can use the -norm trick on the vector of Euclidean norms . (This will encourage many of the blocks to be zero; those blocks that are not zero will not, in general, be sparse.)
This leads to the problem
The above is a second-order cone program. This is easily seen after introducing a new vector variable
The following CVX snippets actually uses the above representation for the least-squares problem with a block-norm penalty:
In our implementation we assume that each block is of the same length .
CVX code
cvx_begin
variable x(n);
variable y(k);
minimize( norm(Ax-b,2) lambdasum( y ) )
subject to
for i=1:k,
y(i) >= norm(x((i-1)*p(1:p)),2);
end
cvx_end
|
In this example we
|
|