Papers โบ Complete Dictionary Recovery over the Sphere
Complete Dictionary Recovery over the Sphere
Ju Sun, Qing Qu, John Wright
We consider the problem of recovering a complete (i.e., square and invertible) matrix ๐โ, from ๐ โโ^(n รp) with ๐ = ๐โ ๐โ, provided ๐โ 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 ๐โ when ๐โ has O(n) nonzeros per column, under suitable probability model for ๐โ. In contrast, prior results based on efficient algorithms provide recovery guarantees when ๐โ has only O(n^(1-ฮด)) nonzeros per column for any constant ฮดโ(0, 1). 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. To show this apparently hard problem is tractable, we first provide a geometric characterization of the high-dimensional objective landscape, which shows that with high probability there are no "spurious" local minima. This particular geometric structure allows us to design a Riemannian trust region algorithm over the sphere that provably converges to one local minimizer with an arbitrary initialization, despite the presence of saddle points. The geometric approach we develop here may also shed light on other problems arising from nonconvex recovery of structured signals.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change ยท a person checks every report against the paper or source before anything changes; decisions are listed on /corrections