maxvolpy.maxvol.maxvol_qr

maxvolpy.maxvol.maxvol_qr(A, tol=1.05, max_iters=100, top_k_index=-1)

Finds good square submatrix in Q factor of QR of A.

When rank of N-by-r matrix A is not guaranteed to be equal to r, good submatrix in A can be found as good submatrix in Q factor of QR decomposition of A.

Parameters:

A : numpy.ndarray(ndim=2)

Real or complex matrix of shape (N, r), N >= r.

tol : float

Upper bound for infinite norm of coefficients of expansion of rows of A by rows of good submatrix. Minimum value is 1.

max_iters : integer

Maximum number of iterations. Each iteration swaps 2 rows.

top_k_index : integer

Pivot rows for good submatrix will be in range from 0 to (top_k_index-1). This restriction is ignored, if top_k_index is -1.

Returns:

piv : numpy.ndarray(ndim=1, dtype=numpy.int32)

Rows of matrix A, corresponding to submatrix, good in terms of 1-volume. Shape is (r, ).

C : numpy.ndarray(ndim=2)

Matrix of coefficients of expansions of all rows of A by good rows piv. Shape is (N, r).

Examples

>>> import numpy as np
>>> from maxvolpy.maxvol import maxvol_qr
>>> np.random.seed(100)
>>> a = np.random.rand(1000, 30, 2).view(dtype=np.complex128)[:,:,0]
>>> piv, C = maxvol_qr(a, 1.0)
>>> np.allclose(a, C.dot(a[piv]))
True
>>> print('Chebyshev norm of matrix C: {:.5f}'.format(abs(C).max()))
Chebyshev norm of matrix C: 1.00000
>>> piv, C = maxvol_qr(a, 1.05)
>>> np.allclose(a, C.dot(a[piv]))
True
>>> print('Chebyshev norm of matrix C: {:.5f}'.format(abs(C).max()))
Chebyshev norm of matrix C: 1.04641
>>> piv, C = maxvol_qr(a, 1.10)
>>> np.allclose(a, C.dot(a[piv]))
True
>>> print('Chebyshev norm of matrix C: {:.5f}'.format(abs(C).max()))
Chebyshev norm of matrix C: 1.07854