# Matrix Completion Under Monotonic Single Index Models

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

## Key facts

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

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

- [ReLU Neural Networks with Linear Layers are Biased Towards Single- and Multi-Index Models](https://mlsanity.com/paper/2305.15598/) (2023)
- [Unlabeled Principal Component Analysis and Matrix Completion](https://mlsanity.com/paper/2101.09446/) (2021)
- [Beyond the Signs: Nonparametric Tensor Completion via Sign Series](https://mlsanity.com/paper/2102.00384/) (2021)
- [Symmetric Matrix Completion with ReLU Sampling](https://mlsanity.com/paper/2406.05822/) (2024)
- [An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function](https://mlsanity.com/paper/2503.23832/) (2025)
- [Nonparametric Trace Regression in High Dimensions via Sign Series Representation](https://mlsanity.com/paper/2105.01783/) (2021)
- [Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure](https://mlsanity.com/paper/2608.21607/) (2026)
- [Retraction-Based Gradient Projection Algorithms on Manifolds](https://mlsanity.com/paper/2609.30885/) (2026)

## Abstract (arXiv)

Most recent results in matrix completion assume that the matrix under consideration is low-rank or that the columns are in a union of low-rank subspaces. In real-world settings, however, the linear structure underlying these models is distorted by a (typically unknown) nonlinear transformation. This paper addresses the challenge of matrix completion in the face of such nonlinearities. Given a few observations of a matrix that are obtained by applying a Lipschitz, monotonic function to a low rank matrix, our task is to estimate the remaining unobserved entries. We propose a novel matrix completion method that alternates between low-rank matrix estimation and monotonic function estimation to estimate the missing matrix elements. Mean squared error bounds provide insight into how well the matrix can be estimated based on the size, rank of the matrix and properties of the nonlinear transformation. Empirical results on synthetic and real-world datasets demonstrate the competitiveness of the proposed approach.