Linear algebra

Tools of linear algebra.

Normalization

sknetwork.linalg.normalize(matrix: Union[scipy.sparse._csr.csr_matrix, numpy.ndarray, scipy.sparse.linalg._interface.LinearOperator], p=1)[source]

Normalize the rows of a matrix so that all have norm 1 (or 0; null rows remain null).

Parameters
  • matrix – Input matrix.

  • p – Order of the norm.

Returns

Normalized matrix (same format as input matrix).

Return type

normalized matrix

sknetwork.linalg.diagonal_pseudo_inverse(weights: numpy.ndarray) scipy.sparse._csr.csr_matrix[source]

Compute \(\text{diag}(w)^+\), the pseudo-inverse of the diagonal matrix with diagonal elements given by the weights \(w\).

Parameters

weights – The weights to invert.

Returns

Return type

sparse.csr_matrix

Sparse + Low Rank

class sknetwork.linalg.SparseLR(*args, **kwargs)[source]

Class for matrices with “sparse + low rank” structure. Example:

\(A + xy^T\)

Parameters
  • sparse_mat (scipy.spmatrix) – Sparse component. Is converted to csr format automatically.

  • low_rank_tuples (list) – Single tuple of arrays of list of tuples, representing the low rank components [(x1, y1), (x2, y2),…]. Each low rank component is of the form \(xy^T\).

Examples

>>> from scipy import sparse
>>> from sknetwork.linalg import SparseLR
>>> adjacency = sparse.eye(2, format='csr')
>>> slr = SparseLR(adjacency, (np.ones(2), np.ones(2)))
>>> x = np.ones(2)
>>> slr.dot(x)
array([3., 3.])
>>> slr.sum(axis=0)
array([3., 3.])
>>> slr.sum(axis=1)
array([3., 3.])
>>> slr.sum()
6.0

References

De Lara (2019). The Sparse + Low Rank trick for Matrix Factorization-Based Graph Algorithms. Proceedings of the 15th International Workshop on Mining and Learning with Graphs (MLG).

property H

Hermitian adjoint.

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Can be abbreviated self.H instead of self.adjoint().

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

property T

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

adjoint()

Hermitian adjoint.

Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.

Can be abbreviated self.H instead of self.adjoint().

Returns

A_H – Hermitian adjoint of self.

Return type

LinearOperator

astype(dtype: Union[str, numpy.dtype])[source]

Change dtype of the object.

dot(x)

Matrix-matrix or matrix-vector multiplication.

Parameters

x (array_like) – 1-d or 2-d array, representing a vector or matrix.

Returns

Ax – 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.

Return type

array

left_sparse_dot(matrix: scipy.sparse._csr.csr_matrix)[source]

Left dot product with a sparse matrix.

matmat(X)

Matrix-matrix multiplication.

Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.

Parameters

X ({matrix, ndarray}) – An array with shape (N,K).

Returns

Y – A matrix or ndarray with shape (M,K) depending on the type of the X argument.

Return type

{matrix, ndarray}

Notes

This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.

matvec(x)

Matrix-vector multiplication.

Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (N,) or (N,1).

Returns

y – A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.

right_sparse_dot(matrix: scipy.sparse._csr.csr_matrix)[source]

Right dot product with a sparse matrix.

rmatmat(X)

Adjoint matrix-matrix multiplication.

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array, or 2-d array. The default implementation defers to the adjoint.

Parameters

X ({matrix, ndarray}) – A matrix or 2D array.

Returns

Y – A matrix or 2D array depending on the type of the input.

Return type

{matrix, ndarray}

Notes

This rmatmat wraps the user-specified rmatmat routine.

rmatvec(x)

Adjoint matrix-vector multiplication.

Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.

Parameters

x ({matrix, ndarray}) – An array with shape (M,) or (M,1).

Returns

y – A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.

Return type

{matrix, ndarray}

Notes

This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.

sum(axis=None)[source]

Row-wise, column-wise or total sum of operator’s coefficients.

Parameters

axis – If 0, return column-wise sum. If 1, return row-wise sum. Otherwise, return total sum.

transpose()

Transpose this linear operator.

Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().

Solvers

class sknetwork.linalg.LanczosEig(which='LM', n_iter: Optional[int] = None, tol: float = 0.0)[source]

Eigenvalue solver using Lanczos method.

Parameters
  • which (str) –

    Which eigenvectors and eigenvalues to find:

    • 'LM' : Largest (in modulus) eigenvalues.

    • 'SM' : Smallest (in modulus) eigenvalues.

    • 'LA' : Largest (algebraic) eigenvalues.

    • 'SA' : Smallest (algebraic) eigenvalues.

  • n_iter (int) – Maximum number of Arnoldi update iterations allowed. Default = 10 * nb of rows.

  • tol (float) – Relative accuracy for eigenvalues (stopping criterion). Default = 0 (machine precision).

Variables
  • eigenvectors_ (np.ndarray) – Two-dimensional array, each column is an eigenvector of the input.

  • eigenvalues_ (np.ndarray) – Eigenvalues associated to each eigenvector.

See also

scipy.sparse.linalg.eigsh

fit(matrix: Union[scipy.sparse._csr.csr_matrix, scipy.sparse.linalg._interface.LinearOperator], n_components: int = 2)[source]

Perform spectral decomposition on symmetric input matrix.

Parameters
  • matrix (sparse.csr_matrix or linear operator) – Matrix to decompose.

  • n_components (int) – Number of eigenvectors to compute

Returns

self

Return type

EigSolver

get_params()

Get parameters as dictionary.

Returns

params – Parameters of the algorithm.

Return type

dict

set_params(params: dict) sknetwork.base.Algorithm

Set parameters of the algorithm.

Parameters

params (dict) – Parameters of the algorithm.

Returns

self

Return type

Algorithm

class sknetwork.linalg.LanczosSVD(n_iter: Optional[int] = None, tol: float = 0.0)[source]

SVD solver using Lanczos method on \(AA^T\) or \(A^TA\).

Parameters
  • n_iter (int) – Maximum number of Arnoldi update iterations allowed. Default = 10 * nb or rows or columns.

  • tol (float) – Relative accuracy for eigenvalues (stopping criterion). Default = 0 (machine precision).

Variables
  • singular_vectors_left_ (np.ndarray) – Two-dimensional array, each column is a left singular vector of the input.

  • singular_vectors_right_ (np.ndarray) – Two-dimensional array, each column is a right singular vector of the input.

  • singular_values_ (np.ndarray) – Singular values.

See also

scipy.sparse.linalg.svds

fit(matrix: Union[scipy.sparse._csr.csr_matrix, scipy.sparse.linalg._interface.LinearOperator], n_components: int, init_vector: Optional[numpy.ndarray] = None)[source]

Perform singular value decomposition on input matrix.

Parameters
  • matrix – Matrix to decompose.

  • n_components (int) – Number of singular values to compute

  • init_vector (np.ndarray) – Starting vector for iteration. Default = random.

Returns

self

Return type

SVDSolver

get_params()

Get parameters as dictionary.

Returns

params – Parameters of the algorithm.

Return type

dict

set_params(params: dict) sknetwork.base.Algorithm

Set parameters of the algorithm.

Parameters

params (dict) – Parameters of the algorithm.

Returns

self

Return type

Algorithm