Bilinear Compressed Sensing

Bilineares Compressed Sensing

Zusammenfassung

Die Theorie des Compressed Sensing (CS) hat gezeigt, dass eine substantielle Aufwandsreduktionen in vielen linearen Abtastproblemen und relevanten Schätzaufgaben erzielt werden kann. Jüngste theoretische Entwicklungen deuten nun darauf hin, dass eine ganze Reihe praktischer nicht-linearer Probleme ebenfalls in diesem Kontext gelöst werden könnten. Beispiele dafür sind das blinde Dekodieren von Mobilfunksignalen unter Kanalunsicherheiten, die Rekonstruktion von Bildern aus ungenauen Aufnahmen ohne genaue Kenntnis der Verzerrung oder allgemeinere Modellunsicherheiten in der herkömmlichen CS-Theorie. Die gemeinsame Charakteristik dieserProblemstellungen ist, dass das zugrunde liegende Signal nur durch ein unkalibriertes System zugänglich ist, dessen genaue Eigenschaften zum Zeitpunkt der Messung nur teilweise bekannt sind. Mathematisch gesehen ist die Parametermenge, die diese Eigenschaften beschreibt, mit dem Signal multiplikativ gekoppelt - es ergibt sich also eine bilineare Struktur. Während in herkömmlichem CS solche Modellungenauigkeiten unvermeidbare Qualitätsverluste bei der Rekonstruktion zur Folge haben, besteht der neue Ansatz darin, gleichzeitig Signal und Modellparameter abzuschätzen.

Die Theorie des bilinearen Compressed Sensing ist erst an ihren Anfängen, hat aber in letzter Zeit ein beträchtliches Maß an Aufmerksamkeit auf sich gezogen und macht rasante Fortschritte. (Da sie die ersten beiden im CS untersuchten Modellannahmen - Dünnbesetztheit und niedrigen Rang - zusammenführt und verallgemeinert, wurde dieses Forschungsfeld mit dem Schlagwort Compressed Sensing 3.0 assoziiert.) In diesem Kontext können unserer Ansicht nach einige Probleme aus den Anwendungen in naher Zukunft erfolgreich angegangen werden - es sind aber andererseits auch noch viele grundlegende mathematische Fragestellungen ungeklärt. Wir haben uns daher in einem Team von drei Forschern verschiedener Fachrichtungen zusammengetan, weil wir glauben, dass wir nur in einer interdisziplinären Kooperation in der Lage sein werden, die erforderliche Expertise zu theoretischen und praktischen Aspekten zu vereinen. Gemeinsam wollen wir mit der Beantwortung essentieller Fragestellungen zur Entwicklung einer allgemeinen Theorie des bilinearen Compressed Sensing beitragen. Einerseits werden wir in einem abstrakten Zusammenhang die Rekonstruktionseigenschaften aus zufälligen bilinearen Abtastwerten sowie bilineare Abbildungen von Vektoren unter zufälligen Unterraumannahmen untersuchen. Andererseits werden wir uns mit auf spezifische Anwendungen zugeschnittenen Szenarien beschäftigen, hauptsächtlich im Mobilfunk, aber auch in der Bildverarbeitung und Spektroskopie.

Summary

The theory of compressed sensing (CS) has shown that a substantial reduction in sampling and storage complexity can be achieved in many relevant linear and non--adaptive estimation problems. Recent theoretical developments have also put the analysis of a whole range of practical non-linear problems within reach. Examples include blind decoding of wireless signals under channel uncertainties, recovery of images from fuzzy snapshots without precise knowledge of the blurring kernel, or more general model uncertainties in conventional CS. The unifying feature of these tasks is that the signal is accessible only through an uncalibrated system, whose description is partially unknown at the time of measurement. Mathematically, one set of parameters (the channel, the kernel, the sensing matrix) is coupled in a multiplicative way to the signal -- giving rise to an inherent bilinear structure. While in conventional CS such model uncertainties inevitably degrade the quality of the recovery, the novel approach is to combine bilinearity and compressibility in order to simultaneously estimate both the signal and the model parameters.

The theory of bilinear CS is only at its beginnings, but has recently garnered a significant amount of attention and is developing rapidly. (Because it unites and extends the first two structural assumptions considered in the CS community -- sparsity and low-rank -- it is sometimes refered to as compressed sensing 3.0). While we believe that engineering applications are within reach over the duration of the Priority Program, considerable mathematical problems remain to be addressed. We have therefore chosen a team of three principal investigators who contribute the necessary diverse set of theoretical and practical expertise. Together, we will work towards a comprehensive theory for bilinear CS. On the one hand, we will study, in an abstract context, recovery properties for random subsampling of bilinear maps, as well as bilinear maps of vectors under random subspace conditions. On the other hand, we will work to develop adapted techniques for specific applications, focusing on wireless communication, but also touching on imaging and spectroscopy.

Preprints

  1. Kueng, R. and Jung, P., Robust Nonnegative Sparse Recovery and the Nullspace Property of 0/1 Measurements, March 2016

  2. Walk, P., Jung, P., Pfander, G. E., and Hassibi, B. Blind Deconvolution with Additional Autocorrelations via Convex Programs, January 2017

  3. Genzel, M. and Jung, P. Recovering Structured Data From Superimposed Non-Linear Measurements, August 2017

  4. Lee, K., Krahmer, F., and Romberg, J. Spectral methods for passive imaging: Non-asymptotic performance and robustness, August 2017

  5. Chang, Y., Jung, P., Zhou, C., and Stanczak, S., Block Compressed Sensing Based Distributed Device Detection for M2M Communications, September 2017

  6. Augustin, S., Frohmann, S., Jung, P., Huebers, H.-W. Mask Responses for Single-Pixel Terahertz Imaging, October 2017

  7. Željka Stojanac, Daniel Suess, Martin Kliesch, On products of Gaussian random variables, November 2017

