2
$\begingroup$

Let $L$ and $R$ be $n \times n$ matrices. Consider the following minimization problem

\begin{equation} \mathbf{L} = \min_{L \geq \mathbf{0}} \mu\|\mathbf{L}\|_* + \dfrac{1}{2\lambda}\|\mathbf{L-R}\|_F^2 \end{equation}

By $\mathbf{L}$ $\geq$ 0 , i mean that i want the entries of $\mathbf{L}$ to be non negative. I know the solution can be obtained using the singular value thresholding of $\mathbf{R}$ when the non-negativity constraint on $\mathbf{L}$ is not present. But I can't figure out the change needed in order to satisfy the non-negativity constraint on $\mathbf{L}$. Will simply setting the negative entries of $\mathbf{L}$ to zero work? I have checked this link How to solve this minimization problem involving the nuclear norm? which is about $\mathbf{L}$ being positive definite; however my question is about the entries of $\mathbf{L}$ being non-negative. Can someone please answer this?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You could use the Douglas-Rachford method, which minimizes $f(L) + g(L)$, where $f$ and $g$ are closed convex functions with proximal operators that can be evaluated efficiently. For this problem, you can take $f(L) = \mu \|L\|_*$ and $g(L) = I(L) + \frac{1}{2\lambda} \| L - R \|^2_F$, where $I(L) = 0$ if $L \geq 0$ and $I(L) = \infty$ otherwise.

$\endgroup$
4
  • $\begingroup$ And what happens when $\mathbf{f(L)}$ is not convex (weighted nuclear norm, for example)? $\endgroup$
    – sourish
    Jul 7, 2019 at 7:17
  • $\begingroup$ how to calculate the proximal of $\mathcal{g(L)}$ here? $\endgroup$
    – sourish
    Jul 8, 2019 at 3:14
  • $\begingroup$ Some recent papers have studied Douglas-Rachford for non-convex problems. I'd have to check to see what convergence results are available. But empirically, Douglas-Rachford has sometimes been observed to perform well on certain non-convex problems. $\endgroup$
    – littleO
    Jul 8, 2019 at 3:33
  • $\begingroup$ To evaluate the proximal operator of $g$, you can first write out the definition of the proximal operator explicitly, then combine the two quadratic terms by completing the square. At that point, you will see that all you need to do is set the negative entries of a particular matrix equal to zero. $\endgroup$
    – littleO
    Jul 8, 2019 at 3:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .