Learning Low Rank Matrices from O(n) Entries

Details Learning Low Rank Matrices from O(n) Entries Learning Low Rank Matrices from O(n) Entries

2008-12-14

arxiv.org/abs/0812.2599v1

Computer Science

Data Structures and Algorithms

8 pages, 11 figures, Forty-sixth Allerton Conference on Communication, Control and Computing, invited paper

Scientific paper

How many random entries of an n by m, rank r matrix are necessary to reconstruct the matrix within an accuracy d? We address this question in the case of a random matrix with bounded rank, whereby the observed entries are chosen uniformly at random. We prove that, for any d>0, C(r,d)n observations are sufficient. Finally we discuss the question of reconstructing the matrix efficiently, and demonstrate through extensive simulations that this task can be accomplished in nPoly(log n) operations, for small rank.

Affiliated with

Also associated with

No associations

Rating

Learning Low Rank Matrices from O(n) Entries 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 Learning Low Rank Matrices from O(n) Entries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning Low Rank Matrices from O(n) Entries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-249977