Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method

Abstract

We consider the problem of recovering a complete (i.e., square and invertible) matrix ${\mathbf{A}}_0$, from $\mathbf{Y}\in {\mathbb{R}}^{n\times p}$ with $\mathbf{Y}={\mathbf{A}}_0{\mathbf{X}}_0$, provided ${\mathbf{X}}_0$ 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 ${\mathbf{A}}_0$ when ${\mathbf{X}}_0$ has $O(n)$ nonzeros per column, under suitable probability model for ${\mathbf{X}}_0$. 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 ${\mathbf{X}}_0$. The rows are then recovered by linear programming rounding and deflation.

The 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 (33)

• 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
• Matrix Completion has No Spurious Local Minimum
• Nonconvex phase synchronization
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• 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
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• 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
• Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
• 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
• 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
• A Non-Convex Blind Calibration Method for Randomised Sensing Strategies
• Nearly-optimal Robust Matrix Completion
• 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
• 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 (51)

• 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
• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation
• Escaping from saddle points on Riemannian manifolds
• Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
• Blind Data Detection in Massive MIMO via ${\ell }_3$-norm Maximization over the Stiefel Manifold
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
• Dictionary Learning with BLOTLESS Update
• Fast, asymptotically efficient, recursive estimation in a Riemannian manifold
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Dual Principal Component Pursuit
• No-go Theorem for Acceleration in the Hyperbolic Plane
• Matrix Completion and Related Problems via Strong Duality
• Efficient Sparse Coding using Hierarchical Riemannian Pursuit
• Analysis of the Optimization Landscapes for Overcomplete Representation Learning
• Identifiability of Complete Dictionary Learning
• Learning Polynomials of Few Relevant Dimensions
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• ADMM for Multiaffine Constrained Optimization
• Short-and-Sparse Deconvolution -- A Geometric Approach
• Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
• First-order methods almost always avoid saddle points: the case of vanishing step-sizes
• Unique Sharp Local Minimum in ${\ell }_1$-minimization Complete Dictionary Learning
• Global and Local Analyses of Nonlinear Low-Rank Matrix Recovery Problems
• Manifold Proximal Point Algorithms for Dual Principal Component Pursuit and Orthogonal Dictionary Learning
• Multichannel Sparse Blind Deconvolution on the Sphere
• On Riemannian Stochastic Approximation Schemes with Fixed Step-Size
• Understanding Notions of Stationarity in Non-Smooth Optimization
• Asymptotic proximal point methods: finding the global minima with linear convergence for a class of multiple minima problems
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
• Learning Semidefinite Regularizers
• Non-Convex Compressed Sensing with Training Data
• Riemannian Stochastic Hybrid Gradient Algorithm for Nonconvex Optimization