Regularization methods for learning incomplete matrices

2009/06/11 by Rahul Mazumder, Trevor Hastie, Mazumder, Rahul +3
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Computation (stat.CO) #FOS: Computer and information sciences #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.0906.2034

openalex publication_date 2009/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We use convex relaxation techniques to provide a sequence of solutions to the matrix completion problem. Using the nuclear norm as a regularizer, we provide simple and very efficient algorithms for minimizing the reconstruction error subject to a bound on the nuclear norm. Our algorithm iteratively replaces the missing elements with those obtained from a thresholded SVD. With warm starts this allows us to efficiently compute an entire regularization path of solutions.

Citations

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization

Related

• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• A Singular Value Thresholding Algorithm for Matrix Completion
• Calibrated Elastic Regularization in Matrix Completion
• Double Weighted Truncated Nuclear Norm Regularization for Low-Rank Matrix Completion
• Matrix Completion With Noise