Complete Dictionary Recovery Over the Sphere and Riemannian Trust-Region Method

A nonconvex spherical optimization formulation and second-order *Riemannian Trust-Region (RTR)* algorithm over the unit sphere $\mathbb{S}^{n-1}$ (introduced by Ju Sun, Qing Qu, and John Wright in 2015/2017) for recovering a complete invertible dictionary $A_0\in\mathbb{R}^{n\times n}$ and sparse coefficient matrix $X_0\in\mathbb{R}^{n\times p}$ from $Y = A_0 X_0$ up to scale and permutation when $X_0$ follows an i.i.d. Bernoulli-Gaussian($\theta$) distribution with constant sparsity $\theta\in (0, 1/3)$. Observing that $\mathrm{row}(Y) = \mathrm{row}(X_0)$ so the $n$ rows of $X_0$ are the sparsest vectors in $\mathrm{row}(Y)$, the method sequentially finds directions $q\in\mathbb{S}^{n-1}$ by minimizing the smooth log-cosh sparsity surrogate $f(q; Y) = \frac{1}{p}\sum_{k=1}^p \mu\log\cosh(q^\top y_k / \mu)$ on $\mathbb{S}^{n-1}$ (Equation 1.5). Theorem 2.1 proves that when $p \ge C n^2\log^2 n/(\mu^2\theta)$ (down to $\theta = \Omega(1)$ where $O(n)$ nonzeros per column defeat existing $\ell_1$/SOS dictionary recovery methods), $f(q; X_0)$ has *no spurious local minima* across the entire sphere $\mathbb{S}^{n-1}$: in each of the $2n$ spherical caps $S_{\pm}^{(i)}$ mapped to $B(\sqrt{1 - 1/(4n)})$ via $q(w) = (w, \sqrt{1 - \|w\|^2})$, $g(w) = f(q(w))$ exhibits (1) strong convexity $\nabla^2 g(w) \succeq \frac{c_*\theta}{\mu}I$ in the core $R_1 = \{\|w\| \le \frac{\mu}{4\sqrt{2}}\}$ containing a unique local minimizer $w_*$ within $O(\mu\sqrt{\frac{n\log p}{\theta p}})$ of $e_i$ (Proposition 2.5, Lemma 2.3), (2) strictly positive radial gradient $\frac{w^\top \nabla g(w)}{\|w\|} \ge c_*\theta$ in the annulus $R_2 = \{\frac{\mu}{4\sqrt{2}} \le \|w\| \le \frac{1}{20\sqrt{5}}\}$ (Proposition 2.6), and (3) strictly negative radial curvature $\frac{w^\top \nabla^2 g(w) w}{\|w\|^2} \le -c_*\theta$ in the equatorial collar $R_3 = \{\frac{1}{20\sqrt{5}} \le \|w\| \le \sqrt{\frac{4n-1}{4n}}\}$ (Proposition 2.7), enabling the Riemannian Trust-Region algorithm with exponential-map retraction $R_q(\delta) = q\cos\|\delta\| + \frac{\delta}{\|\delta\|}\sin\|\delta\|$ and linear-programming rounding ($\min_q \|q^\top Y\|_1$ s.t. $\langle r, q\rangle = 1$, Lemma 4.2) to recover all $n$ dictionary atoms.