maxvolpy.maxvol.maxvol

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

Finds good square submatrix.

Uses greedy iterative maximization of 1-volume to find good r-by-r submatrix in a given N-by-r matrix A of rank r. Returns good submatrix and coefficients of expansion (N-by-r matrix) of rows of matrix A by rows of good submatrix.

Parameters:

A : numpy.ndarray(ndim=2)

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

tol : float, optional

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

max_iters : integer, optional

Maximum number of iterations. Each iteration swaps 2 rows. Defaults to 100.

top_k_index : integer, optional

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. Defaults to -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
>>> np.random.seed(100)
>>> a = np.random.rand(1000, 30, 2).view(dtype=np.complex128)[:,:,0]
>>> piv, C = maxvol(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(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(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