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

DOI10.1109/TIT.2016.2632162MaRDI QIDQ2989630zbMATH OpenOpenAlexFDO

Authors

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We consider the problem of recovering a complete (i.e., square and invertible) matrix $mathbf{A}_0$, from $mathbfYinmathbb{R}^{nimesp}$ with $mathbfY=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(sqrtn)$ 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 $deltain(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.

Recommendations

• Complete Dictionary Recovery Over the Sphere II: Recovery by Riemannian Trust-Region Method
• Sparse signal recovery via non-convex optimization and overcomplete dictionaries
• Sparse Image Reconstruction on the Sphere: Implications of a New Sampling Theorem
• Spherical designs and nonconvex minimization for recovery of sparse signals on the sphere
• Sensing Matrix Design and Sparse Recovery on the Sphere and the Rotation Group
• Sparsity-Aware Sphere Decoding: Algorithms and Complexity Analysis
• The dictionary approach for spherical deconvolution
• The Geometry of Compressed Sensing
• Dictionary-sparse recovery from heavy-tailed measurements

Cited in

(67)

• Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018
• Learning semidefinite regularizers
• The global optimization geometry of shallow linear neural networks
• A convex variational model for learning convolutional image atoms from incomplete data
• On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint
• Data clustering based on the modified relaxation Cheeger cut model
• Solving phase retrieval with random initial guess is nearly as good as by spectral initialization
• Optimization landscape of Tucker decomposition
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Sensor calibration for off-the-grid spectral estimation
• Compressed dictionary learning
• Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods
• An envelope for Davis-Yin splitting and strict saddle-point avoidance
• First-order methods almost always avoid strict saddle points
• Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation
• Dual principal component pursuit
• Local identifiability of \(\ell_1\)-minimization dictionary learning: a sufficient and almost necessary condition
• Robust PCA by manifold optimization
• A Newton-based method for nonconvex optimization with fast evasion of saddle points
• Spectral Compressed Sensing via Projected Gradient Descent
• On collaborative compressive sensing systems: the framework, design, and algorithm
• Exact guarantees on the absence of spurious local minima for non-negative rank-1 robust principal component analysis
• Unique sharp local minimum in \(\ell_1\)-minimization complete dictionary learning
• On stationary-point hitting time and ergodicity of stochastic gradient Langevin dynamics
• Matrix completion and related problems via strong duality
• Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods
• One-dimensional system arising in stochastic gradient descent
• Identifiability of complete dictionary learning
• Extending the Step-Size Restriction for Gradient Descent to Avoid Strict Saddle Points
• Analysis of asymptotic escape of strict saddle sets in manifold optimization
• Stochastic proximal gradient method FOR _1 regularized optimization over a sphere
• Global convergence of stochastic gradient Hamiltonian Monte Carlo for nonconvex stochastic optimization: nonasymptotic performance bounds and momentum-based acceleration
• A trust region method for finding second-order stationarity in linearly constrained nonconvex optimization
• Exact Recovery of Multichannel Sparse Blind Deconvolution via Gradient Descent
• Finding a low-rank basis in a matrix subspace
• Proximal gradient method for nonsmooth optimization over the Stiefel manifold
• ADMM for multiaffine constrained optimization
• Non-convex matrix completion and related problems via strong duality
• On the landscape of synchronization networks: a perspective from nonconvex optimization
• Rayleigh quotient minimization for absolutely one-homogeneous functionals
• The global landscape of phase retrieval. I: Perturbed amplitude models
• The global landscape of phase retrieval. II: Quotient intensity models
• An active-set proximal quasi-Newton algorithm for ℓ₁-regularized minimization over a sphere constraint
• Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
• Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model
• Decentralized nonconvex optimization with guaranteed privacy and accuracy
• Adaptive trust-region method on Riemannian manifold
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Learning polynomial transformations via generalized tensor decompositions
• Nonsmooth optimization over the Stiefel manifold and beyond: proximal gradient method and recent variants
• Cardinality minimization, constraints, and regularization: a survey
• A new complexity metric for nonconvex rank-one generalized matrix completion
• Three proofs of the Benedetto-Fickus theorem
• Gradient descent provably escapes saddle points in the training of shallow ReLU networks
• Convergence regions of alternating minimization algorithms for dictionary learning
• Optimal vintage factor analysis with deflation varimax
• Riemannian trust-region methods for strict saddle functions with complexity guarantees
• A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees
• Simple alternating minimization provably solves complete dictionary learning
• Data-driven methods for quantitative imaging
• Generalized orthogonal Procrustes problem under arbitrary adversaries
• Dictionary learning for the almost-linear sparsity regime
• Optimal regularization for a data source
• Local geometry determines global landscape in low-rank factorization for synchronization
• Understanding deep representation learning via layerwise feature compression and discrimination
• Degree-of-freedom and optimization-dynamic effects on the observability of Kuramoto-Sivashinsky systems
• Spectral neural networks: approximation theory and optimization landscape

This page was built for publication: Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989630)