# NoisyCUR: An algorithm for two-cost budgeted matrix completion

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 24 references that are in the map.
- First posted on arXiv 16 Apr 2021.

## Builds on (most cited first, 11 of 11)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [A Statistical Perspective on Algorithmic Leveraging](https://mlsanity.com/paper/1306.5362/) (2013)
- [Low-Rank Matrix and Tensor Completion via Adaptive Sampling](https://mlsanity.com/paper/1304.4672/) (2013)
- [Sharper Bounds for Regularized Data Fitting](https://mlsanity.com/paper/1611.03225/) (2016)
- [Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging](https://mlsanity.com/paper/1702.04837/) (2017)
- [On the Power of Adaptivity in Matrix Completion and Approximation](https://mlsanity.com/paper/1407.3619/) (2014)
- [CUR Algorithm for Partially Observed Matrices](https://mlsanity.com/paper/1411.0860/) (2014)
- [Noise-Tolerant Life-Long Matrix Completion via Adaptive Sampling](https://mlsanity.com/paper/1612.00100/) (2016)
- [Completing Any Low-rank Matrix, Provably](https://mlsanity.com/paper/1306.2979/) (2013)

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

- [Graph-incorporated Latent Factor Analysis for High-dimensional and Sparse Matrices](https://mlsanity.com/paper/2204.07818/) (2022)

## Abstract (arXiv)

Matrix completion is a ubiquitous tool in machine learning and data analysis. Most work in this area has focused on the number of observations necessary to obtain an accurate low-rank approximation. In practice, however, the cost of observations is an important limiting factor, and experimentalists may have on hand multiple modes of observation with differing noise-vs-cost trade-offs. This paper considers matrix completion subject to such constraints: a budget is imposed and the experimentalist's goal is to allocate this budget between two sampling modalities in order to recover an accurate low-rank approximation. Specifically, we consider that it is possible to obtain low noise, high cost observations of individual entries or high noise, low cost observations of entire columns. We introduce a regression-based completion algorithm for this setting and experimentally verify the performance of our approach on both synthetic and real data sets. When the budget is low, our algorithm outperforms standard completion algorithms. When the budget is high, our algorithm has comparable error to standard nuclear norm completion algorithms and requires much less computational effort.