# 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. 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 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]$$. 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. Jul 2 '15 at 2:07
• Thanks, how does the solution change? Jul 2 '15 at 3:01

Generally you can solve any problem of the kind $$$$\min f(x) + g(x)$$$$ where $$f$$ is a lipschitz-differentiable convex function and $$g$$ is just a convex function by using proximal gradient descent (See N. Parikh and S. Boyd - Proximal Algorithms for details).
$$\mathcal{L}_\lambda$$ is the proximity operator of $$\lambda \|.\|_*$$ so proximal gradient descent you simply get: $$$$X_{n+1} = \mathcal{L}_{\gamma \lambda_*} (X_n - \gamma(\mathbb{W}^* \mathbb{W} X_n - \mathbb{W}^* B))$$$$ 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).