, ALORA: Affine Low-Rank Approximations, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01762882
, Approximation of boundary element matrices, Numerische Mathematik, vol.86, issue.4, pp.565-589, 2000.
DOI : 10.1007/pl00005410
, Hierarchical Matrices, 2008.
, Efficient Numerical Methods for Non-local Operators: H-2 matrix Compression, Algorithms and Analysis, 2010.
, An improved approximation algorithm for the column subset selection problem, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.968-977, 2009.
DOI : 10.1137/1.9781611973068.105
URL : https://epubs.siam.org/doi/pdf/10.1137/1.9781611973068.105
, Sublinear randomized algorithms for skeleton decompositions, SIAM Journal on Matrix Analysis and Applications, vol.34, issue.3, pp.1361-1383, 2013.
DOI : 10.1137/110852310
URL : http://arxiv.org/pdf/1110.4193
, Exponential inapproximability of selecting a maximum volume sub-matrix, Algorithmica, vol.65, issue.1, pp.159-176, 2013.
, Random projection trees and low dimensional manifolds, Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC), pp.537-546, 2008.
DOI : 10.1145/1374376.1374452
URL : http://www.cs.ucsd.edu/~dasgupta/papers/rptree-stoc.pdf
, Communication avoiding rank revealing QR factorization with column pivoting, SIAM J. Matrix Anal. Appl, 2015.
DOI : 10.21236/ada584728
URL : https://hal.archives-ouvertes.fr/hal-01112914
, Communication-optimal parallel and sequential QR and LU factorizations, 2008.
DOI : 10.1137/080731992
URL : https://hal.archives-ouvertes.fr/hal-00870930
, Communication-optimal parallel and sequential QR and LU factorizations, SIAM J. Sci. Comput, vol.34, issue.1, pp.206-239, 2012.
DOI : 10.1137/080731992
URL : https://hal.archives-ouvertes.fr/hal-00870930
, Matrix approximation and projective clustering via volume sampling, Theory of Computing, vol.2, pp.225-247, 2006.
DOI : 10.1145/1109557.1109681
URL : http://www-math.mit.edu/~vempala/papers/matrixsoda.ps
, The black-box fast multipole method, Journal of Computational Physics, vol.228, pp.8712-8725, 2009.
DOI : 10.1016/j.jcp.2009.08.031
, Matrix Computations, 1996.
, How to find a good submatrix, ICM HKBU, 2008.
DOI : 10.1142/9789812836021_0015
, The maximal-volume concept in approximation by low-rank matrices, Contemporary Mathematics, issue.280, pp.47-51, 2001.
DOI : 10.1090/conm/280/4620
, Quasioptimality of skeleton approximation of a matrix in the chebyshev norm, Doklady Mathematics, vol.83, issue.3, pp.374-375, 2011.
, N-body problems in statistical learning, Adv. Neural Inf. Process. Syst, pp.521-527, 2001.
, A fast algorithm for particle simulations, Journal of Computational Physics, vol.73, issue.2, pp.325-348, 1987.
, Low rank approximation of a sparse matrix based on lu factorization with column and row tournament pivoting, SIAM J. Sci. Comput, vol.40, issue.2, pp.181-209, 2018.
DOI : 10.1137/16m1074527
URL : https://hal.archives-ouvertes.fr/hal-01313856
, Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM J. Matrix Anal. Appl, vol.17, issue.4, pp.848-869, 1996.
, Hierarchical Matrices: Algorithms and Analysis, Springer Series in Computational Mathematics, 2015.
, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, 2002.
, Topics in Matrix Analysis, 1991.
, N-body problems: IES3: Efficient electrostatic and electromagnetic simulation, IEEE Computational Science and Engineering, vol.5, issue.4, pp.60-67, 1998.
, Fast multipole methods for three-dimensional N-body problems, pp.377-390, 1995.
, Literature survey on low rank approximation of matrices. Linear and Multilinear Algebra, vol.65, pp.2212-2244, 2017.
, Cur matrix decompositions for improved data analysis, Proceedings of the National Academy of Sciences, vol.106, issue.3, pp.697-702, 2009.
, Far-field compression for fast kernel summation methods in high dimensions, Applied and Computational Harmonic Analysis, vol.43, issue.1, pp.39-75, 2017.
, An accelerated kernel-independent fast multipole method in one dimension, SIAM J. Sci. Comput, vol.29, issue.3, pp.1160-1178, 2007.
, Symmetric gauge functions and unitarily invariant norms, Quart. J. Math. Oxford Ser, vol.11, issue.2, pp.50-59, 1960.
, Pseudo-skeleton approximations with better accuracy estimates, Linear Algebra and its Applications, vol.537, pp.221-249, 2018.
, A low-rank IE-QR algorithm for matrix compression in volume integral equations, IEEE Transactions on Magnetics, vol.40, issue.2, pp.1017-1020, 2004.
, Bounds on singular values revealed by QR factorizations, BIT Numerical Mathematics, vol.39, issue.4, pp.740-756, 1999.
, Adaptive cross approximation of dense matrices, International Association for Boundary Element Methods Conference, IABEM, 2002.
, An Introduction to the Geometry of n Dimensions, 1958.
, Numerical Approximation Methods for Elliptic Boundary Value Problems: Finite and Boundary Elements, 2008.
, Efficient algorithms for cur and interpolative matrix decompositions, Advances in Computational Mathematics, vol.43, issue.3, pp.495-516, 2017.
, Source and target points, given as matrices of size (mxd) and (nxd)
, % respectively, where d is the geometric dimension 5 % k: fixed approximation rank
, Laplacian kernel: fun = @(x,y) ?1/(2 * pi) * log(norm, % fun: kernel function
, % Exponential kernel: fun = @(x,y) exp(1i * norm(x?y))/norm
, Gravitation kernel: fun = @(x,y) 1/(4 * pi * norm
, Returns: 10 % CUR: a rank?k approximation of matrix A(i,j)=fun, vol.9
, U are complex matrices of size (mxk), (kxn), (kxk) 12 13 function
, C=zeros(m,t
, R=zeros(k,n)
, % Decompose target domain into t subdomains
,
,
, 1:k), Q=Q
, :k)), p _ c
, :k); j=1:size(Y,1)
, has two sons corresponding to disjoint sets of pints separated by the plane orthogonal to the line having direction given as the first left singular vector of matrix T := [y 1 , · · · , y h ] ? g ? R 3×r , and intersecting it at g. The following algorithm, 53 calling function BinaryPartition, which is an approach known as geometrically balanced clustering, c.f. [4, Alg, vol.3
, %% Select target points using geometrically balanced partition 2 % Require
, % Y: set of n target points, Y is an mxd matrix, d: geometric dimension
,
, Bal _ Partition(Y
,
, for j = 1:size(S{i?1},2) % number of clusters at previous generation 27 [g,s] = Geo _ Bal _ Partition, vol.26
,
, G{i},g); j=1:size(G{l},2) 35 for i=1:size(Y,1) 36 if(G{l}{j}'==Y(i
, J(j)=i
, cluster of points 53 % Returns: 54 % Son: list of two cluster sons
, contains the gravity centers of cluster sons
, , vol.59, p.60
,
,
, Cov)
,
,
, Getting the index of target point closest to the gravity center of S _ y 73 v = (S _ y ? g
, n _ s = size(Sons{j},1)
, * ones(n _ s,1)/n _ s
,
,
, Selecting columns using Nearest-Neighbors approach This approach consists in selecting t target points the closest to the set of source points, see Figure 2c. Then, indices corresponding to these points are the selected columns to be used to compute a CUR approximation and we call the resulting algorithm CUR_NNS as
, %% Select target points using Nearest?Neighbors