How do I minimize $||L||_* + \lambda ||S||_1$

Question

Assume that we got a $n * m$ picture called $X$ and $X$ contains the noise picture $S$. $X - S = L$ where $L$ is the clean filtered ideal picture and $X = L + S$ is the real picture taken by camera.

I want to minimize $$||L||_* + \lambda ||S||_1$$ With the subject to: $$X = L + S$$

Where $||L||_*$ is the Nuclear norm (Sum of singular values) and $||S||_1$ is the L1-norm (Sum of absolute values) and $\lambda$ is just a tuning parameter e.g a number.

Questions:

1. What method should I use to solve this optimization problem?
2. What algorithm should I use with that method?
3. Can I solve this using least squares?
4. Can I solve this with linear programming e.g simplex method?
5. Can I solve this with dynamic programming?

I assume that this is a quadratic programming problem because we got two matrices to work with, $L$ and $S$.

Answer 1

What method should I use to solve this optimization problem? What algorithm should I use with that method?

Your problem is a non-smooth convex optimization problem that would typically be solved using a first-order method such as ADMM.

Since the objective function involves the nuclear norm of a nonsymmetric matrix you will have to compute SVD's during the solution of the problem. The subgradient and prox operator for the nuclear norm term can both be computed from the SVD.

Can I solve this using least squares?

No.

Can I solve this with linear programming e.g simplex method?

No.

Can I solve this with dynamic programming?

I don't believe so.