# Matrix completion algorithm

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

For $||A_{i+1}-A_{i}||_F$ I'm getting

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

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.
• It seems that $||A_i-A_{i+1}||_F$ is still changing...so why should you stop? – AndreaCassioli May 20 '14 at 13:45
• 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$ – BRabbit27 May 20 '14 at 15:25