# Least-squares with nuclear norm regularization

Let $$L$$ and $$R$$ be $$n \times n$$ matrices. I am trying to solve the following regularized least-squares problem

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

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 please tell me the way?

• Search for "singular value thresholding". See math.stackexchange.com/questions/1231015/…
– p.s.
May 25, 2017 at 12:33
• Short answer: compute the singular value decomposition $R=U\Sigma V^T$, then $L=U(\Sigma-\lambda \mu I)_+ V^T$.
– p.s.
May 25, 2017 at 13:02
• 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? May 26, 2017 at 4:47
• Isn't the nuclear norm of a symmetric PSD matrix just its trace? Mar 31 at 10:58

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 }

• Thank you for answering my question! It's clear explanation! May 29, 2017 at 3:09
• 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? Jun 2, 2017 at 9:49
• Great derivation. In general it is math.stackexchange.com/a/2444238/33.
– Royi
Sep 25, 2017 at 8:21