Matrix completion with nonconvex regularization: spectral operators and scalable algorithms
From MaRDI portal
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., 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 matrix with 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.
Recommendations
- Spectral regularization algorithms for learning large incomplete matrices
- A Singular Value Thresholding Algorithm for Matrix Completion
- Matrix completion and low-rank SVD via fast alternating least squares
- A non-convex algorithm framework based on DC programming and DCA for matrix completion
- A nonconvex approach to low-rank matrix completion using convex optimization.
Cites work
- A Bayesian approach for noisy matrix completion: optimal rate under general sampling distribution
- A general theory of concave regularization for high-dimensional sparse estimation problems
- A simpler approach to matrix completion
- A Singular Value Thresholding Algorithm for Matrix Completion
- A Statistical View of Some Chemometrics Regression Tools
- A unified approach to model selection and sparse recovery using regularized least squares
- An extended Frank-Wolfe method with ``in-face directions, and its application to low-rank matrix completion
- Best subset selection via a modern optimization lens
- Convex Analysis
- Convex analysis and nonlinear optimization. Theory and examples.
- Does $\ell _{p}$ -Minimization Outperform $\ell _{1}$ -Minimization?
- Enhancing sparsity by reweighted \(\ell _{1}\) minimization
- Estimation of (near) low-rank matrices with noise and high-dimensional scaling
- Estimation of high-dimensional low-rank matrices
- Estimation of the mean of a multivariate normal distribution
- Exact matrix completion via convex optimization
- Guaranteed Matrix Completion via Non-Convex Factorization
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- scientific article; zbMATH DE number 47363 (Why is no real title available?)
- scientific article; zbMATH DE number 3567782 (Why is no real title available?)
- scientific article; zbMATH DE number 823379 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 3892457 (Why is no real title available?)
- scientific article; zbMATH DE number 3895043 (Why is no real title available?)
- scientific article; zbMATH DE number 6276219 (Why is no real title available?)
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Incoherence-Optimal Matrix Completion
- Iteratively reweighted least squares minimization for sparse recovery
- Least angle regression. (With discussion)
- Local Strong Homogeneity of a Regularized Estimator
- Low-rank matrix completion using alternating minimization
- Low-rank matrix recovery via iteratively reweighted least squares minimization
- Matrix completion and low-rank SVD via fast alternating least squares
- Matrix completion from noisy entries
- Matrix Completion With Deterministic Pattern: A Geometric Perspective
- Nearly unbiased variable selection under minimax concave penalty
- Noisy low-rank matrix completion with general sampling distribution
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
- One-step sparse estimates in nonconcave penalized likelihood models
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- Regularization and the small-ball method. I: Sparse recovery
- Regularized \(M\)-estimators with nonconvexity: statistical and algorithmic theory for local optima
- Restricted strong convexity and weighted matrix completion: optimal bounds with noise
- Sorted concave penalized regression
- SparseNet: coordinate descent with nonconvex penalties
- Spectral analysis of large dimensional random matrices
- Spectral regularization algorithms for learning large incomplete matrices
- The Adaptive Lasso and Its Oracle Properties
- The Discrete Dantzig Selector: Estimating Sparse Linear Models via Mixed Integer Linear Optimization
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- Unbiased Risk Estimates for Singular Value Thresholding and Spectral Estimators
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
- Weighted nuclear norm minimization and its applications to low level vision
Cited in
(7)- Gradient flow methods for matrix completion with prescribed eigenvalues.
- Flexible low-rank statistical modeling with missing data and side information
- Computing the degrees of freedom of rank-regularized estimators and cousins
- Majorized proximal alternating imputation for regularized rank constrained matrix completion
- A non-convex algorithm framework based on DC programming and DCA for matrix completion
- Spectral regularization algorithms for learning large incomplete matrices
- Matrix completion via max-norm constrained optimization
Describes a project that uses
Uses Software
This page was built for publication: Matrix completion with nonconvex regularization: spectral operators and scalable algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2195855)
