Geometry and Symmetry in Short-and-Sparse Deconvolution

Han-Wen Kuo, Yenson Lau, Yuqian Zhang, John Wright
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3570-3580, 2019.

Abstract

We study the Short-and-Sparse (SaS) deconvolution problem of recovering a short signal a0 and a sparse signal x0 from their convolution. We propose a method based on nonconvex optimization, which under certain conditions recovers the target short and sparse signals, up to a signed shift symmetry which is intrinsic to this model. This symmetry plays a central role in shaping the optimization landscape for deconvolution. We give a regional analysis, which characterizes this landscape geometrically, on a union of subspaces. Our geometric characterization holds when the length-p0 short signal a0 has shift coherence {\textmu}, and x0 follows a random sparsity model with sparsity rate $\theta$ $\in$ [c1/p0, c2/(p0\sqrt{\mu}+\sqrt{p0})] / (log^2(p0)) . Based on this geometry, we give a provable method that successfully solves SaS deconvolution with high probability.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-kuo19a, title = {Geometry and Symmetry in Short-and-Sparse Deconvolution}, author = {Kuo, Han-Wen and Lau, Yenson and Zhang, Yuqian and Wright, John}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {3570--3580}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/kuo19a/kuo19a.pdf}, url = {https://proceedings.mlr.press/v97/kuo19a.html}, abstract = {We study the Short-and-Sparse (SaS) deconvolution problem of recovering a short signal a0 and a sparse signal x0 from their convolution. We propose a method based on nonconvex optimization, which under certain conditions recovers the target short and sparse signals, up to a signed shift symmetry which is intrinsic to this model. This symmetry plays a central role in shaping the optimization landscape for deconvolution. We give a regional analysis, which characterizes this landscape geometrically, on a union of subspaces. Our geometric characterization holds when the length-p0 short signal a0 has shift coherence {\textmu}, and x0 follows a random sparsity model with sparsity rate $\theta$ $\in$ [c1/p0, c2/(p0\sqrt{\mu}+\sqrt{p0})] / (log^2(p0)) . Based on this geometry, we give a provable method that successfully solves SaS deconvolution with high probability.} }
Endnote
%0 Conference Paper %T Geometry and Symmetry in Short-and-Sparse Deconvolution %A Han-Wen Kuo %A Yenson Lau %A Yuqian Zhang %A John Wright %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-kuo19a %I PMLR %P 3570--3580 %U https://proceedings.mlr.press/v97/kuo19a.html %V 97 %X We study the Short-and-Sparse (SaS) deconvolution problem of recovering a short signal a0 and a sparse signal x0 from their convolution. We propose a method based on nonconvex optimization, which under certain conditions recovers the target short and sparse signals, up to a signed shift symmetry which is intrinsic to this model. This symmetry plays a central role in shaping the optimization landscape for deconvolution. We give a regional analysis, which characterizes this landscape geometrically, on a union of subspaces. Our geometric characterization holds when the length-p0 short signal a0 has shift coherence {\textmu}, and x0 follows a random sparsity model with sparsity rate $\theta$ $\in$ [c1/p0, c2/(p0\sqrt{\mu}+\sqrt{p0})] / (log^2(p0)) . Based on this geometry, we give a provable method that successfully solves SaS deconvolution with high probability.
APA
Kuo, H., Lau, Y., Zhang, Y. & Wright, J.. (2019). Geometry and Symmetry in Short-and-Sparse Deconvolution. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:3570-3580 Available from https://proceedings.mlr.press/v97/kuo19a.html.

Related Material