Low-rank matrix completion by Riemannian optimization
From MaRDI portal
Publication:2848192
DOI10.1137/110845768zbMATH Open1277.15021arXiv1209.3834OpenAlexW2058078260WikidataQ115247017 ScholiaQ115247017MaRDI QIDQ2848192FDOQ2848192
Authors: Bart Vandereycken 
Publication date: 25 September 2013
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: The matrix completion problem consists of finding or approximating a low-rank matrix based on a few samples of this matrix. We propose a new algorithm for matrix completion that minimizes the least-square distance on the sampling set over the Riemannian manifold of fixed-rank matrices. The algorithm is an adaptation of classical non-linear conjugate gradients, developed within the framework of retraction-based optimization on manifolds. We describe all the necessary objects from differential geometry necessary to perform optimization over this low-rank matrix manifold, seen as a submanifold embedded in the space of matrices. In particular, we describe how metric projection can be used as retraction and how vector transport lets us obtain the conjugate search directions. Finally, we prove convergence of a regularized version of our algorithm under the assumption that the restricted isometry property holds for incoherent matrices throughout the iterations. The numerical experiments indicate that our approach scales very well for large-scale problems and compares favorably with the state-of-the-art, while outperforming most existing solvers.
Full work available at URL: https://arxiv.org/abs/1209.3834
Recommendations
- Guarantees of Riemannian optimization for low rank matrix completion
- A Riemannian rank-adaptive method for low-rank matrix completion
- Low-rank matrix completion via preconditioned optimization on the Grassmann manifold
- Robust low-rank matrix completion by Riemannian optimization
- Riemannian conjugate gradient method for low-rank tensor completion
matrix completionRiemannian manifoldsdifferential geometrylow-rank matricesoptimization on manifoldsnonlinear conjugate gradients
Numerical mathematical programming methods (65K05) Matrix completion problems (15A83) Methods of local Riemannian geometry (53B21)
Cited In (only showing first 100 items - show all)
- A Riemannian subspace BFGS trust region method
- Low-rank optimization with trace norm penalty
- Hybrid Riemannian conjugate gradient methods with global convergence properties
- Reconstruction of jointly sparse vectors via manifold optimization
- Low-rank tensor completion by Riemannian optimization
- Intrinsic representation of tangent vectors and vector transports on matrix manifolds
- Sufficient descent Riemannian conjugate gradient methods
- Low-rank matrix completion via preconditioned optimization on the Grassmann manifold
- Guarantees of Riemannian optimization for low rank matrix recovery
- Toeplitz matrix completion via smoothing augmented Lagrange multiplier algorithm
- \(\varepsilon\)-subgradient algorithms for locally Lipschitz functions on Riemannian manifolds
- A semi-smoothing augmented Lagrange multiplier algorithm for low-rank Toeplitz matrix completion
- Toeplitz matrix completion via a low-rank approximation algorithm
- Some empirical advances in matrix completion
- Riemannian optimization for high-dimensional tensor completion
- Convergence results for projected line-search methods on varieties of low-rank matrices via Łojasiewicz inequality
- The two-stage iteration algorithms based on the shortest distance for low-rank matrix completion
- Sensitivity of low-rank matrix recovery
- A quadratically convergent algorithm for structured low-rank approximation
- A penalty method for rank minimization problems in symmetric matrices
- Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
- Accelerated Alternating Projections for Robust Principal Component Analysis
- Efficient Weingarten map and curvature estimation on manifolds
- Riemannian optimization for phase retrieval from masked Fourier measurements
- A Riemannian BFGS method without differentiated retraction for nonconvex optimization problems
- A gradient sampling method on algebraic varieties and application to nonsmooth low-rank optimization
- Riemannian conjugate gradient methods with inverse retraction
- Online learning in the embedded manifold of low-rank matrices
- Reduction of nonlinear embedded boundary models for problems with evolving interfaces
- A brief introduction to manifold optimization
- A nonmonotone trust region method for unconstrained optimization problems on Riemannian manifolds
- Riemannian gradient descent methods for graph-regularized matrix completion
- A limited-memory Riemannian symmetric rank-one trust-region method with a restart strategy
- Fast Cadzow's algorithm and a gradient variant
- Differentiable piecewise-Bézier surfaces on Riemannian manifolds
- Adaptive quadratically regularized Newton method for Riemannian optimization
- Matrix completion for matrices with low-rank displacement
- Nonnegative low rank matrix approximation for nonnegative matrices
- Fixed-rank matrix factorizations and Riemannian low-rank optimization
- A kind of ill-posed inverse problem solving with sparsity constraint
- A gradient system for low rank matrix completion
- Low-rank nonnegative matrix factorization on Stiefel manifold
- Low rank tensor recovery via iterative hard thresholding
- Robust low-rank matrix completion by Riemannian optimization
- Memoryless quasi-Newton methods based on the spectral-scaling Broyden family for Riemannian optimization
- An ADMM-factorization algorithm for low rank matrix completion
- A Broyden class of quasi-Newton methods for Riemannian optimization
- An efficient method for non-negative low-rank completion
- Low-rank matrix completion in a general non-orthogonal basis
- Preserving Lagrangian structure in nonlinear model reduction with application to structural dynamics
- Low rank matrix completion by alternating steepest descent methods
- Two Newton methods on the manifold of fixed-rank matrices endowed with Riemannian quotient geometries
- Tensor completion in hierarchical tensor representations
- Stability analysis of hierarchical tensor methods for time-dependent PDEs
- A Riemannian gradient sampling algorithm for nonsmooth optimization on manifolds
- An extended Frank-Wolfe method with ``in-face directions, and its application to low-rank matrix completion
- A hybrid Riemannian conjugate gradient method for nonconvex optimization problems
- Low-rank retractions: a survey and new results
- Robust principal component pursuit via inexact alternating minimization on matrix manifolds
- Exact low-rank matrix completion from sparsely corrupted entries via adaptive outlier pursuit
- Tensor networks and hierarchical tensors for the solution of high-dimensional partial differential equations
- Riemannian multigrid line search for low-rank problems
- Painless breakups -- efficient demixing of low rank matrices
- A Riemannian subspace limited-memory SR1 trust region method
- Exact matrix completion based on low rank Hankel structure in the Fourier domain
- Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion
- The geometry of algorithms using hierarchical tensors
- A geometric approach to dynamical model order reduction
- Jacobi-Davidson method on low-rank matrix manifolds
- Preconditioned low-rank Riemannian optimization for linear systems with tensor product structure
- Nonlinear matrix recovery using optimization on the Grassmann manifold
- Hierarchical compressed sensing
- Low-rank Riemannian eigensolver for high-dimensional Hamiltonians
- The Extrinsic Geometry of Dynamical Systems Tracking Nonlinear Matrix Projections
- Accurate and fast matrix factorization for low-rank learning.
- Fast gradient method for low-rank matrix estimation
- Proximal linearization methods for Schatten \(p\)-quasi-norm minimization
- Alternating least squares as moving subspace correction
- Riemannian preconditioning
- One-bit tensor completion via transformed tensor singular value decomposition
- Rank $2r$ Iterative Least Squares: Efficient Recovery of Ill-Conditioned Low Rank Matrices from Few Entries
- AN EFFICIENT METHOD FOR SOLVING A CLASS OF MATRIX TRACE FUNCTION MINIMIZATION PROBLEM IN MULTIVARIATE STATISTICAL
- A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds
- Riemannian conjugate gradient method for low-rank tensor completion
- Optimization on flag manifolds
- Survey on matrix completion models and algorithms
- Optimization on matrix manifold based on gradient information and its applications in network control
- Fenchel Duality and a Separation Theorem on Hadamard Manifolds
- Harmonic mean iteratively reweighted least squares for low-rank matrix recovery
- An equivalence between critical points for rank constraints versus low-rank factorizations
- Riemannian thresholding methods for row-sparse and low-rank matrix recovery
- Robust PCA by manifold optimization
- An efficient damped Newton-type algorithm with globalization strategy on Riemannian manifolds
- Geometric Methods on Low-Rank Matrix and Tensor Manifolds
- A new method based on the manifold-alternative approximating for low-rank matrix completion
- Normal Cones Intersection Rule and Optimality Analysis for Low-Rank Matrix Optimization with Affine Manifolds
- Proximal gradient method for nonsmooth optimization over the Stiefel manifold
- Riemannian gradient methods for stochastic composition problems
- A trust region method for solving multicriteria optimization problems on Riemannian manifolds
- A Riemannian rank-adaptive method for low-rank matrix completion
Uses Software
This page was built for publication: Low-rank matrix completion by Riemannian optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848192)
