A random algorithm for low-rank decomposition of large-scale matrices with missing entries
A Random SubMatrix method (RSM) is proposed to calculate the low-rank decomposition of large-scale matrices with known entry percentage \rho. RSM is very fast as the floating-point operations (flops) required are compared favorably with the state-of-the-art algorithms. Meanwhile RSM is very memory-saving. With known entries homogeneously distributed in the given matrix, sub-matrices formed by known entries are randomly selected. According to the just proved theorem that subspace related to smaller singular values is less perturbed by noise, the null vectors or the right singular vectors associated with the minor singular values are calculated for each submatrix. The vectors are the null vectors of the corresponding submatrix in the ground truth of the given large-scale matrix. If enough sub-matrices are randomly chosen, the low-rank decomposition is estimated. The experimental results on random synthetical matrices with sizes such as 131072X1024 and on real data sets indicate that RSM is much faster and memory-saving, and, meanwhile, has considerable high precision achieving or approximating to the best.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions
Low-rank Tucker and CP tensor decompositions are powerful tools in data analytics. The widely used alternating least squares (ALS) method, which solves a sequence of over-determined least squares subproblems, is costly f…
Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms
Tensor rank and low-rank tensor decompositions have many applications in learning and complexity theory. Most known algorithms use unfoldings of tensors and can only handle rank up to $n^{\lfloor p/2 \rfloor}$ for a $p$-…
Tensor DecompositionHigh Dimensional Low Rank plus Sparse Matrix Decomposition
This paper is concerned with the problem of low rank plus sparse matrix decomposition for big data. Conventional algorithms for matrix decomposition use the entire data to extract the low-rank and sparse components, and …
ClusteringSmall Data Image ClassificationVocal Bursts Intensity PredictionRandomized Online CP Decomposition
CANDECOMP/PARAFAC (CP) decomposition has been widely used to deal with multi-way data. For real-time or large-scale tensors, based on the ideas of randomized-sampling CP decomposition algorithm and online CP decompositio…
Randomized Tensor Ring Decomposition and Its Application to Large-scale Data Reconstruction
Dimensionality reduction is an essential technique for multi-way large-scale data, i.e., tensor. Tensor ring (TR) decomposition has become popular due to its high representation ability and flexibility. However, the trad…
Dimensionality ReductionImage Reconstruction