Guarantees of Riemannian Optimization for Low Rank Matrix Recovery

DOI10.1137/15M1050525zbMath1347.65109arXiv1511.01562OpenAlexW2964014592WikidataQ115246964 ScholiaQ115246964MaRDI QIDQ2818273

Shingyu Leung, Ke Wei, Tony F. Chan, Jian-Feng Cai

Publication date: 7 September 2016

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

algorithmgradient descent methodRiemannian optimizationmatrix recoveryrestricted isometry constantlow rank matrixconjugate gradient descent methodlow rank matrix manifold

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Vector spaces, linear dependence, rank, lineability (15A03) Methods of local Riemannian geometry (53B21) Matrix completion problems (15A83)

Related Items

Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery, Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization, Guarantees of Riemannian optimization for low rank matrix completion, GNMR: A Provable One-Line Algorithm for Low Rank Matrix Recovery, Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution, Fast gradient method for low-rank matrix estimation, Matrix completion with sparse measurement errors, Riemannian thresholding methods for row-sparse and low-rank matrix recovery, Affine matrix rank minimization problem via non-convex fraction function penalty, Provable sample-efficient sparse phase retrieval initialized by truncated power method, Two relaxation methods for rank minimization problems, Nonnegative Low Rank Matrix Completion by Riemannian Optimalization Methods, Gradient projection method on matrix manifolds, Painless breakups -- efficient demixing of low rank matrices, A Geometric Approach to Dynamical Model Order Reduction, Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization, A brief introduction to manifold optimization, Median-Truncated Gradient Descent: A Robust and Scalable Nonconvex Approach for Signal Estimation, Geometric Methods on Low-Rank Matrix and Tensor Manifolds, Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion, Fast rank-one alternating minimization algorithm for phase retrieval, Unnamed Item, A geometric analysis of phase retrieval, Spectral Compressed Sensing via Projected Gradient Descent, Fast Cadzow's algorithm and a gradient variant, Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data, Guarantees of Riemannian Optimization for Low Rank Matrix Recovery, $$L^p$$ Continuity and Microlocal Properties for Pseudodifferential Operators, Accelerated Alternating Projections for Robust Principal Component Analysis, Riemannian optimization for phase retrieval from masked Fourier measurements, A Riemannian rank-adaptive method for low-rank matrix completion, Blind Deconvolution by a Steepest Descent Algorithm on a Quotient Manifold, Matrix completion via minimizing an approximate rank, Existence of dynamical low-rank approximations to parabolic problems, Unnamed Item, Rank $2r$ Iterative Least Squares: Efficient Recovery of Ill-Conditioned Low Rank Matrices from Few Entries, A Three-Operator Splitting Algorithm for Nonconvex Sparsity Regularization, Riemannian conjugate gradient descent method for fixed multi rank third-order tensor completion, Unnamed Item, Hierarchical compressed sensing

Uses Software

• LMaFit
• ADMiRA
• PhaseLift
• Wirtinger Flow

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convergence of fixed-point continuation algorithms for matrix rank minimization
• Null space conditions and thresholds for rank minimization
• Iterative hard thresholding for compressed sensing
• Low rank matrix completion by alternating steepest descent methods
• The restricted isometry property and its implications for compressed sensing
• Convex multi-task feature learning
• Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
• Matrix recipes for hard thresholding methods
• Fixed-rank matrix factorizations and Riemannian low-rank optimization
• The local convexity of solving systems of quadratic equations
• Exact matrix completion via convex optimization
• Riemannian Preconditioning
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• Robust Low-Rank Matrix Completion by Riemannian Optimization
• Low-Rank Matrix Completion by Riemannian Optimization
• Normalized Iterative Hard Thresholding for Matrix Completion
• Guaranteed Matrix Completion via Non-Convex Factorization
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Blind Deconvolution Using Convex Programming
• A Singular Value Thresholding Algorithm for Matrix Completion
• Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Decoding by Linear Programming
• Interior-Point Method for Nuclear Norm Approximation with Application to System Identification
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Conjugate Gradient Iterative Hard Thresholding: Observed Noise Stability for Compressed Sensing
• CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
• Stable low-rank matrix recovery via null space properties
• Living on the edge: phase transitions in convex programs with random data
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• Matrix Completion From a Few Entries
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• A Simpler Approach to Matrix Completion
• Low-rank matrix completion using alternating minimization
• Phase Retrieval via Matrix Completion
• Compressed sensing