Fast Monte-Carlo Low Rank Approximations for Matrices

Details Fast Monte-Carlo Low Rank Approximations for Matrices Fast Monte-Carlo Low Rank Approximations for Matrices

2005-10-26

arxiv.org/abs/math/0510573v1

Mathematics

Numerical Analysis

Scientific paper

In many applications, it is of interest to approximate data, given by mxn matrix A, by a matrix B of at most rank k, which is much smaller than m and n. The best approximation is given by singular value decomposition, which is too time consuming for very large m and n. We present here a Monte Carlo algorithm for iteratively computing a k-rank approximation to the data consisting of mxn matrix A. Each iteration involves the reading of O(k) of columns or rows of A. The complexity of our algorithm is O(kmn). Our algorithm, distinguished from other known algorithms, guarantees that each iteration is a better k-rank approximation than the previous iteration. We believe that this algorithm will have many applications in data mining, data storage and data analysis.

Affiliated with

Also associated with

No associations

Rating

Fast Monte-Carlo Low Rank Approximations for Matrices 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 Fast Monte-Carlo Low Rank Approximations for Matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Monte-Carlo Low Rank Approximations for Matrices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-555799