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

  • 1
    $\begingroup$ It would help to know whether $X$ is a vector or scalar, what $vec(X)$ means, and what $\lambda_*$ and $|| X||_*$ mean. $\endgroup$
    – Michael
    Commented Jul 1, 2015 at 21:06
  • $\begingroup$ 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 $\endgroup$
    – Michael
    Commented Jul 1, 2015 at 21:47
  • $\begingroup$ 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]$$. $\endgroup$
    – Michael
    Commented Jul 1, 2015 at 23:02
  • 1
    $\begingroup$ It can still be solved with soft thresholding. It's the gradient step that changes, not the proximal step. $\endgroup$ Commented Jul 2, 2015 at 2:07
  • $\begingroup$ Thanks, how does the solution change? $\endgroup$
    – Michael
    Commented Jul 2, 2015 at 3:01

1 Answer 1


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 (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: \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).

I'm not too sure how this would translate using your notations but it should not be too hard to implement anyway.

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).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .