Matrix completion via max-norm constrained optimization
From MaRDI portal
Abstract: Matrix completion has been well studied under the uniform sampling model and the trace-norm regularized methods perform well both theoretically and numerically in such a setting. However, the uniform sampling model is unrealistic for a range of applications and the standard trace-norm relaxation can behave very poorly when the underlying sampling scheme is non-uniform. In this paper we propose and analyze a max-norm constrained empirical risk minimization method for noisy matrix completion under a general sampling model. The optimal rate of convergence is established under the Frobenius norm loss in the context of approximately low-rank matrix reconstruction. It is shown that the max-norm constrained method is minimax rate-optimal and yields a unified and robust approximate recovery guarantee, with respect to the sampling distributions. The computational effectiveness of this method is also discussed, based on first-order algorithms for solving convex optimizations involving max-norm regularization.
Recommendations
- Exact matrix completion via convex optimization
- Maximum rank matrix completion
- Matrix completion via an alternating direction method
- A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- Matrix completion via minimizing an approximate rank
- An alternating minimization method for matrix completion problems
- Matrix completion with nonconvex regularization: spectral operators and scalable algorithms
- The \(N_{0}^{1}\)-matrix completion problem
- On a Class of Matrix Completion Problems
Cites work
- scientific article; zbMATH DE number 4032351 (Why is no real title available?)
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- scientific article; zbMATH DE number 194093 (Why is no real title available?)
- scientific article; zbMATH DE number 1064667 (Why is no real title available?)
- scientific article; zbMATH DE number 2034517 (Why is no real title available?)
- 1-bit matrix completion
- 10.1162/153244303321897690
- A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
- A simpler approach to matrix completion
- Complexity measures of sign matrices
- Computational enhancements in low-rank semidefinite programming
- Construction of high-order deceptive functions using low-order Walsh coefficients
- Estimation of (near) low-rank matrices with noise and high-dimensional scaling
- Estimation of high-dimensional low-rank matrices
- Exact matrix completion via convex optimization
- Generalized alternating direction method of multipliers: new theoretical insights and applications
- Gradient methods for minimizing composite functions
- Information-theoretic determination of minimax rates of convergence
- Interior-point method for nuclear norm approximation with application to system identification
- Learning Theory
- Matrix completion from noisy entries
- Max-norm optimization for robust matrix recovery
- Noisy low-rank matrix completion with general sampling distribution
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
- Rank estimation in missing data matrix problems
- Rank penalized estimators for high-dimensional matrices
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- Restricted strong convexity and weighted matrix completion: optimal bounds with noise
- Scaled sparse linear regression
- Spectral regularization algorithms for learning large incomplete matrices
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
- Uniqueness of low-rank matrix completion by rigidity theory
- User-friendly tail bounds for sums of random matrices
- Von Neumann entropy penalization and low-rank matrix estimation
Cited in
(33)- Adaptive multinomial matrix completion
- Deterministic tensor completion with hypergraph expanders
- Covariate-assisted matrix completion with multiple structural breaks
- Learning Theory
- Robust Schatten-\(p\) norm based approach for tensor completion
- Matrix Completion under Low-Rank Missing Mechanism
- Structured matrix estimation and completion
- Restricted strong convexity and weighted matrix completion: optimal bounds with noise
- Matrix completion with covariate information
- Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
- Matrix completion under complex survey sampling
- Noisy low-rank matrix completion with general sampling distribution
- Robust low-rank matrix estimation
- Collective matrix completion
- Regularization and the small-ball method. II: Complexity dependent error rates
- Leave-One-Out Approach for Matrix Completion: Primal and Dual Analysis
- Geometric inference for general high-dimensional linear inverse problems
- Adaptive and Implicit Regularization for Matrix Completion
- Matrix completion from a computational statistics perspective
- Matrix completion with the trace norm: learning, bounding, and transducing
- Max-norm optimization for robust matrix recovery
- A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
- Unitary dilation approach to contractive matrix completion.
- Recovery of low-rank matrices based on the rank null space properties
- scientific article; zbMATH DE number 7306912 (Why is no real title available?)
- Constrained \((0,1)\)-matrix completion with a staircase of fixed zeros
- Cross: efficient low-rank tensor completion
- Adaptive confidence sets for matrix completion
- Online optimization for max-norm regularization
- Robust matrix completion
- Matrix completion by singular value thresholding: sharp bounds
- MC2: a two-phase algorithm for leveraged matrix completion
- Into the unknown: assigning reviewers to papers with uncertain affinities
This page was built for publication: Matrix completion via max-norm constrained optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q302432)
