Paper Info
Title
A fast and efficient algorithm for low-rank approximation of a matrix
Abstract
The low-rank matrix approximation problem involves finding of a rank k version of a m x n matrix A, labeled Ak, such that Ak is as "close" as possible to the best SVD approximation version of A at the same rank level. Previous approaches approximate matrix A by non-uniformly adaptive sampling some columns (or rows) of A, hoping that this subset of columns contain enough information about A. The sub-matrix is then used for the approximation process. However, these approaches are often computationally intensive due to the complexity in the adaptive sampling. In this paper, we propose a fast and efficient algorithm which at first pre-processes matrix A in order to spread out information (energy) of every columns (or rows) of A, then randomly selects some of its columns (or rows). Finally, a rank-k approximation is generated from the row space of these selected sets. The preprocessing step is performed by uniformly randomizing signs of entries of A and transforming all columns of A by an orthonormal matrix F with existing fast implementation (e.g. Hadamard, FFT, DCT...). Our main contribution is summarized as follows. 1) We show that by uniformly selecting at random d rows of the preprocessed matrix with d = ( 1/η k max {log k, log 1/β} ), we guarantee the relative Frobenius norm error approximation: (1 + η) norm{A - Ak}F with probability at least 1 - 5β. 2) With d above, we establish a spectral norm error approximation: (2 + √2m/d) norm{A - Ak}2 with probability at least 1 - 2β. 3) The algorithm requires 2 passes over the data and runs in time (mn log d + (m+n) d2) which, as far as the best of our knowledge, is the fastest algorithm when the matrix A is dense. 4) As a bonus, applying this framework to the well-known least square approximation problem min norm{A x - b} where A ∈ Rm x r, we show that by randomly choosing d = (1/η γ r log m), the approximation solution is proportional to the optimal one with a factor of η and with extremely high probability, (1 - 6 m-γ), say.
Year
DOI
Venue
2009
10.1145/1536414.1536446
STOC
Keywords
Field
DocType
orthonormal matrix f,approximate matrix a,rank-k approximation,matrix a,approximation process,low-rank matrix approximation problem,square approximation problem min,svd approximation version,spectral norm error approximation,approximation solution,low-rank approximation,efficient algorithm,spectral norm,singular value decomposition,random matrix,low rank approximation
Singular value decomposition,Discrete mathematics,Square root of a 2 by 2 matrix,Combinatorics,Orthogonal matrix,Matrix (mathematics),Algorithm,Matrix norm,Low-rank approximation,Fast Fourier transform,Block matrix,Mathematics
Conference
ISSN
Citations 
PageRank 
0737-8017
11
1.20
References 
Authors
10
3
Name
Order
Citations
PageRank
Nam H. Nguyen123112.48
Thong T. Do223412.76
Trac D. Tran31507108.22