A Geometric Approach to Low-Rank Matrix Completion

DOI10.1109/TIT.2011.2171521MaRDI QIDQ5272162zbMATH OpenOpenAlexFDO

Authors

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Matrix completion problems (15A83) Synthetic treatment of fundamental manifolds in projective geometries (Grassmannians, Veronesians and their generalizations) (51M35)

Abstract: The low-rank matrix completion problem can be succinctly stated as follows: given a subset of the entries of a matrix, find a low-rank matrix consistent with the observations. While several low-complexity algorithms for matrix completion have been proposed so far, it remains an open problem to devise search procedures with provable performance guarantees for a broad class of matrix models. The standard approach to the problem, which involves the minimization of an objective function defined using the Frobenius metric, has inherent difficulties: the objective function is not continuous and the solution set is not closed. To address this problem, we consider an optimization procedure that searches for a column (or row) space that is geometrically consistent with the partial observations. The geometric objective function is continuous everywhere and the solution set is the closure of the solution set of the Frobenius metric. We also preclude the existence of local minimizers, and hence establish strong performance guarantees, for special completion scenarios, which do not require matrix incoherence or large matrix size.

Cited in

(13)

• Two Newton methods on the manifold of fixed-rank matrices endowed with Riemannian quotient geometries
• Fixed-rank matrix factorizations and Riemannian low-rank optimization
• A Riemannian gossip approach to subspace learning on Grassmann manifold
• Low-rank matrix completion via preconditioned optimization on the Grassmann manifold
• A Broyden class of quasi-Newton methods for Riemannian optimization
• Geometric Methods on Low-Rank Matrix and Tensor Manifolds
• Exact low-rank matrix completion from sparsely corrupted entries via adaptive outlier pursuit
• Riemannian modified Polak-Ribière-Polyak conjugate gradient order reduced model by tensor techniques
• Intrinsic representation of tangent vectors and vector transports on matrix manifolds
• Embedding graphs on Grassmann manifold
• Robust optimization and inference on manifolds
• A worst-case complexity analysis for Riemannian non-monotone line-search methods
• An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function

This page was built for publication: A Geometric Approach to Low-Rank Matrix Completion

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