Interpretable Low Rank Approximations via Data Subset Selection

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2141 papers183 conceptsfrozen 2026-10-04

In the standard toolkit of data science, the Singular Value Decomposition (SVD) and Principal Component Analysis (PCA) are the undisputed workhorses for dimensionality reduction. They find the "best" low-rank approximation of a dataset by projecting it onto a new set of orthogonal axes.

However, as Zhihua Zhang notes in The Singular Value Decomposition, Applications and Beyond, these mathematically optimal axes are often "mathematical ghosts." They are linear combinations of all original features, meaning a single "principal component" might be composed of 1% of a gene's expression, 2% of a patient's age, and 0.5% of a geographic coordinate. For a biologist or a climate scientist, these abstract components are impossible to map back to physical reality.

A growing body of research suggests a more intuitive alternative: instead of inventing new, synthetic axes, we should approximate our data using a small, carefully selected subset of the actual data itself.

The Intuition of CUR Decomposition

The core idea behind this shift is the CUR decomposition. Unlike SVD, which decomposes a matrix into abstract singular vectors, CUR approximates a matrix $A$ using a subset of its actual columns ($C$) and actual rows ($R$), linked by a small scaling matrix ($U$).

As Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan demonstrate in Relative-Error CUR Matrix Decompositions, this approach preserves the "metadata" of the data. If your columns are specific documents or individual genes, your basis vectors remain specific documents or individual genes.

This is not just a matter of convenience; it is a matter of sparsity and structure. Standard SVD destroys the sparsity of the original data—even if your matrix is 99% zeros, your singular vectors will be dense. By using actual rows and columns, CUR preserves the original properties of the data, such as non-negativity and sparsity, making the results immediately actionable for domain experts.

How to Pick the Best Representatives

The fundamental challenge in this field is the Column Subset Selection Problem (CSSP): out of millions of columns, which $k$ columns best represent the entire matrix?

Early methods relied on simple heuristics, but Christos Boutsidis, Michael W. Mahoney, and Petros Drineas revolutionized this in An Improved Approximation Algorithm for the Column Subset Selection Problem by introducing randomized importance sampling. They showed that columns should be sampled based on their statistical leverage scores—a measure of how much "unique information" a column contains relative to the best low-rank space.

More recently, researchers like Tianbao Yang and Shenghuo Zhu have refined these bounds, discovering that sampling proportional to the square root of leverage scores can be even more effective for non-uniform data in An Explicit Sampling Dependent Spectral Error Bound for Column Subset Selection.

From Matrices to Tensors

Real-world data is rarely just a flat table; it often has multiple dimensions (e.g., time, space, and frequency). Michael W. Mahoney, Mauro Maggioni, and Petros Drineas extended the CUR philosophy to these higher-dimensional structures in Tensor-CUR decompositions for tensor-based data.

Instead of selecting just rows and columns, they select slabs (2D slices) and fibers (1D vectors) directly from the tensor. This allows a researcher analyzing hyperspectral images of plants, like Mirwaes Wahabzada and Christian Bauckhage in Metro Maps of Plant Disease Dynamics, to identify specific wavelengths and time points that characterize a disease, rather than abstract "spectral modes."

Anchoring to the Extremes

Another powerful way to ensure interpretability is to look at the convex hull of the data. In Convex NMF on Non-Convex Massiv Data, Kristian Kersting and colleagues argue that the most "interpretable" basis vectors are the archetypes—the data points that lie on the boundaries of the dataset.

By constraining basis vectors to be convex combinations of actual data points, methods like Convex Matrix Factorization (cvxMF) ensure that every "latent pattern" discovered by the model looks like a real, albeit idealized, example from the dataset. Abhishek Agarwal and Olgica Milenkovic have even brought this into the real-time era with Online Convex Dictionary Learning, allowing these interpretable models to scale to massive, streaming datasets.

Why It Works: The Physical Grounding

The recurring theme across these 123 papers is that interpretability is a functional requirement, not a luxury.

  1. Feature Identity: In fields like molecular dynamics, Marina Meila and Samson J. Koelle show in Isometry pursuit that we must select raw features (like bond angles) because synthetic ones have no physical meaning.
  2. Error Localization: In network anomaly detection, Minnan Luo and Huan Liu use CUR in ANOMALOUS to pinpoint exactly which attributes make a node an anomaly.
  3. Semantic Grouping: Instead of projecting features into a black box, Alberto Maria Metelli and Marcello Restelli propose aggregating correlated features into their averages in LinCFA, preserving the logical meaning of the group.

By treating the original data as the primary source of its own explanation, these methods bridge the gap between high-performance machine learning and the human-centric needs of scientific discovery.

Papers in this version

Showing 60 of 141 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 90 papers
  2. Version 1 · 2026-10-04 · 141 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_interpretable_matrix_decomposition_060d88b8,
  title = {interpretable matrix decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/interpretable-matrix-decomposition/rdr_060d88b826604de4b92b8dea71757e75},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_interpretable_low_rank_approximations_vi_060d88b8_v1,
  title = {Interpretable Low Rank Approximations via Data Subset Selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/interpretable-low-rank-approximations-via-data-subset-selection/rdr_060d88b826604de4b92b8dea71757e75/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}