Publications

  1. Augustin, S., Hieronymus, J., Jung, P., and Hübers, W. H. Compressed Sensing in a Fully Non-Mechanical 350 GHz Imaging Setting, Journal of Infrared, Millimeter, and Terahertz Waves, 36(5):496--512. (May 2015) doi 10.1007/s10762-014-0141-5

  2. Stoeger, D. and Jung, P. and Krahmer, F., Blind deconvolution and Compressed Sensing, In 4th International Workshop on Compressed Sensing Theory and its Applications to Radar, Sonar and Remote Sensing (CoSeRa), pages 24--27. IEEE. 9-22 September 2016, Aachen, Germany.

  3. Kueng, R. and P., Jung., Robust Nonnegative Sparse Recovery and 0/1-Bernoulli Measurements, IEEE Inf. Theory Workshop (ITW), Cambridge, 12-14 September 2016

  4. Walk, P., Jung, P., Pfander, G. E., and Hassibi, B. Ambiguities of Convolutions with Application to Phase Retrieval Problems, In 2016 50th Asilomar Conference on Signals, Systems and Computers (invited paper). 6-9 Nov. 2016, Pacific Grove, CA, USA

  5. Kech, M. and Krahmer, F. Optimal injectivity conditions for bilinear inverse problems with applications to identifiability of deconvolution problems, SIAM J. Appl. Algebra Geom., 1(1):20--37. (Feb. 2017)

  6. Kueng, R. and Jung, P. Convex signal reconstruction with positivity constraints, In BASP Frontiers, 29. January-3. February, 2017 - Villars-sur-Ollon, Switzerland

  7. Walk, P., Jung, P., and Hassibi, B. Blind Signal Transmission Using Huffman Sequences, 2017 Information Theory and Applications Workshop, 12.-17. Februar 2017, San Diego, Unites States

  8. Jung, P., Walk, P., and Pfander, G. Blind Deconvolution and Polynomial Factorization, In BASP Frontiers, 29. January-3. February, 2017 - Villars-sur-Ollon, Switzerland

  9. Stoeger, D., Jung, P., and Krahmer, F. Blind Demixing and Deconvolution with Noisy Data: Near-optimal Rate, In 21st International ITG Workshop on Smart Antenna (WSA), VDE, 15-17 March 2017, Berlin, Germany

  10. Genzel, M. and Jung, P. Sparse Recovery From Superimposed Non-Linear Sensor Measurements, In SPARS17, 5-8 June 2017, Lisbon, Portugal

  11. Lee, K., Krahmer, F., and Romberg, J. An eigen approach to stable multichannel blind deconvolution under an fir subspace model, In Sampling Theory and Applications, 12th International Conference (SampTA), pages 386--390. IEEE. 3-7 July 2017, Tallin, Estonia

  12. Geppert, J. A., Krahmer, F., and Stöger, D., Refined performance guarantees for sparse power factorization, In Sampling Theory and Applications, 12th International Conference (SampTA), pages 509--513. IEEE. 3-7 July 2017, Tallin, Estonia

  13. Walk, P., Jung, P., and Hassibi. Constrained Blind Deconvolution using Wirtinger Flow Methods, In Sampling Theory and Applications, 12th International Conference (SampTA), 3-7 July 2017, Tallin, Estonia

  14. Genzel, M. and Jung, P. Blind Sparse Recovery From Superimposed Non-Linear Sensor Measurements, In Sampling Theory and Applications, 12th International Conference (SampTA). 3-7 July 2017, Tallin, Estonia

  15. Stoeger, D., Jung, P., and Krahmer, F. Blind demixing and deconvolution with noisy data at near optimal rate, In Proc. SPIE 10394, Wavelets and Sparsity XVII, 103941E, 24 August 2017, San Diego, California, United States

  16. Augustin, S., Frohmann, S., Jung, P., and Hübers, H.-W. An optically controllable 0.35 THz single-pixel camera for millimeter resolution imaging, In The International Society of Infrared, Millimeter, and Terahertz Waves (IRMMW17), IEEE, 27 Aug.-1 Sept. 2017, Cancun, Mexico

  17. Kueng, R. and Jung, P. Robust Nonnegative Sparse Recovery and the Nullspace Property of 0/1 Measurements. IEEE Transactions on Information Theory, 64(2), 689–703, August 2017.

  18. Željka Stojanac, Daniel Suess, Martin Kliesch, On the distribution of a product of N Gaussian random variables. In Proc. SPIE 10394, Wavelets and Sparsity XVII, 103941E, 24 August 2017, San Diego, California, United States

  19. Jung, P., Krahmer, F., and Stöger, D., Blind Demixing and Deconvolution at Near-Optimal Rate, IEEE Transactions on Information Theory, 64(2), 704–727, December 2017.

  20. F. Krahmer and Y. K. Liu, Phase Retrieval Without Small-Ball Probability Assumptions, IEEE Transactions on Information Theory, vol. 64, no. 1, pp. 485-500, Jan. 2018.

About Us ¦ Data Privacy Statement ¦ HTML Validation ¦ CSS Validation