Accurate low-rank matrix recovery from a small number of linear measurements

Details Accurate low-rank matrix recovery from a small number of linear measurements Accurate low-rank matrix recovery from a small number of linear measurements

2009-10-02

arxiv.org/abs/0910.0413v1

Computer Science

Information Theory

8 pages, 1 table

Scientific paper

We consider the problem of recovering a lowrank matrix M from a small number of random linear measurements. A popular and useful example of this problem is matrix completion, in which the measurements reveal the values of a subset of the entries, and we wish to fill in the missing entries (this is the famous Netflix problem). When M is believed to have low rank, one would ideally try to recover M by finding the minimum-rank matrix that is consistent with the data; this is, however, problematic since this is a nonconvex problem that is, generally, intractable. Nuclear-norm minimization has been proposed as a tractable approach, and past papers have delved into the theoretical properties of nuclear-norm minimization algorithms, establishing conditions under which minimizing the nuclear norm yields the minimum rank solution. We review this spring of emerging literature and extend and refine previous theoretical results. Our focus is on providing error bounds when M is well approximated by a low-rank matrix, and when the measurements are corrupted with noise. We show that for a certain class of random linear measurements, nuclear-norm minimization provides stable recovery from a number of samples nearly at the theoretical lower limit, and enjoys order-optimal error bounds (with high probability).

Affiliated with

Also associated with

No associations

Rating

Accurate low-rank matrix recovery from a small number of linear measurements does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Accurate low-rank matrix recovery from a small number of linear measurements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accurate low-rank matrix recovery from a small number of linear measurements will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-26409