Dictionary Learning for the Almost-Linear Sparsity Regime

Alexei Novikov, Stephen White

Research output: Contribution to journalConference articlepeer-review


Dictionary learning, the problem of recovering a sparsely used matrix D ∈ RM×K and N independent K×1 s-sparse vectors X ∈ RK×N from samples of the form Y = DX, is of increasing importance to applications in signal processing and data science. Early papers on provable dictionary learning identified that one can detect whether two samples yi, yj share a common dictionary element by testing if their inner product (correlation) exceeds a certain threshold: | 〈yi, yj〉 | > τ. These correlation-based methods work well _when sparsity is small, but suffer from declining performance when sparsity grows faster than √M; as a result, such methods were abandoned in the search for dictionary learning algorithms when sparsity is nearly linear in M. In this paper, we revisit correlation-based dictionary learning. Instead of seeking to recover individual dictionary atoms, we employ a spectral method to recover the subspace spanned by the dictionary atoms in the support of each sample. This approach circumvents the primary challenge encountered by previous correlation methods, namely that when sharing information between two samples it is difficult to tell which dictionary element the two samples share. We prove that under a suitable random model the resulting algorithm recovers dictionaries in polynomial time for sparsity linear in M up to log factors. Our results improve on the best known methods by achieving a decaying error bound in dimension M; the best previously known results for the overcomplete (K > M) setting achieve polynomial time in the linear regime only for constant error bounds. Numerical simulations confirm our results.

Original languageEnglish (US)
Pages (from-to)1516-1554
Number of pages39
JournalProceedings of Machine Learning Research
StatePublished - 2023
Event34th International Conference onAlgorithmic Learning Theory, ALT 2023 - Singapore, Singapore
Duration: Feb 20 2023Feb 23 2023

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Cite this