5
$\begingroup$

I am trying to implement the algorithm presented in this paper which tries to recover a matrix that represent a less noisier dataset of the intensities of the pixels of a set of images. In this case the noise comes from the specularities and shadows of the material of the objects in the images.

I have little (or no) experience in convex optimization. My question is, what should the stopping criterion be in the algorithm?

I was using the $||A_{i+1}-A_{i}||_F$ where $F$ denotes the Frobenius norm and checking the difference between the current and previous recovered matrix $A$ but it results that the value of that norm remains the same iteration after iteration.

Can someone give me some advise to be able to implement the algorithm?

EDIT

After recoded the algorithm, I check both conditions as suggested in one of the answers and this is what the plots look like.

For $||E_{i+1}-E_{i}||_F$ I'm getting Difference between the norm of E

For $||A_{i+1}-A_{i}||_F$ I'm getting Difference between the norm of A

I don't know where the error could be, I went step by step over the code and it seems right to me.

$\endgroup$
1
$\begingroup$

I am not sure how this algorithm works exactly, but I guess that $||A_i-A_{i+1}||_F \leq \epsilon_A$ is a fairly reasonable stopping criterion, but also $||E_i-E_{i+1}||_F \leq \epsilon_E$ seems to be needed.

If both $||A_i-A_{i+1}||_F $ and $||E_i-E_{i+1}||_F $ do not decrease, then you are making some big mistake in the two inner loops of the algorithms.

$\endgroup$
  • $\begingroup$ I checked my implementation many times and the behavior of both norms as you suggested, you can see my edit to see what the plots look like. $\endgroup$ – BRabbit27 May 20 '14 at 10:30
  • $\begingroup$ It seems that $||A_i-A_{i+1}||_F$ is still changing...so why should you stop? $\endgroup$ – AndreaCassioli May 20 '14 at 13:45
  • $\begingroup$ Anyway, I would check the solution against a general purpose convex optimizer (as MOSEK) so to have a safe comparison and to be sure your algorithm is correct. $\endgroup$ – AndreaCassioli May 20 '14 at 13:46
  • $\begingroup$ Is there some matlab tool that can help me solve the convex optimization problem that's shown in here, namely $min_{A,E} ||A||_* + \lambda||E||_1 s.t. D = A+E$ $\endgroup$ – BRabbit27 May 20 '14 at 15:25
  • $\begingroup$ Actually, after reading the code of SVT and the code of ALM Method the authors use the ratio between the observed values and the recovered matrix. I'll try that, although, I don't know what does that mean. $\endgroup$ – BRabbit27 May 20 '14 at 16:13

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.