| # Group sparsity and the -norm trick SOCP > SOC inequalities | Standard forms | Group sparsity | Applications 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) `lambda`sum( y ) ) subject to for i=1:k, y(i) >= norm(x((i-1)*p(1:p)),2); end cvx_end
| In this example we