Low-rank matrix completion using alternating minimization
From MaRDI portal
Abstract: Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data. For example, for the problem of low-rank matrix completion, this method is believed to be one of the most accurate and efficient, and formed a major component of the winning entry in the Netflix Challenge. In the alternating minimization approach, the low-rank target matrix is written in a bi-linear form, i.e. ; the algorithm then alternates between finding the best and the best . Typically, each alternating step in isolation is convex and tractable. However the overall problem becomes non-convex and there has been almost no theoretical understanding of when this approach yields a good result. In this paper we present first theoretical analysis of the performance of alternating minimization for matrix completion, and the related problem of matrix sensing. For both these problems, celebrated recent results have shown that they become well-posed and tractable once certain (now standard) conditions are imposed on the problem. We show that alternating minimization also succeeds under similar conditions. Moreover, compared to existing results, our paper shows that alternating minimization guarantees faster (in particular, geometric) convergence to the true matrix, while allowing a simpler analysis.
Recommendations
- Low rank matrix completion by alternating direction method of multipliers
- Low rank matrix completion by alternating steepest descent methods
- An alternating minimization method for matrix completion problems
- Matrix completion and low-rank SVD via fast alternating least squares
- Matrix completion via minimizing an approximate rank
- Matrix Completion under Low-Rank Missing Mechanism
- Matrix Completion Based on Non-Convex Low-Rank Approximation
- Matrix completion via an alternating direction method
- An ADMM-factorization algorithm for low rank matrix completion
- Low-rank matrix completion in a general non-orthogonal basis
Cited in
(only showing first 100 items - show all)- Using side information to reliably learn low-rank matrices from missing and corrupted observations
- Low rank matrix completion by alternating steepest descent methods
- Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization
- Community detection with dependent connectivity
- Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization
- Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
- Alternating minimization for generalized rank-1 matrix sensing: sharp predictions from a random initialization
- A preconditioned Riemannian gradient descent algorithm for low-rank matrix recovery
- Practical matrix completion and corruption recovery using proximal alternating robust subspace minimization
- Learning sparsely used overcomplete dictionaries via alternating minimization
- DANTE: deep alternations for training neural networks
- A new method based on the manifold-alternative approximating for low-rank matrix completion
- Fast alternating minimization method with non-monotone search for low-rank and sparse matrix recovery
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- Approximate matrix completion based on cavity method
- Collaborative filtering with information-rich and~information-sparse entities
- The alternating descent conditional gradient method for sparse inverse problems
- Orthogonal rank-one matrix pursuit for low rank matrix completion
- Enhanced image approximation using shifted rank-1 reconstruction
- Optimal prediction in the linearly transformed spiked model
- Model-free nonconvex matrix completion: local minima analysis and applications in memory-efficient kernel PCA
- A gradual rank increasing process for matrix completion
- Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
- A divide-and-conquer algorithm for binary matrix completion
- Iterative Methods for Solving Factorized Linear Systems
- Convergence of the majorized PAM method with subspace correction for low-rank composite factorization model
- Majorized proximal alternating imputation for regularized rank constrained matrix completion
- An alternating minimization method for matrix completion problems
- Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
- Matrix completion with nonconvex regularization: spectral operators and scalable algorithms
- Robust sensing of low-rank matrices with non-orthogonal sparse decomposition
- Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
- Heteroskedastic PCA: algorithm, optimality, and applications
- Alternating DC algorithm for partial DC programming problems
- The local convexity of solving systems of quadratic equations
- Learning the truth vector in high dimensions
- Matrix optimization over low-rank spectral sets: stationary points and local and global minimizers
- Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements
- A Geometry-Adaptive Regularized Newton-Type Method for Manifold-Affine Intersection Problems
- Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
- Recent Theoretical Advances in Non-Convex Optimization
- Sharp global guarantees for nonconvex low-rank recovery in the noisy overparameterized regime
- A Comparative Study of Pairwise Learning Methods Based on Kernel Ridge Regression
- Rank determination for low-rank data completion
- Matrix completion for cost reduction in finite element simulations under hybrid uncertainties
- Adaptive confidence sets for matrix completion
- Structural variability from noisy tomographic projections
- Proof methods for robust low-rank matrix recovery
- Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation
- Characterization of sampling patterns for low-tt-rank tensor retrieval
- Accelerated low rank matrix approximate algorithms for matrix completion
- Adaptive primal-dual methods with an inexact oracle for relatively smooth optimization problems and their applications to recovering low-rank matrices
- Guarantees of Riemannian optimization for low rank matrix completion
- Weighted nuclear norm minimization and its applications to low level vision
- Generalized approximate survey propagation for high-dimensional estimation *
- Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery
- scientific article; zbMATH DE number 7370536 (Why is no real title available?)
- A partial derandomization of phaselift using spherical designs
- Stable als approximation in the TT-format for rank-adaptive tensor completion
- scientific article; zbMATH DE number 7415093 (Why is no real title available?)
- scientific article; zbMATH DE number 7049740 (Why is no real title available?)
- An adaptation for iterative structured matrix completion
- Sequential stub matching for asymptotically uniform generation of directed graphs with a given degree sequence
- A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery
- Robust Matrix Completion with Heavy-Tailed Noise
- Matrix denoising for weighted loss functions and heterogeneous signals
- Toeplitz matrix completion via smoothing augmented Lagrange multiplier algorithm
- Guarantees of Riemannian optimization for low rank matrix recovery
- Low permutation-rank matrices: structural properties and noisy completion
- A semi-smoothing augmented Lagrange multiplier algorithm for low-rank Toeplitz matrix completion
- Toeplitz matrix completion via a low-rank approximation algorithm
- Flexible low-rank statistical modeling with missing data and side information
- Quantum recommendation systems
- The two-stage iteration algorithms based on the shortest distance for low-rank matrix completion
- Sparse power factorization: balancing peakiness and sample complexity
- A quadratically convergent algorithm for structured low-rank approximation
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
- Noisy tensor completion via the sum-of-squares hierarchy
- Low-rank spectral optimization via gauge duality
- Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Low-rank matrix recovery with Ky Fan 2-\(k\)-norm
- A learned proximal alternating minimization algorithm and its induced network for a class of two-block nonconvex and nonsmooth optimization
- Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
- Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
- Accelerated Alternating Projections for Robust Principal Component Analysis
- Multi-target prediction for dummies using two-branch neural networks
- One-bit tensor completion via transformed tensor singular value decomposition
- Matrix completion under interval uncertainty
- Fundamental limits of weak recovery with applications to phase retrieval
- Entrywise eigenvector analysis of random matrices with low expected rank
- Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery
- Sparse functional identification of complex cells from spike times and the decoding of visual stimuli
- A geometric analysis of phase retrieval
- Rank $2r$ Iterative Least Squares: Efficient Recovery of Ill-Conditioned Low Rank Matrices from Few Entries
- Individualized dynamic latent factor model for multi-resolutional data with application to mobile health
- Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
- Role of sparsity and structure in the optimization landscape of non-convex matrix sensing
- Decentralized and privacy-preserving low-rank matrix completion
This page was built for publication: Low-rank matrix completion using alternating minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495837)
