The source codes are transfered to THU-numbda (https://github.com/THU-numbda/randQB_auto).
Randomized QB factorization for fixed-precision low-rank matrix approximation.
This package includes Matlab codes for the randQB_EI and randQB_FP algorithms. They are efficient randomized algorithms for the fixed-precision low-rank matrix approximation. The test cases and scripts for running the experiments in paper "Efficient randomized algorithms for the fixed-precision low-rank matrix approximation" by Wenjian Yu, Yu Gu and Yaohang Li, are also included.
- Main algorithms
randQB_EI_auto.m -- fixed-precision version of the randQB_EI algorithm
randQB_FP_auto.m -- fixed-precision version of the randQB_EI algorithm
randQB_EI_k.m -- fixed-rank version of the randQB_EI algorithm
randQB_FP_k.m -- fixed-rank version of the randQB_EI algorithm
randQB_FP_svd.m -- compute rank-k truncated SVD with the randQB_FP algorithm
- Auxiliary algorithms for comparison
basicQB.m -- the basic randQB algorithm (fixed-rank) in [1]
randQB_b_k.m -- the blocked randQB algorithm (fixed-rank) in [2]
AdpRangeFinder.m -- adaptive randomized range finder algorithm (fixed-precision) [1]
singlePass2011.m -- the single-pass algorithm in [1]
singlePass2011_svd.m -- compute rank-k truncated SVD with the single-pass algorithm in [1]
basicQB_svd.m -- compute rank-k truncated SVD with the basic randQB algorithm [1]
SVD_errors.m -- compute the optimal rank-k approximation error with SVD.
- Test data and codes
genTestMatrix.m -- generate the three dense test matrices (Matrix 1/2/3).
gen_rand_mat_exp_decay.m -- generate a matrix with singular value decay exponentially.
image1.jpg -- A scenic image
Aminer100K_matrix.zip -- A keyword-person matrix (in COO format) from "AMiner" (Please unzip it)
Aminer100K_s.mat -- Accurate singular values of Aminer100K matrix (obtained with SVD)
- Experiment scripts.
EIplot.m -- For validating the error indicator in randQB_EI. Also draw Fig. 2 in [3].
CompSinglePass_Plot.m -- Compare different single-pass algorithms. Draw Fig. 8/9 in [3].
DrawSinglarValue.m -- Needed by CompSinglePass_Plot.m
DrawApproxError.m -- Needed by CompSinglePass_Plot.m
test4fixedprecision.m -- Validate the algorithms for fixed-precision computation.
readImage.m -- Convert an image to a matrix.
loadAminerMatrix.m -- Load the Aminer matrix.
For comment/question/suggestion, please send email to yu-wj at tsinghua dot edu dot cn (Dr. Wenjian Yu).
Reference
[1] N. Halko, P.-G. Martinsson and J. A. Tropp, "Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions," SIAM Review, 53 (2011), no. 2, pp. 217{288.
[2] P.-G. Martinsson and S. Voronin, "A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices," SIAM J. Sci. Comput., 38(2016), no. 5, pp. S485 - S507.
[3] Wenjian Yu, Yu Gu and Yaohang Li, "Efficient randomized algorithms for the fixed-precision low-rank matrix approximation," SIAM Journal on Matrix Analysis and Applications, 39(3): 1339-1359, 2018.