0
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ So this is a very difficult problem and involves heavy math? $\endgroup$
    – DanM
    Feb 9, 2021 at 2:08
  • $\begingroup$ In terms of computational complexity it's not that bad, but one would need to be reasonably familiar with convex optimization to write a code to solve the problem. The SVD is a standard function of many computational libraries- you wouldn't need to code that yourself. $\endgroup$ Feb 9, 2021 at 3:05
  • $\begingroup$ In terms of difficulty, this might be a reasonable homework assignment in a graduate-level course on convex optimization. It would be a bit too simple for an MS thesis. $\endgroup$ Feb 9, 2021 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.