This article presents a low-rank decomposition algorithm based on subsampling of matrix entries. The proposed algorithm first computes rank-revealing decompositions of submatrices with a blocked adaptive cross approximation (BACA) algorithm, and then applies a hierarchical merge operation via truncated singular value decompositions (H-BACA). The proposed algorithm significantly improves the convergence of the baseline ACA algorithm and achieves reduced computational complexity compared to the traditional decompositions such as rank-revealing QR. Numerical results demonstrate the efficiency, accuracy, and parallel scalability of the proposed algorithm.
BachF (2013) Sharp analysis of low-rank kernel matrix approximations. In: Proceedings of the 26th annual conference on learning theory, Proceedings of machine learning research, vol. 30. Princeton, USA: PMLR, 12–14 June 2013, pp. 185–209.
2.
BalzanoLNowakRRechtB (2010) Online identification and tracking of subspaces from highly incomplete information. In: 2010 48th annual Allerton conference on communication, control, and computing (Allerton), pp. 704–711. DOI: 10.1109/ALLERTON.2010.5706976.
3.
BebendorfM (2000) Approximation of boundary element matrices. Numerische Mathematik86(4): 565–589.
4.
BebendorfMGrzhibovskisR (2006) Accelerating Galerkin BEM for linear elasticity using adaptive cross approximation. Mathematical Methods in the Applied Sciences29(14): 1721–1747.
5.
BlackfordLSChoiJClearyA, et al. (1997) ScaLAPACK Users’ Guide. Philadelphia: Society for Industrial and Applied Mathematics.
6.
BoutsidisCMahoneyMWDrineasP (2009) An improved approximation algorithm for the column subset selection problem. In: Proceedings of the twentieth annual ACM-SIAM symposium on discrete algorithms, SODA ‘09, Philadelphia: Society for Industrial and Applied Mathematics, New York, New York, USA, 4–6 January 2009, pp. 968–977.
7.
CandèsEJRechtB (2009) Exact matrix completion via convex optimization. Foundations of Computational Mathematics9(6): 717.
8.
ChengHGimbutasZMartinssonP, et al. (2005) On the compression of low rank matrices. SIAM Journal on Scientific Computing26(4): 1389–1404.
9.
DheeruDKarra TaniskidouE (2017) UCI machine learning repository. Available at: http://archive.ics.uci.edu/ml (accessed 2 December 2014).
10.
FengYXiaoJGuM (2019) Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition. Electronic Transactions on Numerical Analysis51: 469–494.
11.
FosterLV (1997) The growth factor and efficiency of Gaussian elimination with rook pivoting. Journal of Computational and Applied Mathematics86(1): 177–194.
12.
GrasedyckLHackbuschW (2003) Construction and Arithmetics of H-matrices. Computing70(4): 295–334.
13.
GrasedyckLHackbuschW (2005) Hybrid cross approximation of integral operators. Numerische Mathematik101(2): 221–249.
14.
GuMEisenstatS (1996) Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM Journal on Scientific Computing17(4): 848–869.
15.
HackbuschWGrasedyckLBörmS (2002) An introduction to hierarchical matrices. Mathematica Bohemica127(2): 229–241.
16.
HeldringAUbedaERiusJM (2014) On the convergence of the ACA algorithm for radiation and scattering problems. IEEE Transactions on Antennas and Propagation62(7): 3806–3809.
17.
HeldringAUbedaERiusJM (2015) Stochastic estimation of the Frobenius norm in the ACA convergence criterion. IEEE Transactions on Antennas and Propagation63(3): 1155–1158.
18.
LibertyEWoolfeFMartinssonPG, et al. (2007) Randomized algorithms for the low-rank approximation of matrices. Proceedings of the National Academy of Sciences104(51): 20167–20172.
19.
MahoneyMWDrineasP (2009) CUR matrix decompositions for improved data analysis. Proceedings of the National Academy of Sciences106(3): 697–702.
20.
MartinssonPGQuintana-OrtíHeavnerN (2019) randUTV: a blocked randomized algorithm for computing a rank-revealing UTV factorization. ACM Transactions on Mathematical Software45(1): 1–26.
21.
MuscoCMuscoC (2017) Recursive sampling for the Nyström method. In: Advances in Neural Information Processing Systems30. New York: Curran Associates, Inc., pp. 3833–3845.
22.
NealLPooleG (1992) A geometric analysis of Gaussian elimination. II. Linear Algebra and its Applications173: 239–264.
23.
PooleGNealL (1991) A geometric analysis of Gaussian elimination. I. Linear Algebra and its Applications149: 249–272.
24.
PooleGNealL (1992) Gaussian elimination: When is scaling beneficial?Linear Algebra and its Applications162–164: 309–324.
25.
RebrovaEChavezGLiuY, et al. (2018) A study of clustering techniques and hierarchical matrix formats for kernel ridge regression. 2018 IEEE international parallel and distributed processing symposium workshops (IPDPSW), Vancouver, Canada, 21–25 May 2018, pp. 883–892.
26.
VoroninSMartinssonPG (2017) Efficient algorithms for CUR and interpolative matrix decompositions. Advances in Computational Mathematics43(3): 495–516.
27.
WangRLiYDarveE (2018) On the numerical rank of radial basis function kernels in high dimensions. SIAM Journal on Matrix Analysis and Applications39(4): 1810–1835.
28.
XiaoJGuMLangouJ (2017) Fast parallel randomized QR with column pivoting algorithms for reliable low-rank matrix approximations. In: 2017 IEEE 24th international conference on high performance computing (HiPC), pp. 233–242. DOI: 10.1109/HiPC.2017.00035.
29.
ZhaoKVouvakisMNLeeJF (2005) The adaptive cross approximation algorithm for accelerated method of moments computations of EMC problems. IEEE Transactions on Electromagnetic Compatibility47(4): 763–773.
30.
ZhouHZhuGKongW, et al. (2017) An upgraded ACA algorithm in complex field and its statistical analysis. IEEE Transactions on Antennas and Propagation65(5): 2734–2739.
