Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture

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$. In contrast, prior results based on efficient algorithms either only guarantee recovery when ${\mathbf{X}}_0$ has $O(\sqrt{n})$ zeros per column, or require multiple rounds of SDP relaxation to work when ${\mathbf{X}}_0$ has $O(n^{1-\delta })$ nonzeros per column (for any constant $\delta \in (0,1)$). } Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint. In this paper, we provide a geometric characterization of the objective landscape. In particular, we show that the problem is highly structured: with high probability, (1) there are no "spurious" local minimizers; and (2) around all saddle points the objective has a negative directional curvature. This distinctive structure makes the problem amenable to efficient optimization algorithms. In a companion paper (arXiv:1511.04777), we design a second-order trust-region algorithm over the sphere that provably converges to a local minimizer from arbitrary initializations, despite the presence of saddle points.

Accepted by IEEE Transaction on Information Theory; revised according to the reviewers' comments

References in corpus (34)

• Guaranteed Matrix Completion via Non-convex Factorization
• 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
• Provable Tensor Factorization with Missing Data
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• 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
• Simple, Efficient, and Neural Algorithms for Sparse Coding
• On the Computational Efficiency of Training Neural Networks
• Fast matrix completion without the condition number
• 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
• Statistical guarantees for the EM algorithm: From population to sample-based analysis
• The non-convex Burer-Monteiro approach works on smooth semidefinite programs
• High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• The local convexity of solving systems of quadratic equations
• Deep Learning without Poor Local Minima
• Provable Tensor Methods for Learning Mixtures of Generalized Linear Models
• Fast Exact Matrix Completion with Finite Samples
• Tight Hardness of the Non-commutative Grothendieck Problem
• Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
• Identifiability and Stability in Blind Deconvolution under Minimal Assumptions
• Provable Sparse Tensor Decomposition
• Support recovery without incoherence: A case for nonconvex regularization
• Statistical consistency and asymptotic normality for high-dimensional robust M-estimators
• Local identifiability of $l_1$-minimization dictionary learning: a sufficient and almost necessary condition

Cited by in corpus (96)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• How to Escape Saddle Points Efficiently
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Adaptive Interference Removal for Un-coordinated Radar/Communication Co-existence
• Global Optimality in Low-rank Matrix Optimization
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Gradient Descent Converges to Minimizers
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• An Analysis of the t-SNE Algorithm for Data Visualization
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Stochastic Cubic Regularization for Fast Nonconvex Optimization
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• Nonconvex Demixing From Bilinear Measurements
• Efficiently escaping saddle points on manifolds
• Computing Large-Scale Matrix and Tensor Decomposition with Structured Factors: A Unified Nonconvex Optimization Perspective
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Robust PCA by Manifold Optimization
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• A convex variational model for learning convolutional image atoms from incomplete data
• Time Series Forecasting via Learning Convolutionally Low-Rank Models
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• Optimization Landscape of Tucker Decomposition
• Blind Data Detection in Massive MIMO via ${\ell }_3$-norm Maximization over the Stiefel Manifold
• An Unconstrained Layer-Peeled Perspective on Neural Collapse
• Dictionary Learning with BLOTLESS Update
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Complete Dictionary Learning via ${\ell }_p$-norm Maximization
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
• Regularized Gradient Descent: A Nonconvex Recipe for Fast Joint Blind Deconvolution and Demixing
• An Alternating Manifold Proximal Gradient Method for Sparse PCA and Sparse CCA
• On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation
• Matrix Completion and Related Problems via Strong Duality
• Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold
• Dual Principal Component Pursuit
• Unique sparse decomposition of low rank matrices
• Efficient Sparse Coding using Hierarchical Riemannian Pursuit
• Analysis of the Optimization Landscapes for Overcomplete Representation Learning
• Sensor Calibration for Off-the-Grid Spectral Estimation
• Identifiability of Complete Dictionary Learning
• Short-and-Sparse Deconvolution -- A Geometric Approach
• Riemannian Perspective on Matrix Factorization
• Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
• The Global Optimization Geometry of Shallow Linear Neural Networks
• First-order methods almost always avoid saddle points: the case of vanishing step-sizes
• ADMM for Multiaffine Constrained Optimization
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• Provable Representation Learning for Imitation Learning via Bi-level Optimization
• A Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysis
• Spectral Compressed Sensing via Projected Gradient Descent
• Alternating minimization for dictionary learning: Local Convergence Guarantees
• Escaping spurious local minimum trajectories in online time-varying nonconvex optimization
• Unique Sharp Local Minimum in ${\ell }_1$-minimization Complete Dictionary Learning
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization
• Gradient descent provably escapes saddle points in the training of shallow ReLU networks
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• Finding a low-rank basis in a matrix subspace
• Heavy-ball Algorithms Always Escape Saddle Points
• Multi-target Position and Velocity Estimation Using OFDM Communication Signals
• Understanding Notions of Stationarity in Non-Smooth Optimization
• A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees
• Convex Sparse Blind Deconvolution
• Three proofs of the Benedetto-Fickus theorem
• Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization
• The loss landscape of deep linear neural networks: a second-order analysis
• Manifold Proximal Point Algorithms for Dual Principal Component Pursuit and Orthogonal Dictionary Learning
• 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
• Multichannel Sparse Blind Deconvolution on the Sphere
• A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• On Collaborative Compressive Sensing Systems: The Framework, Design and Algorithm
• Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries
• Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models: Extension
• Blind Signal Detection in Massive MIMO: Exploiting the Channel Sparsity
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• A Comprehensive Study on Optimization Strategies for Gradient Descent In Deep Learning
• Learning Semidefinite Regularizers
• Non-Convex Compressed Sensing with Training Data
• Conditions for Exact Convex Relaxation and No Spurious Local Optima
• Escaping Saddle Points for Zeroth-order Nonconvex Optimization using Estimated Gradient Descent
• One-dimensional System Arising in Stochastic Gradient Descent
• Double-Sparsity Learning Based Channel-and-Signal Estimation in Massive MIMO with Generalized Spatial Modulation
• Dictionary Learning and Sparse Coding on Statistical Manifolds
• An Envelope for Davis-Yin Splitting and Strict Saddle Point Avoidance
• Stochastic Approximation for Online Tensorial Independent Component Analysis
• Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience
• Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications
• Opinion Dynamics with Varying Susceptibility to Persuasion via Non-Convex Local Search