An adaptation for iterative structured matrix completion

DOI10.3934/FODS.2021028MaRDI QIDQ2072669zbMATH OpenOpenAlexWikidataFDO

Authors Henry Adams, Lara Kassab, D. Needell

Publication date 26 January 2022

Published in Foundations of Data Science (Search for Journal in Brave)

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

zbMATH Keywords

gradient-projection methodsiteratively reweighted algorithmslow-rank matrix completionsparse matricesstructured matrix completion

Mathematics Subject Classification ID

Matrix completion problems (15A83) Computational methods for sparse matrices (65F50) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Abstract: The task of predicting missing entries of a matrix, from a subset of known entries, is known as extit{matrix completion}. In today's data-driven world, data completion is essential whether it is the main goal or a pre-processing step. Structured matrix completion includes any setting in which data is not missing uniformly at random. In recent work, a modification to the standard nuclear norm minimization (NNM) for matrix completion has been developed to take into account emph{sparsity-based} structure in the missing entries. This notion of structure is motivated in many settings including recommender systems, where the probability that an entry is observed depends on the value of the entry. We propose adjusting an Iteratively Reweighted Least Squares (IRLS) algorithm for low-rank matrix completion to take into account sparsity-based structure in the missing entries. We also present an iterative gradient-projection-based implementation of the algorithm that can handle large-scale matrices. Finally, we present a robust array of numerical experiments on matrices of varying sizes, ranks, and level of structure. We show that our proposed method is comparable with the adjusted NNM on small-sized matrices, and often outperforms the IRLS algorithm in structured settings on matrices up to size $1000imes1000$.

Recommendations

• Adaptive and Implicit Regularization for Matrix Completion
• Matrix completion via an alternating direction method
• Adaptive Low Rank Matrix Completion
• An ADMM-factorization algorithm for low rank matrix completion
• Structured matrix estimation and completion
• Adaptive multinomial matrix completion
• A Riemannian rank-adaptive method for low-rank matrix completion
• An alternating minimization method for matrix completion problems
• Some empirical advances in matrix completion
• Matrix completion via minimizing an approximate rank

Cites work

• A remark on global positioning from local distances
• A simpler approach to matrix completion
• A Singular Value Thresholding Algorithm for Matrix Completion
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
• Completing any low-rank matrix, provably
• Convergence of fixed-point continuation algorithms for matrix rank minimization
• Decoding by Linear Programming
• Exact matrix completion via convex optimization
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Fixed point and Bregman iterative methods for matrix rank minimization
• Graph implementations for nonsmooth convex programs
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Harmonic mean iteratively reweighted least squares for low-rank matrix recovery
• scientific article; zbMATH DE number 6276219 (Why is no real title available?)
• Imputation and low-rank estimation with missing not at random data
• Interior-point method for nuclear norm approximation with application to system identification
• Iteratively reweighted least squares minimization for sparse recovery
• Low-rank matrix completion using alternating minimization
• Low-rank matrix recovery via iteratively reweighted least squares minimization
• Main effects and interactions in mixed and incomplete data frames
• Rank-Sparsity Incoherence for Matrix Decomposition
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Robust principal component analysis?
• The geometry of graphs and some of its algorithmic applications
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Theory of semidefinite programming for sensor network localization
• Uncertainty Principles and Signal Recovery
• Weighted low rank approximations with provable guarantees

Cited in

(3)

• Contravariant adaptation on structured matrix spaces
• Adaptive and Implicit Regularization for Matrix Completion
• Iterative rank-one matrix completion via singular value decomposition and nuclear norm regularization

Describes a project that uses

Uses Software

• CVX
• ADMiRA
• GitHub

This page was built for publication: An adaptation for iterative structured matrix completion

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