Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
arXiv:1511.04777 · doi:10.1109/TIT.2016.2632149
Abstract
We consider the problem of recovering a complete (i.e., square and invertible) matrix , from with , provided is sufficiently sparse. This recovery problem is central to theoretical understanding of dictionary learning, which seeks a sparse representation for a collection of input signals and finds numerous applications in modern signal processing and machine learning. We give the first efficient algorithm that provably recovers when has nonzeros per column, under suitable probability model for . Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint, and hence is naturally phrased in the language of manifold optimization. In a companion paper (arXiv:1511.03607), we have showed that with high probability our nonconvex formulation has no "spurious" local minimizers and around any saddle point the objective function has a negative directional curvature. In this paper, we take advantage of the particular geometric structure, and describe a Riemannian trust region algorithm that provably converges to a local minimizer with from arbitrary initializations. Such minimizers give excellent approximations to rows of . The rows are then recovered by linear programming rounding and deflation.
arXiv commentThe second of two papers based on the report arXiv:1504.06785. Accepted by IEEE Transaction on Information Theory; revised according to the reviewers' comments
References in corpus (46)
- Phase Retrieval via Wirtinger Flow: Theory and Algorithms
- Manopt, a Matlab toolbox for optimization on manifolds
- User-friendly tail bounds for sums of random matrices
- Guaranteed Matrix Completion via Non-convex Factorization
- Global rates of convergence for nonconvex optimization on manifolds
- Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
- Global Optimality of Local Search for Low Rank Matrix Recovery
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Matrix Completion has No Spurious Local Minimum
- Nonconvex phase synchronization
- No bad local minima: Data independent training error guarantees for multilayer neural networks
- Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
- Fast Algorithms for Robust PCA via Gradient Descent
- Provable Tensor Factorization with Missing Data
- Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
- Non-convex Robust PCA
- When Are Nonconvex Problems Not Scary?
- Exact Recovery of Sparsely-Used Dictionaries
- Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank- Updates
- On the low-rank approach for semidefinite programs arising in synchronization and community detection
- Alternating Minimization for Mixed Linear Regression
- Phaseless Rcovery using Gauss-Newton Method
- Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
- Fast matrix completion without the condition number
- Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
- A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
- Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
- Dropping Convexity for Faster Semi-definite Optimization
- Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
- The non-convex Burer-Monteiro approach works on smooth semidefinite programs
- Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
- Phase Retrieval via Incremental Truncated Wirtinger Flow
- The local convexity of solving systems of quadratic equations
- Guarantees of Riemannian Optimization for Low Rank Matrix Completion
- Deep Learning without Poor Local Minima
- Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems
- Nearly-optimal Robust Matrix Completion
- A Non-Convex Blind Calibration Method for Randomised Sensing Strategies
- A Note on Alternating Minimization Algorithm for the Matrix Completion Problem
- RIP-like Properties in Subsampled Blind Deconvolution
- Recovery guarantee of weighted low-rank approximation via alternating minimization
- Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
- Provable Tensor Methods for Learning Mixtures of Generalized Linear Models
- Fast Exact Matrix Completion with Finite Samples
- A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries
- Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Cited by in corpus (52)
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Global rates of convergence for nonconvex optimization on manifolds
- Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
- Global Optimality in Low-rank Matrix Optimization
- Gradient Descent Converges to Minimizers
- Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
- The Non-convex Geometry of Low-rank Matrix Optimization
- Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
- A Geometric Analysis of Neural Collapse with Unconstrained Features
- Averaging Stochastic Gradient Descent on Riemannian Manifolds
- Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
- First-order Methods for Geodesically Convex Optimization
- The Global Optimization Geometry of Low-Rank Matrix Optimization
- From Symmetry to Geometry: Tractable Nonconvex Problems
- R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
- The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
- Precoder Design for Massive MIMO Downlink with Matrix Manifold Optimization
- Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
- Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
- Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
- Escaping from saddle points on Riemannian manifolds
- Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation
- Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
- Blind Data Detection in Massive MIMO via -norm Maximization over the Stiefel Manifold
- A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
- Fast, asymptotically efficient, recursive estimation in a Riemannian manifold
- Dictionary Learning with BLOTLESS Update
- Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
- No-go Theorem for Acceleration in the Hyperbolic Plane
- Matrix Completion and Related Problems via Strong Duality
- Dual Principal Component Pursuit
- Analysis of the Optimization Landscapes for Overcomplete Representation Learning
- Efficient Sparse Coding using Hierarchical Riemannian Pursuit
- Identifiability of Complete Dictionary Learning
- First-order methods almost always avoid saddle points: the case of vanishing step-sizes
- Short-and-Sparse Deconvolution -- A Geometric Approach
- Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
- ADMM for Multiaffine Constrained Optimization
- Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
- Learning Polynomials of Few Relevant Dimensions
- Unique Sharp Local Minimum in -minimization Complete Dictionary Learning
- Asymptotic proximal point methods: finding the global minima with linear convergence for a class of multiple minima problems
- Manifold Proximal Point Algorithms for Dual Principal Component Pursuit and Orthogonal Dictionary Learning
- Global and Local Analyses of Nonlinear Low-Rank Matrix Recovery Problems
- Multichannel Sparse Blind Deconvolution on the Sphere
- Finding a low-rank basis in a matrix subspace
- On Riemannian Stochastic Approximation Schemes with Fixed Step-Size
- Understanding Notions of Stationarity in Non-Smooth Optimization
- On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
- Learning Semidefinite Regularizers
- Riemannian Stochastic Hybrid Gradient Algorithm for Nonconvex Optimization
- Non-Convex Compressed Sensing with Training Data