Sparse Matrix Storage for Single-Cell Counts

Why Store a Count Matrix Sparsely?

A gene-by-cell count matrix has one row per gene and one column per cell. An entry records the count for that gene in that cell. In a typical single-cell data set, each cell has counts for only a fraction of all genes, so most matrix entries are zero. Storing every zero explicitly can waste substantial memory.

Sparse storage records the nonzero entries and enough index information to locate them. A zero that is not stored is understood to be zero; it is not an unknown value or a missing measurement. Sparse storage changes the representation of the matrix, not the counts it represents. The earlier material on building a gene-by-cell count matrix establishes what its rows, columns, and entries mean.

Definition: A matrix is sparse when most of its entries are zero. Its number of nonzero entries, often written \(z\), counts the entries whose values are not zero. A sparse matrix representation stores those values together with indices or pointers that identify their locations.

The three common representations considered here are coordinate format (COO), compressed sparse row (CSR), and compressed sparse column (CSC). Each can encode the same matrix exactly. They differ in how they record locations, and therefore in the storage overhead and the convenience of accessing rows or columns. For clarity, the examples use zero-based indices: the first row and column are numbered 0.

A Small Matrix in Three Representations

Consider this hypothetical matrix with four genes as rows and three cells as columns. The entries are hypothetical counts.

A = \begin{bmatrix} 0 & 2 & 0 \\ 5 & 0 & 1 \\ 0 & 0 & 0 \\ 3 & 4 & 0 \end{bmatrix}

There are \(4\times3=12\) total entries, of which five are nonzero. In this example, row 2 is entirely zero: that gene has a recorded count of zero in every cell in the matrix.

Worked Example: Encoding the Same Counts Three Ways

List the nonzero entries of \(A\), then write them in COO, CSR, and CSC form.

COO. Store one row index, one column index, and one value for each nonzero. Listing entries in row order gives:

(\text{row},\text{column},\text{value}) = (0,1,2),\ (1,0,5),\ (1,2,1),\ (3,0,3),\ (3,1,4).

For instance, \((1,2,1)\) means that row 1, column 2 contains the value 1. The zero-based index convention matters: this is the second row and third column when counted from 1.

CSR. Store the nonzero values in row order, their column indices, and a row-pointer array. The row pointer gives the starting position of each row’s entries in the values and column-index arrays; its final element is the total number of stored entries.

\begin{aligned} \text{values} &= [2,5,1,3,4],\\ \text{column indices} &= [1,0,2,0,1],\\ \text{row pointers} &= [0,1,3,3,5]. \end{aligned}

The first row uses positions 0 through 0 because its pointer interval is \([0,1)\). The second row uses positions 1 through 2, since its interval is \([1,3)\). The third row has no entries: its interval is \([3,3)\). The fourth row uses positions 3 and 4, the interval \([3,5)\). These intervals recover all five values and their columns.

CSC. Store the nonzero values in column order, their row indices, and a column-pointer array:

\begin{aligned} \text{values} &= [5,3,2,4,1],\\ \text{row indices} &= [1,3,0,3,1],\\ \text{column pointers} &= [0,2,4,5]. \end{aligned}

Column 0 occupies positions 0 and 1, column 1 occupies positions 2 and 3, and column 2 occupies position 4. The pointer intervals are respectively \([0,2)\), \([2,4)\), and \([4,5)\). As in CSR, the last pointer equals the number of stored entries.

The pointer arrays include a boundary for every row or column, including empty ones. That is why the CSR row-pointer array has \(m+1\) entries for a matrix with \(m\) rows, and the CSC column-pointer array has \(n+1\) entries for a matrix with \(n\) columns. The pointer values are positions in the stored-entry arrays, not row or column labels.

Storage Costs and the Break-Even Idea

Sparse storage is not automatically smaller for every matrix. It saves space when the cost of storing the nonzero values and their location information is less than the cost of storing every matrix entry. A simple calculation makes this tradeoff explicit.

