Papers › Dictionary Learning for the Almost-Linear Sparsity Regime

Dictionary Learning for the Almost-Linear Sparsity Regime

19 Oct 2022arXiv:2210.10855archive 2025-07-28

Alexei Novikov, Stephen White

Dictionary learning, the problem of recovering a sparsely used matrix 𝐃 ∈ℝ^(M ×K) and N s-sparse vectors 𝐱ᵢ ∈ℝᴷ from samples of the form 𝐲ᵢ = 𝐃𝐱ᵢ, is of increasing importance to applications in signal processing and data science. When the dictionary is known, recovery of 𝐱ᵢ is possible even for sparsity linear in dimension M, yet to date, the only algorithms which provably succeed in the linear sparsity regime are Riemannian trust-region methods, which are limited to orthogonal dictionaries, and methods based on the sum-of-squares hierarchy, which requires super-polynomial time in order to obtain an error which decays in M. In this work, we introduce SPORADIC (SPectral ORAcle DICtionary Learning), an efficient spectral method on family of reweighted covariance matrices. We prove that in high enough dimensions, SPORADIC can recover overcomplete (K > M) dictionaries satisfying the well-known restricted isometry property (RIP) even when sparsity is linear in dimension up to logarithmic factors. Moreover, these accuracy guarantees have an ``oracle property" that the support and signs of the unknown sparse vectors 𝐱ᵢ can be recovered exactly with high probability, allowing for arbitrarily close estimation of 𝐃 with enough samples in polynomial time. To the author's knowledge, SPORADIC is the first polynomial-time algorithm which provably enjoys such convergence guarantees for overcomplete RIP matrices in the near-linear sparsity regime.

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