Monday, December 13, 2010

CS: Recovering low-rank matrices, Sparsity tracking for low rank matrix recovery from noise

John Wright or Arvind Ganesh have put together a page that compares all the research and the available codes for recovering low-rank matrices. The subject is extremely important for calibration of instruments but has many other purposes (Netflix, ...) .What I liked about the page is the comparison table at the very end, so far, reads:



Thanks John or Arvind!

This week-end, we also saw a new paper on that topic: Sparsity tracking for low rank matrix recovery from noise by Yue Deng, Qionghai Dai, Zengke Zhang. The abstract reads:

Rank-based analysis is a basic approach for many real world applications. Recently, with the developments of compressive sensing, an interesting problem was proposed to recover a lowrank matrix from sparse noise. In this paper, we will address this problem and propose a low rank matrix recovery algorithm based on sparsity tacking. The core of the proposed Sparsity Tracking Recovery(STR) is a heuristic kernel, which is introduced to penalize the noise distribution. With the heuristic method, the sparse entries in the noise matrix can be accurately tracked and discouraged to be zero. Compared with the state-of-the-art algorithm, STR could handle many tough problems and its feasible region is much larger. Besides, if the recovered rank of the matrix is low enough, it can even cope with non-sparse noise distribution.
Of interest is the potential to solve less-sparse noise problems as well.
I requested when the code would be available but I have yet to get an answer. This is exciting.

3 comments:

Anonymous said...

Hi Igor,

It looks like this paper by Hastie et al. is also addressing the same problem but not mentioned by the survey:

http://www-stat.stanford.edu/~hastie/Papers/SVD_JMLR.pdf

Anonymous said...

Actually here is a more recent work on the same topic by the same team:

http://jmlr.csail.mit.edu/papers/volume11/mazumder10a/mazumder10a.pdf

Igor said...

Olivier,
Thanks for the heads-up. The page is really different in that it was giving an up-to-date view of one and all other algorithms. But let me feature this new paper. Maybe I should start a tracking research page on the topic.

Cheers,

Igor.

Printfriendly