Matrix completion with nonconvex regularization: spectral operators and scalable algorithms
Abstract 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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2021
|
| Online Access: | https://hdl.handle.net/1721.1/131497 |
| _version_ | 1811080369057824768 |
|---|---|
| author | Mazumder, Rahul Saldana, Diego Weng, Haolei |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Mazumder, Rahul Saldana, Diego Weng, Haolei |
| author_sort | Mazumder, Rahul |
| collection | MIT |
| description | Abstract
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. in J Mach Learn Res 1532(11):2287–2322, 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. in J Mach Learn Res, 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 $$\times $$× 20,000 matrix with $$10^8$$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 language, are made available on github. |
| first_indexed | 2024-09-23T11:30:19Z |
| format | Article |
| id | mit-1721.1/131497 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:30:19Z |
| publishDate | 2021 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1314972023-12-18T19:51:09Z Matrix completion with nonconvex regularization: spectral operators and scalable algorithms Mazumder, Rahul Saldana, Diego Weng, Haolei Sloan School of Management Abstract 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. in J Mach Learn Res 1532(11):2287–2322, 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. in J Mach Learn Res, 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 $$\times $$× 20,000 matrix with $$10^8$$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 language, are made available on github. 2021-09-20T17:17:19Z 2021-09-20T17:17:19Z 2020-03-14 2020-09-24T21:26:22Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/131497 en https://doi.org/10.1007/s11222-020-09939-5 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer Science+Business Media, LLC, part of Springer Nature application/pdf Springer US Springer US |
| spellingShingle | Mazumder, Rahul Saldana, Diego Weng, Haolei Matrix completion with nonconvex regularization: spectral operators and scalable algorithms |
| title | Matrix completion with nonconvex regularization: spectral operators and scalable algorithms |
| title_full | Matrix completion with nonconvex regularization: spectral operators and scalable algorithms |
| title_fullStr | Matrix completion with nonconvex regularization: spectral operators and scalable algorithms |
| title_full_unstemmed | Matrix completion with nonconvex regularization: spectral operators and scalable algorithms |
| title_short | Matrix completion with nonconvex regularization: spectral operators and scalable algorithms |
| title_sort | matrix completion with nonconvex regularization spectral operators and scalable algorithms |
| url | https://hdl.handle.net/1721.1/131497 |
| work_keys_str_mv | AT mazumderrahul matrixcompletionwithnonconvexregularizationspectraloperatorsandscalablealgorithms AT saldanadiego matrixcompletionwithnonconvexregularizationspectraloperatorsandscalablealgorithms AT wenghaolei matrixcompletionwithnonconvexregularizationspectraloperatorsandscalablealgorithms |