1
$\begingroup$

Let $L$ and $R$ be $n \times n$ matrices. I am trying to solve the following minimization problem

$$ L^{k+1} := \arg \min_{L} \lambda \|L\|_{\ast} + \frac{1}{2\mu}\|L-R^{k}\|_{F}^{2} $$ $$ \mbox{s.t.}\ L \succeq 0 $$

where $\|\cdot\|_{\ast}$ and $\|\cdot\|_{F}$ denote the nuclear and Frobenius norms, respectively. Also, $k$ expresses the $k$th iteration when solving an optimization problem successively.

I don't know how to solve this problem. Would you tell me the way?

$\endgroup$
  • $\begingroup$ Search for "singular value thresholding". See math.stackexchange.com/questions/1231015/… $\endgroup$ – p.s. May 25 '17 at 12:33
  • $\begingroup$ Short answer: compute the singular value decomposition $R=U\Sigma V^T$, then $L=U(\Sigma-\lambda \mu I)_+ V^T$. $\endgroup$ – p.s. May 25 '17 at 13:02
  • $\begingroup$ Thank you. The derivation is that 1) differentiate the objective function with $L$, 2) let $X\Delta Y$ be singular value decomposition, replace $X$ and $Y$ with $U$ and $V$ since the derivative of $||L||_{\ast}$ is $XY$ and the objective function has $||L-R||_{F}^{2}$, right? $\endgroup$ – Tomoki Matsumoto May 26 '17 at 4:47
1
$\begingroup$

To flesh out the comment by p.s.

Assume that we know the SVD of $L$ $$L=USV^T$$

Write down the objective function, then its differential and gradient $$\eqalign{ f &= \lambda\|L\|_* + \frac{1}{2\mu}\|L-R\|_F^2 \cr df &= \Big(\lambda\,UV^T + \frac{1}{\mu}(L-R)\Big):dL \cr \frac{\partial f}{\partial L} &= \lambda\,UV^T + \frac{1}{\mu}(USV^T-R) \cr\cr }$$ Set the gradient to zero and solve for $R$ $$\eqalign{ R &= \mu\lambda\,UV^T + USV^T \cr &= U(\mu\lambda\,I + S)V^T \cr &= U\Sigma V^T \cr }$$ So it appears that by perturbing the singular values, we arrive at the SVD of $R$.

Working backwards, let's start with the SVD of $R$ and find $L$. $$\eqalign{ \mu\lambda\,I + S &= \Sigma \implies S = \Sigma - \mu\lambda\,I \cr L &= USV^T = U(\Sigma - \mu\lambda\,I)V^T \cr\cr }$$ One last detail is to ensure that the singular values are restricted to non-negative values. $$\eqalign{ L &= U\,(\Sigma - \mu\lambda\,I)_+\,V^T \cr\cr }$$

$\endgroup$
  • $\begingroup$ Thank you for answering my question! It's clear explanation! $\endgroup$ – Tomoki Matsumoto May 29 '17 at 3:09
  • $\begingroup$ If the condition is that $−L\succeq 0$ instead of that $L\succeq 0$, how the answer changes? I think that $L=-U(\mu\lambda I - \Sigma)_{+}V^{\ast}$. Is it true? $\endgroup$ – Tomoki Matsumoto Jun 2 '17 at 9:49
  • $\begingroup$ Great derivation. In general it is math.stackexchange.com/a/2444238/33. $\endgroup$ – Royi Sep 25 '17 at 8:21

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.