Storage model: Suppose each value uses \(b_v\) bytes, each index uses \(b_i\) bytes, and each pointer uses \(b_p\) bytes. For an \(m\times n\) matrix with \(z\) nonzero entries, dense storage uses \(mn b_v\) bytes. COO uses approximately \(z(b_v+2b_i)\) bytes. CSR uses \(z(b_v+b_i)+(m+1)b_p\) bytes; CSC uses \(z(b_v+b_i)+(n+1)b_p\) bytes.

These formulas assume that every nonzero value has the same storage size, that both COO indices are stored for each entry, and that the compressed format stores one index per value plus its pointer array. They ignore small implementation-specific overheads, such as object headers, alignment, and optional spare capacity. Real software may use different index widths or value types.

For example, CSR is smaller than dense storage under this model when

$$ z(b_v+b_i)+(m+1)b_p < mn b_v. $$

Rearranging shows that the nonzero count must be below a threshold:

z < \frac{mn b_v-(m+1)b_p}{b_v+b_i}.

This is a storage break-even condition, not a statistical assumption about the data. It shows why sparsity alone does not guarantee a saving: the index and pointer costs also count. For a large matrix with many zeros, the nonzero-value and index arrays can still be far smaller than a dense array.

Worked Example: Estimating Storage for a Large Matrix

Suppose a hypothetical matrix has 20,000 genes and 10,000 cells, with 20 million nonzero entries. Assume 4-byte values, 4-byte indices, and 4-byte pointers. Compare approximate dense, CSR, and COO storage.

The dense matrix contains \(20{,}000\times10{,}000=200{,}000{,}000\) entries. Its storage is

200{,}000{,}000\times4 =800{,}000{,}000\ \text{bytes} =800\ \text{MB},

using decimal megabytes, where 1 MB is 1,000,000 bytes.

CSR stores each of the 20 million values and one 4-byte column index, plus 20,001 row pointers:

20{,}000{,}000(4+4)+20{,}001(4) =160{,}080{,}004\ \text{bytes} \approx160.1\ \text{MB}.

COO stores two 4-byte indices and one 4-byte value for each nonzero:

20{,}000{,}000(4+4+4) =240{,}000{,}000\ \text{bytes} =240\ \text{MB}.

Under these assumptions, CSR uses about \(160.1/800=0.2001\), or 20.01%, of the dense storage, a reduction of about 79.99%. COO uses 30.00% of the dense storage. These are approximate array sizes, not guarantees for every software implementation.

This calculation also explains a practical distinction: COO is straightforward to assemble because each entry is recorded independently, while CSR and CSC exploit the grouping of entries by row or column. Converting between formats may be useful when the work changes, but conversion requires computation and temporary storage.

Choosing Between COO, CSR, and CSC

Representation	What is stored	Convenient access	Typical limitation
COO	Row index, column index, and value for each nonzero	Listing or assembling individual entries	Repeated row and column indices add storage; extracting a whole row or column may require searching
CSR	Values, column indices, and row pointers	Rows and row-based operations	Column access may require scanning many stored entries
CSC	Values, row indices, and column pointers	Columns and column-based operations	Row access may require scanning many stored entries

In a gene-by-cell matrix, rows correspond to genes and columns correspond to cells. Thus CSR groups counts gene by gene, whereas CSC groups counts cell by cell. If an operation repeatedly needs all stored counts for one cell, CSC naturally identifies that cell’s entries through its column-pointer interval. If it repeatedly needs all counts for one gene, CSR naturally identifies that gene’s entries through its row-pointer interval. This describes storage access, not a recommendation about any later statistical analysis.

Worked Example: Summing a Row and a Column

Use the hypothetical matrix \(A\) above to find the sum for gene 1 and the sum for cell 0. Explain which compressed representation locates each set of entries directly.

