Matrix completion under interval uncertainty

DOI10.1016/J.EJOR.2016.07.014MaRDI QIDQ1752160zbMATH OpenOpenAlexFDO

Authors Jakub Mareček, Peter Richtárik, M. Takáč

Publication date 24 May 2018

Published in European Journal of Operational Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1408.2467

zbMATH Keywords

matrix completioncoordinate descentrobust optimizationcollaborative filteringlarge-scale optimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Matrix completion problems (15A83)

Abstract: Matrix completion under interval uncertainty can be cast as matrix completion with element-wise box constraints. We present an efficient alternating-direction parallel coordinate-descent method for the problem. We show that the method outperforms any other known method on a benchmark in image in-painting in terms of signal-to-noise ratio, and that it provides high-quality solutions for an instance of collaborative filtering with 100,198,805 recommendations within 5 minutes.

Recommendations

• Spectral regularization algorithms for learning large incomplete matrices
• Matrix completion via an alternating direction method
• Matrix completion and low-rank SVD via fast alternating least squares
• Exact matrix completion via convex optimization
• Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm

Cites work

• scientific article; zbMATH DE number 3895043 (Why is no real title available?)
• A Singular Value Thresholding Algorithm for Matrix Completion
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• Correlation matrix nearness and completion under observation uncertainty
• Distributed block coordinate descent for minimizing partially separable functions
• Distributed coordinate descent method for learning with big data
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Exact matrix completion via convex optimization
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Generalized low rank approximations of matrices
• Geometric conditions for Kuhn-Tucker sufficiency of global optimality in mathematical programming
• Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
• Low-rank matrix completion using alternating minimization
• Matrix Completion From a Few Entries
• Normalized iterative hard thresholding for matrix completion
• Operations research and data mining
• Parallel coordinate descent methods for big data optimization
• Recent advances in robust optimization: an overview
• Robust least square semidefinite programming with applications
• Robust principal component analysis?
• Separable approximations and decomposition methods for the augmented Lagrangian
• Sparse Approximate Solutions to Linear Systems
• Spectral regularization algorithms for learning large incomplete matrices
• Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming
• The complexity of matrix completion
• `Horses for courses' in demand forecasting

Cited in

(4)

• Low-rank matrix estimation via nonconvex spectral regularized methods in errors-in-variables matrix regression
• A penalty barrier framework for nonconvex constrained optimization
• Uncertain Data Dependency Constraints in Matrix Models
• Matrix completion with sparse measurement errors

Describes a project that uses

Uses Software

• ADMiRA
• HOGWILD
• softImpute

This page was built for publication: Matrix completion under interval uncertainty

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1752160)