TY - GEN

T1 - Fast Monte-carlo low rank approximations for matrices

AU - Friedland, Shmuel

AU - Niknejad, Amir

AU - Kaveh, Mostafa

AU - Zare, Hossein

PY - 2006/12/1

Y1 - 2006/12/1

N2 - In many applications, it is of interest to approximate data, given by m × n 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 m × n 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.

AB - In many applications, it is of interest to approximate data, given by m × n 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 m × n 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.

KW - Fast k-rank approximation

KW - Monte-Carlo algorithm

KW - SVD decomposition

UR - http://www.scopus.com/inward/record.url?scp=33845962871&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33845962871&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:33845962871

SN - 1424401887

SN - 9781424401888

T3 - Proceedings 2006 IEEE/SMC International Conference on System of Systems Engineering

SP - 218

EP - 223

BT - Proceedings 2006 IEEE/SMC International Conference on System of Systems Engineering

T2 - 2006 IEEE/SMC International Conference on System of Systems Engineering

Y2 - 24 April 2006 through 26 April 2006

ER -