Gene 1 is row 1. In CSR, its row-pointer interval is \([1,3)\), so its stored values are 5 and 1. Its row sum is

5+1=6\ \text{counts}.

Cell 0 is column 0. In CSC, its column-pointer interval is \([0,2)\), so its stored values are 5 and 3. Its column sum is

5+3=8\ \text{counts}.

The sums also agree with direct inspection of the dense matrix. CSR makes the row’s stored entries directly available; CSC does the same for the column. The result is a sum over matrix entries, not a claim about an underlying population quantity.

Assumptions, Diagnostics, and Common Pitfalls

The representations above assume a well-defined rectangular matrix and a consistent mapping of rows and columns to genes and cells. Each stored index must be within the matrix dimensions, and the value at that index must be the intended count. A standard sparse count matrix has integer-valued, nonnegative entries, but the storage formats themselves can represent other numerical values as well.

When checking a sparse representation, useful structural checks include confirming that the number of values equals the number of index entries, that the final pointer equals the number of stored entries, and that pointers are nondecreasing. A row or column with no stored entries must have equal adjacent pointers. For COO, verify that each row and column index lies within the stated dimensions. These checks test whether the encoding is internally coherent; they do not establish that the underlying counts were generated or assigned correctly.

Confusing implicit zero with missingness. A zero omitted from a sparse array is still a zero in the matrix. Missing or unknown values require a separate representation or convention.
Mixing index bases. In the example, the first row is index 0. Interpreting those values as one-based indices shifts the locations and can produce incorrect dimensions or entries.
Reading pointers as indices. A pointer marks a position in the stored-entry arrays. It does not give the gene or cell label itself.
Assuming the format determines orientation. CSR and CSC refer to how a given matrix is compressed. They do not change which dimension represents genes or cells. A transposed matrix has different row and column meanings.
Assuming sparse is always smaller or faster. For a small or relatively dense matrix, index overhead can exceed the cost of storing zeros. Access speed also depends on the operation and the software implementation.

Worked Example: When Sparse Storage Does Not Save Space

For the 4-by-3 matrix \(A\), suppose values, indices, and pointers each use 4 bytes. Compare dense storage with CSR storage.

Dense storage uses 12 values:

12(4)=48\ \text{bytes}.

CSR stores five values, five column indices, and five row pointers:

5(4)+5(4)+5(4)=60\ \text{bytes}.

So CSR uses 12 bytes more than dense storage in this small example, despite seven of the twelve entries being zero. The pointer and index overhead is large relative to the matrix. This does not contradict sparse storage’s usefulness for large single-cell matrices; it shows that the actual size comparison depends on dimensions, nonzero count, and the representation’s overhead.

Key Takeaway

COO records each nonzero location explicitly; CSR groups entries by rows; CSC groups entries by columns. The three formats can encode identical gene-by-cell counts, but their index and pointer arrays differ. Sparse storage is advantageous when saved zero values outweigh that bookkeeping cost, and the best compressed format depends partly on whether row or column access is more frequent.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions.

A 6-by-4 matrix has 7 nonzero entries. How many values are stored in dense form, and how many value entries are stored in COO, CSR, or CSC?
For a matrix with 8 rows and 5 columns, how many pointers are in CSR and how many are in CSC?
In a zero-based CSR representation, a row has adjacent pointers 4 and 4. How many stored entries does that row contain?
A task repeatedly retrieves the nonzero entries in one cell column of a gene-by-cell matrix. Which compressed format directly groups those entries, and why?

Solutions. (1) Dense form stores \(6\times4=24\) values. Each sparse format stores 7 values; the index and pointer arrays differ, but the number of stored nonzero values is the same. (2) CSR uses \(8+1=9\) row pointers, and CSC uses \(5+1=6\) column pointers. (3) The row has \(4-4=0\) stored entries; it is an all-zero row. (4) CSC groups entries by column, so the column’s pointer interval identifies the positions containing that cell’s stored counts.