When faced with a massive high-dimensional dataset, our first instinct is usually to compress it. For decades, the gold standard for unsupervised dimensionality reduction has been Singular Value Decomposition (SVD) and its close relative, Principal Component Analysis (PCA). These methods find a set of orthogonal vectors that capture the maximum possible variance in the data.
Mathematically, SVD is optimal. Practically, it introduces a severe hidden cost: it destroys meaning.
The Interpretability Crisis in Matrix Factorization
To understand why traditional methods fail human intuition, consider a matrix $A$ where rows represent patients and columns represent gene expression levels. When you run SVD, the algorithm outputs "eigen-genes"—synthetic basis vectors that are linear combinations of all original features. An eigen-gene might look like:
$$\text{Basis Vector} = 0.34 \times \text{Gene A} - 0.12 \times \text{Gene B} + 0.51 \times \text{Gene C} \dots$$
What does this mean biologically? It is almost impossible to tell. As noted by Elbagoury et al. and Erichson et al., mapping these abstract mathematical constructs back to real-world variables creates a massive barrier for domain experts who need to trust and act on model outputs. In fields like hyperspectral imaging or clinical diagnostics, this loss of physical grounding is unacceptable (Esser et al.; Wahabzada et al.).
This tension drives a different approach to dimensionality reduction: interpretable matrix decomposition. Instead of constructing artificial axes, why not represent the dataset using a carefully chosen subset of its actual rows and columns?
Grounding Latent Spaces in Real Observations
The core philosophy of this research direction is to force the low-rank approximation to use the data's original vocabulary. Two primary frameworks achieve this: Column Subset Selection (CSS) and CUR Decomposition.
In Column Subset Selection, we approximate a data matrix $A \in \mathbb{R}^{m \times n}$ by selecting a small subset of $c$ actual columns from $A$ to form a new matrix $C \in \mathbb{R}^{m \times c}$. We then find a coefficient matrix $X$ such that:
$$A \approx C X$$
Because $C$ consists of pure, unaltered columns from our original dataset, every basis vector retains its exact physical identity. If the original column represented the expression of a specific gene, the basis vector is that gene.
CUR decomposition takes this a step further by selecting both actual columns ($C$) and actual rows ($R$) from the matrix, linking them together with a small, low-dimensional middle matrix ($U$):
$$A \approx C U R$$
As Mahoney et al. and Wang et al. demonstrate, this dual selection preserves the structural context of both dimensions simultaneously. If $A$ is a video matrix (pixels $\times$ frames), $C$ might represent a few distinct physical pixels, while $R$ represents a few key representative frames.
The Combinatorial Challenge: Finding the Best Columns
If selecting original columns is so beneficial, why isn't it the default? The challenge is computational. Finding the absolute best $k$ columns out of $n$ to minimize reconstruction error is a hard combinatorial problem; there are $\binom{n}{k}$ possible combinations to evaluate.
To bypass this brute-force nightmare, researchers have developed two main paradigms for column selection:
1. Leverage-Score Sampling (Randomized)
The most influential insight in modern column selection is that we can use the "abstract" SVD to guide our choice of "real" columns. By computing the SVD of $A$ once, we can calculate the statistical leverage scores for each column. A column's leverage score measures how much influence it exerts over the top singular vectors.
Instead of picking columns deterministically, we treat these leverage scores as a probability distribution. As Boutsidis et al. and Yang et al. show, sampling columns proportional to their leverage scores guarantees—with high probability—that the selected subset will reconstruct the matrix with an accuracy remarkably close to the theoretical optimum. In fact, Guruswami et al. proved that choosing roughly $k/\epsilon$ columns can yield a $(1+\epsilon)$ approximation of the best possible rank-$k$ SVD.
2. Volume Sampling and Pivoting (Deterministic)
An alternative geometric intuition is to select columns that are as distinct from one another as possible. If two columns are nearly parallel, keeping both is redundant.
Volume sampling selects subsets of columns based on the volume of the parallelepiped they span in high-dimensional space (Deshpande et al.). Deterministic variants often leverage matrix factorizations like pivoted LU or QR decompositions to greedily select the most orthogonal, high-magnitude columns, ensuring stable and reproducible representations without the randomness of sampling (Chen et al.; Ida et al.).
Why It Works: Preserving Sparsity and Physics
Interpretable matrix decomposition works because it respects the underlying physical constraints of the data generation process.
When SVD creates linear combinations, it mixes dense and sparse signals, resulting in dense singular vectors. If your original data is sparse (e.g., a term-document matrix where most words don't appear in most documents), SVD destroys that sparsity, skyrocketing memory usage. Because column selection extracts raw columns, it inherently preserves the original sparsity of the data.
Furthermore, in physical systems governed by differential equations or structural networks, the data points themselves represent valid physical states. For instance, in scientific computing, Li et al. use interpolative decomposition to compress simulation data by selecting a handful of actual time-snapshots. Because these snapshots are real solutions to the underlying physical laws, engineers can analyze them directly to understand the system's dynamics, a feat impossible with abstract mathematical eigenvectors.
Ultimately, as Mahoney argues, interpretable decomposition bridges the gap between numerical linear algebra and domain-specific intuition. It reframes dimensionality reduction not as a quest for abstract mathematical purity, but as a search for the most informative, real-world exemplars within the data itself.
Key Foundational Work
Tensor-CUR decompositions for tensor-based data (2006) — contributed 2 concept elements to this direction.