quimb.linalg.rand_linalg

Randomized iterative methods for decompositions.

Module Contents

Functions

lu_orthog(X)

qr_orthog(X)

orthog(X[, lu])

QB_to_svd(Q, B[, compute_uv])

trim(arrays, k)

possibly_extend_randn(G, k, p, A)

isstring(x, s)

rsvd_qb(A, k, q, p, state[, AH])

rsvd_core(A, k[, compute_uv, q, p, state, AH])

Core R3SVD algorithm.

is_sorted(x)

gen_k_steps(start[, incr])

rsvd_iterate(A, eps[, compute_uv, q, p, G0, k_max, ...])

Handle rank-adaptively calling rsvd_core.

count_svdvals_needed(s, eps)

isdouble(dtype)

Check if dtype is double precision.

estimate_rank(A, eps[, k_max, use_sli, k_start, ...])

Estimate the rank of an linear operator. Uses a low quality random

maybe_flip(UsV, flipped)

rsvd(A, eps_or_k[, compute_uv, mode, use_qb, q, p, ...])

Fast, randomized, iterative SVD. Adaptive variant of method due
quimb.linalg.rand_linalg.lu_orthog(X)[source]
quimb.linalg.rand_linalg.qr_orthog(X)[source]
quimb.linalg.rand_linalg.orthog(X, lu=False)[source]
quimb.linalg.rand_linalg.QB_to_svd(Q, B, compute_uv=True)[source]
quimb.linalg.rand_linalg.trim(arrays, k)[source]
quimb.linalg.rand_linalg.possibly_extend_randn(G, k, p, A)[source]
quimb.linalg.rand_linalg.isstring(x, s)[source]
quimb.linalg.rand_linalg.rsvd_qb(A, k, q, p, state, AH=None)[source]
quimb.linalg.rand_linalg.rsvd_core(A, k, compute_uv=True, q=2, p=0, state=None, AH=None)[source]

Core R3SVD algorithm.

Parameters:

  • A (linear operator, shape (m, n)) – Operator to decompose, assumed m >= n.

  • k (int) – Number of singular values to find.

  • compute_uv (bool, optional) – Return the left and right singular vectors.

  • q (int, optional) – Number of power iterations.

  • p (int, optional) – Over sampling factor.

  • state ({None, array_like, (), (G0,), (U0, s0, VH0, G0)}, optional) –

    Iterate based on these previous results:

    • None: basic mode.

    • array_like: use this as the initial subspace.

    • ’begin-svd’: begin block iterations, return U, s, VH, G

    • (G0,) : begin block iterations with this subspace

    • (U0, s0, VH0, G0): continue block iterations, return G

quimb.linalg.rand_linalg.is_sorted(x)[source]
quimb.linalg.rand_linalg.gen_k_steps(start, incr=1.4)[source]
quimb.linalg.rand_linalg.rsvd_iterate(A, eps, compute_uv=True, q=2, p=0, G0=None, k_max=None, k_start=2, k_incr=1.4, AH=None, use_qb=20)[source]

Handle rank-adaptively calling rsvd_core.

quimb.linalg.rand_linalg.count_svdvals_needed(s, eps)[source]
quimb.linalg.rand_linalg.isdouble(dtype)[source]

Check if dtype is double precision.

quimb.linalg.rand_linalg.estimate_rank(A, eps, k_max=None, use_sli=True, k_start=2, k_incr=1.4, q=0, p=0, get_vectors=False, G0=None, AH=None, use_qb=20)[source]

Estimate the rank of an linear operator. Uses a low quality random SVD with a resolution of ~ 10.

Parameters:

  • A (linear operator) – The operator to find rank of.

  • eps (float) – Find rank to this relative (compared to largest singular value) precision.

  • k_max (int, optional) – The maximum rank to find.

  • use_sli (bool, optional) – Whether to use scipy.linalg.interpolative.estimate_rank() if possible (double precision and no k_max set).

  • k_start (int, optional) – Begin the adaptive SVD with a block of this size.

  • k_incr (float, optional) – Adaptive rank increment factor. Increase the k-step (from k_start) by this factor each time. Set to 1 to use a constant step.

  • q (int, optional) – Number of power iterations.

  • get_vectors (bool, optional) – Return the right singular vectors found in the pass.

  • G0 (, optional)

Returns:

  • rank (int) – The rank.

  • VH (array) – The (adjoint) right singular vectors if get_vectors=True.

quimb.linalg.rand_linalg.maybe_flip(UsV, flipped)[source]
quimb.linalg.rand_linalg.rsvd(A, eps_or_k, compute_uv=True, mode='adapt+block', use_qb=20, q=2, p=0, k_max=None, k_start=2, k_incr=1.4, G0=None, AH=None)[source]

Fast, randomized, iterative SVD. Adaptive variant of method due originally to Halko. This scales as log(k) rather than k so can be more efficient.

Parameters:

  • A (operator, shape (m, n)) – The operator to decompose.

  • eps_or_k (float or int) – Either the relative precision or the number of singular values to target. If precision, this is relative to the largest singular value.

  • compute_uv (bool, optional) – Whether to return the left and right singular vectors.

  • mode ({'adapt+block', 'adapt', 'block'}, optional) –

    How to perform the randomized SVD. If eps_or_k is an integer then this is implicitly ‘block’ and ignored. Else:

    • ’adapt+block’, perform an initial low quality pass to estimate the rank of A, then use the subspace and rank from that to perform an accurate fully blocked RSVD.

    • ’adapt’, just perform the adaptive randomized SVD.

  • q (int, optional) – The number of power iterations, increase for accuracy at the expense of runtime.

  • p (int, optional) – Oversampling factor. Perform projections with this many extra columns and then throw then away.

  • k_max (int, optional) – Maximum adaptive rank. Default: min(A.shape).

  • k_start (int, optional) – Initial k when increasing rank adaptively.

  • k_incr (float, optional) – Adaptive rank increment factor. Increase the k-step (from k_start) by this factor each time. Set to 1 to use a constant step.

  • G0 (array_like, shape (n, k), optional) – Initial subspace to start iterating on. If not given a random one will be generated.

Returns:

  • U, array, shape (m, k) – Left singular vectors, if compute_uv=True.

  • s, array, shape (k,) – Singular values.

  • V, array, shape (k, n) – Right singular vectors, if compute_uv=True.