Sparse Matrices

Sparseness can refer to either the content of a matrix or the representation.

• A dense matrix is a matrix with a lot of non-zero elements
• A sparse matrix is the opposite and contains of a lot of zeros

The level of sparsity or density is an indication of how sparse or dense a matrix is.  It can be computed by dividing the number of non-zero elements by the total number of elements.

• If this number is low, then the matrix contains a lot of zeros and is called sparse
• If this number is high, the matrix contains only a few zeros and is called dense

• When a matrix only contains only a few nonzero elements then the specialized sparse representation of the matrix can be used
• This is a representation in which only the non-zero elements are stored, while the zeros are implicit

• Words in text: When counting words in a text, texts may only include a few words from all the words existing in a language: For a lot of words the value in the matrix will be zero
• Facebook friends: From 2 billion users, everyone has a couple of hundred friends, not all users are "friends" with each other: Every non-existing friendship on FB is saved as 0 in matrix

• Memory: less memory is needed to store the matrix, since the zero elements are not stored
• Efficiency: using a sparse matrix can speed up process

When working with

• Matrices containing only diagonal entries (e.g. Eigenvalues etc.)
• Matrices containing entries only in the upper or lower triangular
• Matricies that code the connections between nodes in a network
• Counting the words in text-based documents.

There are several ways to store sparse matrices in Scipy. Unfortunately there is no "one" sparse matrix representation that can do all tasks efficiently and fast. There are two groups that specialize in doing one thing really well:

• Group of representations that are efficient to build iteratively and modify individual entries (dok, lil and coo)
• Group of representations that are efficient to index particular items and perform matrix operations, like linear algebra (csc, csr)

1. Compressed sparse row (csr)
2. Compresses sparse column (csc)
3. Dictionary of keys (dok)

CSR represents the matrix with three numpy arrays. They contain:

1. The row indices of the non-zero entries in the matrix
2. The column indices of the non-zero entries in the matrix
3. All non-zero values in the matrix

csr_m = scipy.sparse.csr_matrix(dense_matrix, shape = dense_matrix.shape)

Advantages:

• Fast row slicing
• Efficient computations that operate across rows

Disadvantages:

• Slow column slicing operations
• Changes to the sparsity structure are expensive

CSC represents the matrix with three numpy arrays. They contain:

1. The column indices of the non-zero elements of the matrix
2. The row indices of the non-zero elements of the matrix
3. All values in the matrix that are non-zero

csc_m = scipy.sparse.matrix_csc(dense_matrix, shape = dense_matrix.shape)

Advantages:

• Fast column slicing
• Efficient computations that operate across columns

Disadvantages:

• Slow row slicing operations
• Changes to the sparsity structure are expensive

Dictionary of keys (dok) is a dictionary format where

• every key in the dictionary represents the row and column indices of the element and where
• the value in the dictionary represents the value of the element at that particular position.
• Elements with value 0 are not represented

S = scipy.sparse.matrix_dok((5,5), dtype = numpy.int32)

• In Scipy the total number of rows and columns must be specified at the initialization
• The rows & columns in a Scipy DOK sparse matrix must be integers (in vanilla python e.g. keys can be strings)

Yes, we can! There are three functions we discussed:

1. scipy.sparse.eye()
2. scipy.sparse.rand()
3. scipy.sparse.random()

Each of these functions can be passed a parameter format to indicate which representational format to create.

Convert the dok-matrix to a CSR matrix and use argmin()/argmax()

Convert the dok-matrix to a CSC matrix and use argmin()/argmax()