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)?

  • $\begingroup$ Can you define in the question what the $\|\cdot\|_{2,1}$ notation represents? $\endgroup$ – D.W. Jan 25 '18 at 8:13
  • $\begingroup$ 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)$). $\endgroup$ – breezeintopl Jan 25 '18 at 19:00
  • $\begingroup$ Are you sure you're not supposed to take the square of the norm? $\endgroup$ – Nicholas Mancuso Jan 30 '18 at 7:11
  • $\begingroup$ 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. $\endgroup$ – csTheoryBeginner Jan 31 '18 at 0:21
  • $\begingroup$ @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. $\endgroup$ – breezeintopl Jan 31 '18 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.