Complete Dictionary Recovery Over the Sphere II: Recovery by Riemannian Trust-Region Method

DOI10.1109/TIT.2016.2632149MaRDI QIDQ2989631zbMATH OpenOpenAlexWikidataFDO

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.04777

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$. 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.

Cited in

(37)

• Learning semidefinite regularizers
• A geometric analysis of phase retrieval
• On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint
• Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
• Nonconvex weak sharp minima on Riemannian manifolds
• 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
• The local convexity of solving systems of quadratic equations
• First-order methods almost always avoid strict saddle points
• Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
• Dual principal component pursuit
• Gradient descent only converges to minimizers: non-isolated critical points and invariant regions
• Unique sharp local minimum in \(\ell_1\)-minimization complete dictionary learning
• Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods
• Identifiability of complete dictionary learning
• Extending the Step-Size Restriction for Gradient Descent to Avoid Strict Saddle Points
• Geometry and symmetry in short-and-sparse deconvolution
• Stochastic proximal gradient method FOR _1 regularized optimization over a sphere
• Tracking and Regret Bounds for Online Zeroth-Order Euclidean and Riemannian Optimization
• A trust region method for finding second-order stationarity in linearly constrained nonconvex optimization
• Exact Recovery of Multichannel Sparse Blind Deconvolution via Gradient Descent
• Complete dictionary learning via ^4-norm maximization over the orthogonal group
• Finding a low-rank basis in a matrix subspace
• ADMM for multiaffine constrained optimization
• Non-convex matrix completion and related problems via strong duality
• An active-set proximal quasi-Newton algorithm for ℓ₁-regularized minimization over a sphere constraint
• Riemannian optimization via Frank-Wolfe methods
• Riemannian gradient methods for stochastic composition problems
• Cardinality minimization, constraints, and regularization: a survey
• Convergence regions of alternating minimization algorithms for dictionary learning
• Riemannian trust-region methods for strict saddle functions with complexity guarantees
• Riemannian bilevel optimization
• Data-driven methods for quantitative imaging
• Optimal spectral recovery of a planted vector in a subspace
• Dictionary learning for the almost-linear sparsity regime
• Global Riemannian acceleration in hyperbolic and spherical spaces
• Optimal regularization for a data source

This page was built for publication: Complete Dictionary Recovery Over the Sphere II: Recovery by Riemannian Trust-Region Method

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