Abstract
This paper concerns solving the sparse deconvolution and demixing problem using ℓ 1,2-minimization. We show that under a certain structured random model, robust and stable recovery is possible. The results extend results of Ling and Strohmer (Inverse Probl. 31, 115002 2015), and in particular theoretically explain certain experimental findings from that paper. Our results do not only apply to the deconvolution and demixing problem, but to recovery of column-sparse matrices in general.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahmed, A., Recht, B., Romberg, J.: Blind deconvolution using convex programming. IEEE Trans. Inf. Theory 60(3), 1711–1732 (2014)
Asi, M. S., Mantzel, W., Romberg, J.: Channel protection: Random coding meets sparse channels IEEE Information Theory Workshop, vol. 2009, pp 348–352, Taormina (2009)
Candès, E., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51, 4203–4215 (2005)
Eldar, Y., Mishali, M.: Robust recovery of signals from a structured union of subspaces. IEEE Trans. Inf Theory 55(11), 5302–5316 (2009)
Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressed Sensing. Birkhäuser (2013)
Gross, D.: Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inf. Theory 57(3), 1548–1566 (2011)
Kech, M., Krahmer, F.: Optimal injectivity conditions for bilinear inverse problems with applications to identifiability of deconvolution problems (2016). arXiv:1603.07316
Koltchinskii, V.: A remark on low rank matrix recovery and noncommutative Bernstein type inequalities From robability to statistics and back: High-dimensional models and processes – a festschrift in honor of Jon A. Wellner, pp 213–226. Institute of Mathematical Statistics (2013)
Lee, K., Wu, Y., Bresler, Y.: Near optimal compressed sensing of sparse rank-one matrices via sparse power factorization (2013). arXiv:1312.0525
Ling, S., Strohmer, T.: Blind deconvolution meets blind demixing: Algorithms and performance bounds. arXiv:1512.07730 (2015)
Ling, S., Strohmer, T.: Self-calibration and biconvex compressive sensing. Inverse Probl. 31, 115002 (2015)
Recht, B., Fazel, M., Parrilo, P. A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471–501 (2010)
Stoeger, D., Jung, P., Krahmer, F.: Blind deconvolution and compressed sensing. In Cosera, 2016 (2016)
Stojnic, M., Parvaresh, F., Hassibi, B.: On the reconstruction of block-sparse signals with an optimal number of measurements. IEEE Trans. Signal Process. 57 (8), 3075–3085 (2009)
Tropp, J. A.: User-friendly tail bounds for sums of random matrices. Found. Comp. Math. 12(4), 389–434 (2012)
Vershinyn, R.: Introduction to the non-asymptotic analysis of random matrices. In: Compressed Sensing, Theory and Applications, chapter 5. Cambridge University Press (2012)
Acknowledgments
The author acknowledges support from Deutsche Forschungsgemeinschaft (DFG) Grant KU 1446/18 - 1 and the Berlin Mathematical School. He thanks Felix Krahmer and Dominik Stöger for pointing out weak spots in the first version of the article, as well as providing references making it possible to repair them – and even enhance the results slightly in the process. He also wishes to thank Gitta Kutyniok for fruitful discussions.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interests
The author declares that he has no conflict of interest.
Funding
This Research was funded by the Deutsche Forschungsgemeinschaft (DFG) Grant KU 1446/18-1.
Additional information
Communicated by: Gitta Kutyniok
Rights and permissions
About this article
Cite this article
Flinth, A. Sparse blind deconvolution and demixing through ℓ 1,2-minimization. Adv Comput Math 44, 1–21 (2018). https://doi.org/10.1007/s10444-017-9533-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10444-017-9533-0