# Classification with Low Rank and Missing Data

arXiv: https://arxiv.org/abs/1501.03273 · HTML: https://mlsanity.com/paper/1501.03273/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jan 2015.

## Built on by (most cited first, 9 of 9)

- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Adversarially Robust PAC Learnability of Real-Valued Functions](https://mlsanity.com/paper/2206.12977/) (2022)
- [MisConv: Convolutional Neural Networks for Missing Data](https://mlsanity.com/paper/2110.14010/) (2021)
- [Knockout: A simple way to handle missing inputs](https://mlsanity.com/paper/2405.20448/) (2024)
- [Data Imputation by Pursuing Better Classification: A Supervised Kernel-Based Method](https://mlsanity.com/paper/2405.07800/) (2024)
- [Cloned Identity Detection in Social-Sensor Clouds based on Incomplete Profiles](https://mlsanity.com/paper/2411.01329/) (2024)
- [SparGE: Sparse Coding-based Patient Similarity Learning via Low-rank Constraints and Graph Embedding](https://mlsanity.com/paper/2202.01427/) (2022)
- [An Interdisciplinary and Cross-Task Review on Missing Data Imputation](https://mlsanity.com/paper/2511.01196/) (2025)

## Abstract (arXiv)

We consider classification and regression tasks where we have missing data and assume that the (clean) data resides in a low rank subspace. Finding a hidden subspace is known to be computationally hard. Nevertheless, using a non-proper formulation we give an efficient agnostic algorithm that classifies as good as the best linear classifier coupled with the best low-dimensional subspace in which the data resides. A direct implication is that our algorithm can linearly (and non-linearly through kernels) classify provably as well as the best classifier that has access to the full data.