1
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ Can you define in the question what the $\|\cdot\|_{2,1}$ notation represents? $\endgroup$
    – D.W. ♦
    Commented Jan 25, 2018 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
    Commented Jan 25, 2018 at 19:00
  • $\begingroup$ Are you sure you're not supposed to take the square of the norm? $\endgroup$
    – Nicholas Mancuso
    Commented Jan 30, 2018 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
    Commented Jan 31, 2018 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
    Commented Jan 31, 2018 at 16:17

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.