RPCholesky Factorization

Given a spd matrix A, the rank k random Cholesky factorization can be obtained with

RPCholesky.rpcholesky — Function

rpcholesky(A, k; τ = 1e-8, verbose = false)

Perform the RPCholesky factorization for matrix A of rank at most k. This corresponds to Algorithm 2.1 of Chen et al.

This returns the factorization F, along with the array of pivots, S.

Fields

A - an spd matrix
k - maximum desired rank
τ = 1e-8 - approximation tolerance
verbose = false - provide diagnostic details

source

Its usage is illustrated in the following simple example, which returns the factorization $A\approx FF'$.

using LinearAlgebra
using RPCholesky
using Random

h = 1.0; # kernel width
K(x,y) = exp(-(x-y)^2 / (2*h^2))

N = 10; # number of points
x_pts = LinRange(0,1,N);

# consruct kernel matrix
A = [K(x_, y_) for x_ in x_pts, y_ in x_pts];

Random.seed!(100); # set seed for reproducibility
# factor
k = 5;
F, S = rpcholesky(A, 5);

# check error
@show opnorm(A - F*F'); # spectral norm
@show norm(A - F*F');   # Frobenius norm

7.140168188593941e-7