Regularized Least Squares Using the Nuclear Norm

I have the following least squares nuclear norm problem,

$$\min_{\bf X} \frac{1}{2}{\left\lVert {\bf b} - {{\bf W}}vec({\bf X}) \right\rVert}^2_2 + {\lambda_*}\Arrowvert {\bf X} \Arrowvert_*$$ where ${\bf W}$ is a diagonal weight matrix,

$$\begin{bmatrix} w_{1} & 0 & \ldots & 0\\ 0 & w_2 & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 &\ldots & w_n \end{bmatrix}$$

I know that for ${\bf W} = {\bf I}$ the problem is solved via the singular soft-thresholding operator,

$$\min_{\bf X} \frac{1}{2}{\left\lVert {\bf B} - {\bf X} \right\rVert}^2_F + \lambda_*{\Arrowvert{{\bf X}}\Arrowvert_*}\\ {\hat {\bf X}} = \mathcal{L}_{\lambda_*}({\bf B}) = {\bf U}_{\bf B}\mathcal{S}_{\lambda_*}({\bf \Sigma}_{{\bf B}}){\bf V}_{\bf B}^T$$ When ${\bf W}$ its not identity, however, can I solve it as,

$${\hat {\bf X}} = \mathcal{L}_{\lambda_*}\big(T_M({{\bf W}^{-1}\bf b})\big),$$ where $T_M$ is an operator that transforms its vector argument into a matrix of appropriate size

• It would help to know whether $X$ is a vector or scalar, what $vec(X)$ means, and what $\lambda_*$ and $|| X||_*$ mean. – Michael Jul 1 '15 at 21:06
• Thanks for your reply. X is a matrix and vec(X) is the vectorized form of X (column-wise). $\lambda_*$ > 0 is a regularization parameter and $||X||_*$ is the nuclear norm of X. Also there is relation between b=vec(B). Thanks a lot – Michael Jul 1 '15 at 21:47
• Okay, so I think the objective is $$\min_{(x_{ij})} \left[ \frac{1}{2}\sum_{ij}(b_{ij}-w_{ij}x_{ij})^2 + \lambda_* ||(x_{ij})||_* \right]$$. – Michael Jul 1 '15 at 23:02
• It can still be solved with soft thresholding. It's the gradient step that changes, not the proximal step. – Michael Grant Jul 2 '15 at 2:07
• Thanks, how does the solution change? – Michael Jul 2 '15 at 3:01

Generally you can solve any problem of the kind \begin{equation} \min f(x) + g(x) \end{equation} where $f$ is a lipschitz-differentiable convex function and $g$ is just a convex function by using proximal gradient descent (that's already the algorithm you're using. https://web.stanford.edu/~boyd/papers/prox_algs.html for details).
$\mathcal{L}_\lambda$ is the proximity operator of $\lambda \|.\|_*$ so proximal gradient descent you simply get: \begin{equation} X_{n+1} = \mathcal{L}_{\gamma \lambda_*} (X_n - \gamma(\mathbb{W}^* \mathbb{W} X_n - \mathbb{W}^* B)) \end{equation} noting $\mathbb{W} : (X_{i,j}) \mapsto (w_{i,j} X_{i,j})$ and $\mathbb{W}^*$ its adjunct. $\gamma$ is a stepsize, ideally $\left(\frac{1}{\max w_{i,j}}\right)^2$ (the inverse of lispchitz constant of the gradient).
Note that there are faster ways to do it using the accelerated proximal gradient descent (same link), which you should do if you intend to use your algorithm on large matrices (computing $\mathcal{L}$ takes ages).