Exact LowRank Matrix Completion from Sparsely Cor

Authors: Ming Yan Yi Yang Stanley Osher

Publish Date: 2013/01/26

Volume: 56, Issue: 3, Pages: 433-449

PDF Link

Abstract

Recovering a lowrank matrix from some of its linear measurements is a popular problem in many areas of science and engineering One special case of it is the matrix completion problem where we need to reconstruct a lowrank matrix from incomplete samples of its entries A lot of efficient algorithms have been proposed to solve this problem and they perform well when Gaussian noise with a small variance is added to the given data But they can not deal with the sparse randomvalued noise in the measurements In this paper we propose a robust method for recovering the lowrank matrix with adaptive outlier pursuit when part of the measurements are damaged by outliers This method will detect the positions where the data is completely ruined and recover the matrix using correct measurements Numerical experiments show the accuracy of noise detection and high performance of matrix completion for our algorithms compared with other algorithmsWhen we overestimate K the K outliers will be found to make the objective function 0 Therefore we only need to consider the pK correct entries In the mean time some nonoutliers the overestimated varDelta K entries are also considered as outliers and will not be used for MC As we know if the number of given entries in one row or column is less than r the reconstructed matrix is not unique Since varDelta K of the pK known entries will not be used in reconstructing the matrix when varDelta K is large enough to make the number of known entries in one row or column less than r we will have more than one solution It is easily seen that the smallest number of known entries in one row or column of the matrix is less than or equal to lfloor pK/mrfloor or lfloor pK/nrfloor here lfloor xrfloor is the largest integer that does not exceed x Without loss of generality let us assume column j has the smallest number of known entries It is obvious that this number is bounded by min lfloor pK/mrfloor lfloor pK/nrfloor To make the number of known entries in this column no less than r the smallest number of entries to be deleted should not exceed min lfloor pK/mrfloor lfloor pK/nrfloor r+1 Thus if varDelta K is greater than min lfloor pK/mrfloor lfloor pK/nrfloor r the reconstructed matrix will not be unique

Keywords: