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)
- 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
- The Condition Number of Riemannian Approximation Problems
- A Riemannian gossip approach to subspace learning on Grassmann manifold
- Blind deconvolution by a steepest descent algorithm on a quotient manifold
- Low-rank matrix iteration using polynomial-filtered subspace extraction
- Iterative rank-one matrix completion via singular value decomposition and nuclear norm regularization
- An alternative to EM for Gaussian mixture models: batch and stochastic Riemannian optimization
- Matrix completion with sparse measurement errors
- Majorized proximal alternating imputation for regularized rank constrained matrix completion
- Finding stationary points on bounded-rank matrices: a geometric hurdle and a smooth remedy
- Recent Advances in Stochastic Riemannian Optimization
- Empirical Bayes matrix completion
- A global exact penalty for rank-constrained optimization problem and applications
- Nonconvex weak sharp minima on Riemannian manifolds
- Tracking and Regret Bounds for Online Zeroth-Order Euclidean and Riemannian Optimization
- Sequential quadratic optimization for nonlinear optimization problems on Riemannian manifolds
- Accelerated low rank matrix approximate algorithms for matrix completion
- Riemannian optimization via Frank-Wolfe methods
- Riemannian conjugate gradient descent method for fixed multi rank third-order tensor completion
- Desingularization of bounded-rank matrix sets
- Guarantees of Riemannian optimization for low rank matrix completion
- Analysis of asymptotic escape of strict saddle sets in manifold optimization
- An image inpainting algorithm using exemplar matching and low-rank sparse prior
- A Riemannian Framework for Low-Rank Structured Elliptical Models
- Computing eigenspaces with low rank constraints
- Automatic differentiation for Riemannian optimization on low-rank matrix and tensor-train manifolds
- From low-rank retractions to dynamical low-rank approximation and back
- An improved Riemannian conjugate gradient method and its application to robust matrix completion
- Dynamically Orthogonal Runge–Kutta Schemes with Perturbative Retractions for the Dynamical Low-Rank Approximation
- Stochastic variance reduced gradient for affine rank minimization problem
- Implicit low-rank Riemannian schemes for the time integration of stiff partial differential equations
- Modified memoryless spectral-scaling Broyden family on Riemannian manifolds
- Continuation methods for Riemannian optimization
- Multi-dimensional scaling from \(K\)-nearest neighbourhood distances
- GNMR: a provable one-line algorithm for low rank matrix recovery
- Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
- A nonlocal low-rank regularization method for fractal image coding
- Nonnegative Low Rank Matrix Completion by Riemannian Optimalization Methods
- An efficient algorithm for solving a class of matrix optimization problem in scalable probabilistic approximation
- Riemannian trust region methods for \(\mathrm{SC}^1\) minimization
- Robust recovery of Robinson property in \(L^p\)-graphons: a cut-norm approach
- An entropy-regularized ADMM for binary quadratic programming
- A framework of regularized low-rank matrix models for regression and classification
- A preconditioned Riemannian gradient descent algorithm for low-rank matrix recovery
- Constructing low-rank Tucker tensor approximations using generalized completion
- Hermite interpolation with retractions on manifolds
- Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
- Adaptive trust-region method on Riemannian manifold
- A Riemannian conjugate gradient approach for solving the generalized eigenvalue problem with minimal perturbation
- Nonsmooth optimization over the Stiefel manifold and beyond: proximal gradient method and recent variants
- Practical gradient and conjugate gradient methods on flag manifolds
- Low rank pure quaternion approximation for pure quaternion matrices
- 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
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)
