Sparse blind deconvolution and demixing through ℓ 1,2-minimization | Advances in Computational Mathematics Skip to main content
Springer Nature Link
Log in

Sparse blind deconvolution and demixing through ℓ 1,2-minimization

  • Published:
Advances in Computational Mathematics Aims and scope Submit manuscript

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.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahmed, A., Recht, B., Romberg, J.: Blind deconvolution using convex programming. IEEE Trans. Inf. Theory 60(3), 1711–1732 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  2. 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)

  3. Candès, E., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51, 4203–4215 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  4. Eldar, Y., Mishali, M.: Robust recovery of signals from a structured union of subspaces. IEEE Trans. Inf Theory 55(11), 5302–5316 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressed Sensing. Birkhäuser (2013)

  6. Gross, D.: Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inf. Theory 57(3), 1548–1566 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  7. Kech, M., Krahmer, F.: Optimal injectivity conditions for bilinear inverse problems with applications to identifiability of deconvolution problems (2016). arXiv:1603.07316

  8. 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)

  9. Lee, K., Wu, Y., Bresler, Y.: Near optimal compressed sensing of sparse rank-one matrices via sparse power factorization (2013). arXiv:1312.0525

  10. Ling, S., Strohmer, T.: Blind deconvolution meets blind demixing: Algorithms and performance bounds. arXiv:1512.07730 (2015)

  11. Ling, S., Strohmer, T.: Self-calibration and biconvex compressive sensing. Inverse Probl. 31, 115002 (2015)

  12. 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)

    Article  MathSciNet  MATH  Google Scholar 

  13. Stoeger, D., Jung, P., Krahmer, F.: Blind deconvolution and compressed sensing. In Cosera, 2016 (2016)

  14. 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)

    Article  MathSciNet  Google Scholar 

  15. Tropp, J. A.: User-friendly tail bounds for sums of random matrices. Found. Comp. Math. 12(4), 389–434 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  16. Vershinyn, R.: Introduction to the non-asymptotic analysis of random matrices. In: Compressed Sensing, Theory and Applications, chapter 5. Cambridge University Press (2012)

Download references

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

  1. Techische Universität Berlin, Sekretariat MA 5-4, Straße des 17 Juni 136, 10623, Berlin, Germany

    Axel Flinth

Authors
  1. Axel Flinth
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Axel Flinth.

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10444-017-9533-0

Keywords

Mathematics Subject Classification (2010)

Search

Navigation