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
$\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$
  • $\begingroup$ And what happens when $\mathbf{f(L)}$ is not convex (weighted nuclear norm, for example)? $\endgroup$ – sourish Jul 7 at 7:17
  • $\begingroup$ how to calculate the proximal of $\mathcal{g(L)}$ here? $\endgroup$ – sourish Jul 8 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 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 at 3:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.