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)- Matrix completion via a low rank factorization model and an augmented Lagrangean succesive overrelaxation algorithm
- Matrix completion discriminant analysis
- A gradual rank increasing process for matrix completion
- Adaptive confidence sets for matrix completion
- The two-stage iteration algorithms based on the shortest distance for low-rank matrix completion
- Matrix completion under interval uncertainty
- A geometric analysis of phase retrieval
- Flexible low-rank statistical modeling with missing data and side information
- Practical matrix completion and corruption recovery using proximal alternating robust subspace minimization
- Fast rank-one alternating minimization algorithm for phase retrieval
- Sparse power factorization: balancing peakiness and sample complexity
- Toeplitz matrix completion via smoothing augmented Lagrange multiplier algorithm
- Riemannian gradient descent methods for graph-regularized matrix completion
- A nonmonotone trust region method for unconstrained optimization problems on Riemannian manifolds
- Quartic first-order methods for low-rank minimization
- Low-rank matrix completion in a general non-orthogonal basis
- Ranking recovery from limited pairwise comparisons using low-rank matrix completion
- Inductive matrix completion with feature selection
- Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
- Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization
- Community detection with dependent connectivity
- Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
- DANTE: deep alternations for training neural networks
- A new method based on the manifold-alternative approximating for low-rank matrix completion
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- A semi-smoothing augmented Lagrange multiplier algorithm for low-rank Toeplitz matrix completion
- Toeplitz matrix completion via a low-rank approximation algorithm
- An adaptation for iterative structured matrix completion
- Proof methods for robust low-rank matrix recovery
- Heteroskedastic PCA: algorithm, optimality, and applications
- Low-rank matrix recovery with Ky Fan 2-\(k\)-norm
- Alternating DC algorithm for partial DC programming problems
- Multi-target prediction for dummies using two-branch neural networks
- Role of sparsity and structure in the optimization landscape of non-convex matrix sensing
- Noisy tensor completion via the sum-of-squares hierarchy
- Enhanced alternating energy minimization methods for stochastic Galerkin matrix equations
- Matrix completion methods for the total electron content video reconstruction
- Guarantees of Riemannian optimization for low rank matrix completion
- Enhanced image approximation using shifted rank-1 reconstruction
- Optimal prediction in the linearly transformed spiked model
- An alternating minimization method for matrix completion problems
- A divide-and-conquer algorithm for binary matrix completion
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Weighted nuclear norm minimization and its applications to low level vision
- Matrix completion with nonconvex regularization: spectral operators and scalable algorithms
- Entrywise eigenvector analysis of random matrices with low expected rank
- Characterization of sampling patterns for low-tt-rank tensor retrieval
- Matrix completion for matrices with low-rank displacement
- Accelerated low rank matrix approximate algorithms for matrix completion
- Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
- Multi-target prediction: a unifying view on problems and methods
- A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery
- One-bit tensor completion via transformed tensor singular value decomposition
- Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
- Majorized proximal alternating imputation for regularized rank constrained matrix completion
- Learning the truth vector in high dimensions
- Matrix optimization over low-rank spectral sets: stationary points and local and global minimizers
- Provable accelerated gradient method for nonconvex low rank optimization
- Matrix completion for cost reduction in finite element simulations under hybrid uncertainties
- Stable als approximation in the TT-format for rank-adaptive tensor completion
- A partial derandomization of phaselift using spherical designs
- Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery
- The local convexity of solving systems of quadratic equations
- Fundamental limits of weak recovery with applications to phase retrieval
- Collaborative filtering with information-rich and~information-sparse entities
- Decentralized and privacy-preserving low-rank matrix completion
- Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements
- Low-rank spectral optimization via gauge duality
- Guarantees of Riemannian optimization for low rank matrix recovery
- Efficient matrix sensing using rank-1 Gaussian measurements
- A quadratically convergent algorithm for structured low-rank approximation
- Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
- Iterative Methods for Solving Factorized Linear Systems
- Learning sparsely used overcomplete dictionaries via alternating minimization
- Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation
- Dynamic assortment personalization in high dimensions
- Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
- Learning from comparisons and choices
- Harmonic mean iteratively reweighted least squares for low-rank matrix recovery
- Using side information to reliably learn low-rank matrices from missing and corrupted observations
- Robust PCA by manifold optimization
- Low-Rank Matrix Completion in the Presence of High Coherence
- Accelerated Alternating Projections for Robust Principal Component Analysis
- scientific article; zbMATH DE number 7049740 (Why is no real title available?)
- Rank determination for low-rank data completion
- Quantum recommendation systems
- Adapting regularized low-rank models for parallel architectures
- Structural variability from noisy tomographic projections
- Estimation of a low-rank topic-based model for information cascades
- Matrix completion and related problems via strong duality
- Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
- Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
- Ranking and synchronization from pairwise measurements via SVD
- Exponential-Family Embedding With Application to Cell Developmental Trajectories for Single-Cell RNA-Seq Data
- Rank $2r$ Iterative Least Squares: Efficient Recovery of Ill-Conditioned Low Rank Matrices from Few Entries
- Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
- Column \(\ell_{2,0}\)-norm regularized factorization model of low-rank matrix recovery and its computation
- GNMR: a provable one-line algorithm for low rank matrix recovery
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)
