# Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms

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

## Key facts

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

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

- [A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples](https://mlsanity.com/paper/2106.02119/) (2021)
- [Multi-channel Nuclear Norm Minus Frobenius Norm Minimization for Color Image Denoising](https://mlsanity.com/paper/2209.08094/) (2022)
- [Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion](https://mlsanity.com/paper/2305.12292/) (2023)
- [Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization](https://mlsanity.com/paper/2205.03059/) (2022)
- [Learning Transition Operators From Sparse Space-Time Samples](https://mlsanity.com/paper/2212.00746/) (2022)

## Abstract (arXiv)

In this paper, we study the popularly dubbed matrix completion problem, where the task is to "fill in" the unobserved entries of a matrix from a small subset of observed entries, under the assumption that the underlying matrix is of low-rank. Our contributions herein, enhance our prior work on nuclear norm regularized problems for matrix completion (Mazumder et al., 2010) by incorporating a continuum of nonconvex penalty functions between the convex nuclear norm and nonconvex rank functions. Inspired by SOFT-IMPUTE (Mazumder et al., 2010; Hastie et al., 2016), we propose NC-IMPUTE- an EM-flavored algorithmic framework for computing a family of nonconvex penalized matrix completion problems with warm-starts. We present a systematic study of the associated spectral thresholding operators, which play an important role in the overall algorithm. We study convergence properties of the algorithm. Using structured low-rank SVD computations, we demonstrate the computational scalability of our proposal for problems up to the Netflix size (approximately, a 500,000 × 20, 000 matrix with 108 observed entries). We demonstrate that on a wide range of synthetic and real data instances, our proposed nonconvex regularization framework leads to low-rank solutions with better predictive performance when compared to those obtained from nuclear norm problems. Implementations of algorithms proposed herein, written in the R programming language, are made available on github.