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?


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.


1 Answer 1


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.

  • $\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, 2014 at 10:30
  • $\begingroup$ It seems that $||A_i-A_{i+1}||_F$ is still changing...so why should you stop? $\endgroup$ May 20, 2014 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$ May 20, 2014 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, 2014 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, 2014 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.