How to solve L2,p mixed-norm minimization by CVX?

1

If I want to solve the L2,1 mixed-norm minimization, I can first calculate the L2-norm and then use the sum().
But when I solve the L2,p mixed-norm minimization, I cannot use norms(…, p) in the objective function. How can I solve this problem?

2

Presuming, the 2 is across the rows, the L2,p norm to the pth power of the matrix X would be
sum(pow_pos(norms(X),p))

If that is the only term in the objective function, that will suffice, because the omitted ^(1/p) is not needed.

3

Thank you.
Yes, the 2 is across the rows.
However, the objective function includes other terms, so this ^(1/p) is inevitable.

\underset{\mathbf{X}}{min} \left(\parallel \mathbf{Y} - \mathbf{AX} \parallel\right)_{F}^{2} + \lambda \left(\parallel \mathbf{X} \parallel\right)_{2 , p}
4

Do you have a (DCP) constructive convexity proof of L2,p norm for p other than 1 or infinity?

5

If none of the conic reformulation wizards can figure this out, the L2,p norm for 1 < p < \infty, is a candidate for @Erling’s challenge.

Is there some way of doing it with a combination of power cone (or geo_mean) and some other cone?

The L2,1 and L2,inf norms can be handled respectively as sum(norms(X)) and max(norms(X)) .

6

CVXPY has a function Other Atoms - mixed_norm, I would think CVX should allow norm(norms(X),p) but I couldn’t get it to work. Splitting it in two should do it as everything is convex and monotone in the right way:

t >= norm(u, p)
u >= norms(X)

Note that if p has a large representation/approximation as a rational number a/b (ie. it is not something simple like 3/2 or 5/3) then the conic representation generated by CVX will have many quadratic cones and at some point you might prefer to use a solver which supports the power cone directly and implement the l_p norm using that.

1 Like
7

Thanks @Michal_Adamaszek .

CVX requires the argument of norm to be affine. Not all of your knowledge is infused into CVX. CVX 3.0 is a little smarter (sign-dependent curvature), but I don’t think it could handle this directly either; but in any event, it is riddled with bugs, so should not be used.

help cvx/norm

Disciplined convex programming information:
    norm is convex, except when P<1, so an error will result if
    these non-convex "norms" are used within CVX expressions. norm 
    is nonmonotonic, so its input must be affine.