# 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
>>> 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

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.

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().

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.

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)

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)

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.

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.

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