# suggestion for optimization problem with $\ell_{2,1}$ norm and Frobenius norm

Suppose I derive my application problem as the following type of optimization problem: $$\min_X ||X||_{2,1}+||X^\top||_{2,1}+||X-A||_F,$$ where $X$ is a (square) matrix, $A$ is a constant matrix.

I am wondering is there any current optimization algorithm can solve this optimization problem (better with some convergence or theoretical guarantee)?

• Can you define in the question what the $\|\cdot\|_{2,1}$ notation represents? – D.W. Jan 25 '18 at 8:13
• It is the $\ell_{2,1}$ matrix norm. It is just the $\ell_2$ norm of each column vector, and then sum them up. $||X||_F$ is just the $\ell_2$ norm of matrix $X$ viewed as a long vector ($vec(X)$). – breezeintopl Jan 25 '18 at 19:00
• Are you sure you're not supposed to take the square of the norm? – Nicholas Mancuso Jan 30 '18 at 7:11
• Being an unconstrained minimization, I would try Coordinate descent. The updates in the algorithm in your case will have a very simple expression w.r.t each variable. As far as theoretical guarantees go, it is a first order method. – csTheoryBeginner Jan 31 '18 at 0:21
• @NicholasMancuso I think the Frobenius norm is already square root of the sum of squares, and the $2$ in $\ell_{2,1}$ is also the square root. – breezeintopl Jan 31 '18 at 16:17