CUR Decomposition

The low-rank approximation algorithms in Chapter 4 produce approximations whose factors are linear combinations of all of the columns and rows of $\vec{A}$. Such factors can be hard to interpret, and they do not inherit structure (e.g. sparsity or non-negativity) that the columns and rows of $\vec{A}$ may have. A CUR decomposition instead builds a low-rank approximation directly out of a small number of actual columns and rows of $\vec{A}$.

Since $\vec{C}$ and $\vec{R}$ are columns and rows of $\vec{A}$ itself, they are often meaningful in terms of the underlying data; e.g. if the columns of $\vec{A}$ correspond to features and the rows to samples, then a CUR decomposition identifies a small set of representative features and samples Mahoney & Drineas, 2009. Moreover, $\vec{C}$ and $\vec{R}$ can be formed by reading only $|J|$ columns and $|I|$ rows of $\vec{A}$, so CUR decompositions are natural in settings where we cannot afford to observe all of $\vec{A}$.

Choosing the mixing matrix¶

Suppose the indices $I$ and $J$ have been fixed. Two common choices for $\vec{U}$ are:

1. Skeleton approximation: $\vec{U} = \vec{A}[I,J]^+$. This choice requires observing only the entries of $\vec{C}$ and $\vec{R}$ (note $\vec{A}[I,J]$ is a submatrix of both). If $\operatorname{rank}(\vec{A}) = k$ and $\operatorname{rank}(\vec{A}[I,J]) = k$, then $\vec{A} = \vec{C}\vec{A}[I,J]^+\vec{R}$ exactly.

2. Optimal mixing: $\vec{U} = \vec{C}^+ \vec{A} \vec{R}^+$. This choice minimizes $\|\vec{A} - \vec{C}\vec{U}\vec{R}\|_\F$ over all possible $\vec{U}$, but requires a full pass over $\vec{A}$.

The submatrix $\vec{A}[I,J]$ can be very ill-conditioned, so computing the skeleton approximation stably requires some care; e.g. regularizing the pseudoinverse. See Dong & Martinsson, 2023 for a discussion.

Choosing the columns and rows¶

The quality of a CUR decomposition is determined by the chosen indices $I$ and $J$; ideally the resulting approximation is competitive with the best rank-$k$ approximation to $\vec{A}$. Uniformly random columns and rows can easily miss important directions, so we must sample with better-chosen probabilities or use a pivoting strategy.

Leverage score sampling¶

A natural importance measure for the columns of $\vec{A}$ is given by the leverage scores of the dominant rank-$k$ right singular subspace of $\vec{A}$ (and analogously, for the rows, the dominant left singular subspace). Sampling columns and rows proportional to these (approximate) leverage scores yields relative-error guarantees.

Exact leverage scores require computing the dominant singular subspaces of $\vec{A}$, which is as hard as computing a low-rank approximation directly. However, as with approximate leverage score sampling for subspace embeddings, approximate leverage scores (e.g. obtained via sketching) suffice.

Pivoting¶

An alternative to randomized sampling is to choose the indices with a deterministic pivoting scheme such as column-pivoted QR. Applying such schemes to $\vec{A}$ directly is expensive, but they can instead be applied to a small sketch of $\vec{A}$.

Despite its simplicity, this approach is remarkably effective in practice, and often outperforms more sophisticated sampling-based schemes Dong & Martinsson, 2023.