For multichannel sparse blind deconvolution, Huber-loss Riemannian gradient descent with random initialization plus an LP-rounding step provably recovers the kernel and sparse signals up to a signed shift, with sample complexity O~(n^4).
Subgradient Descent Learns Orthogonal Dictionaries
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
This paper concerns dictionary learning, i.e., sparse coding, a fundamental representation learning problem. We show that a subgradient descent algorithm, with random initialization, can provably recover orthogonal dictionaries on a natural nonsmooth, nonconvex $\ell_1$ minimization formulation of the problem, under mild statistical assumptions on the data. This is in contrast to previous provable methods that require either expensive computation or delicate initialization schemes. Our analysis develops several tools for characterizing landscapes of nonsmooth functions, which might be of independent interest for provable training of deep networks with nonsmooth activations (e.g., ReLU), among numerous other applications. Preliminary experiments corroborate our analysis and show that our algorithm works well empirically in recovering orthogonal dictionaries.
fields
eess.SP 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
A Nonconvex Approach for Exact and Efficient Multichannel Sparse Blind Deconvolution
For multichannel sparse blind deconvolution, Huber-loss Riemannian gradient descent with random initialization plus an LP-rounding step provably recovers the kernel and sparse signals up to a signed shift, with sample complexity O~(n^4).