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 the 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 the first paper (arXiv:1511.03607), we have showed that with high probability our nonconvex formulation has no "spurious" local minimizers and any saddle point present is second-order. In this paper, we take advantage of the particular geometric structure and design a Riemannian trust region algorithm over the sphere that provably converges to a local minimizer with an arbitrary initialization. Such minimizers give excellent approximations to rows of $\mathbf X_0$. The rows are recovered by linear programming rounding and deflation.

本文中，我们提出了一种基于流形优化的Riemann信任域算法来有效恢复具有特定几何结构的矩阵材料，在字典学习，稀疏表征和现代信号处理和机器学习等各种应用中取得了显著的效果，并且解决了稀疏列下矩阵恢复的难题。

球面上完整词典恢复：利用黎曼信赖域方法进行恢复