RaSenQuaSI: Randomisierte Erfassung und Quantisierung von Signalen und Bildern
Zusammenfassung der Projektergebnisse
Die Emmy-Noether-Nachwuchsgruppe Randomisierte Erfassung und Quantisierung von Signalen und Bildern unter Leitung von Felix Krahmer untersuchte das Zusammenspiel von Struktur und Zufall in Anwendungen der Signalverarbeitung. Das Ziel war zu verstehen wie zufallsgetriebene Designs von Messsystemen zusammen mit geeigneten Rekonstruktionsverfahren beweisbare Rekonstruktionsgarantien ermöglichen. Zentral für den Forschungsplan der Gruppe war eine ganzheitliche Perspektive, die eine zufällige Wahl der Designparameter unter Berücksichtigung der strukturellen Anforderungen der Anwendung mit darauf abgestimmten Rekonstruktionsalgorithmen kombiniert. Die Agenda strukturierte sich in die drei Bereiche Compressive Sensing, Quantisierung und Phasenrekonstruktion. Compressive Sensing untersucht Verfahren für die Rekonstruktion von Signalen, die eine besonders einfache Darstellung erlauben, aus unterbestimmten Messungen. Zu den zentralen Herausforderungen, die die Gruppe erfolgreich angehen konnte, gehören die mathematische Analyse der Rekonstruktionsqualität für verrauschte Daten mit unbekanntem Rauschlevel sowie Rekonstruktionsverfahren, die so effizient sind, dass sie die Rekonstruktion von besonders hochdimensionalen Signalen ermöglichen. In Quantisierungsproblemen werden zusätzlich digitale Darstellungen integriert, wieder unter der Fragestellung, wie gut ein Signal aus den darstellenden Bits rekonstruiert werden kann. Die Gruppe entwickelte die erste fast optimale Fehleranalyse für Sigma-Delta-Quantisierung, eine häufig verwendete Klasse von Quantisierungsverfahren, für ein randomisiertes Compressive-Sensing- System unter Strukturbedingungen, sowie eine der ersten Analysen für zufällig abgetastete Signale mit beschränktem Frequenzbereich. Eine weitere Herausforderung in der Bildgebung im Nanobereich ist, dass nur Intensitäten gemessen werden können und die Phaseninformation verloren geht. Das resultierende Phasenrekonstruktionsproblem wurde sowohl aus einer theoretischen Perspektive, in Hinblick auf die Grenzen der Anwendbarkeit, als auch im praktischen Kontext der Ptychographie untersucht, in welchem ein konkretes Szenario mit mehrfach verschobenen Messöffnungen betrachtet wird. Beispielsweise hat die Gruppe eine Methode entwickelt und analysiert, mit der aus Konditionierungsproblemen und Symmetrien resultierende Einschränkungen überwunden werden können. Aus mathematischer Perspektive führten die behandelten Probleme zu herausfordernden Fragestellungen an der Schnittstelle vieler mathematischer Disziplinen. Die Arbeit der Emmy-Noether-Gruppe kombiniert Techniken der Wahrscheinlichkeitstheorie, der Optimierung, der Banachraumgeometrie, der Approximationstheorie und der Fourieranalysis. Dabei sind einige der entwickelten Ergebnisse auch von unabhängigem mathematischem Interesse wie zum Beispiel die Charakterisierung der Geometrie von zufälligen Polytopen, die von endlastig verteilten Zufallsvektoren aufgespannt werden.
Projektbezogene Publikationen (Auswahl)
-
A Novel Compressed Sensing Scheme for Photoacoustic Tomography. SIAM Journal on Applied Mathematics, 75(6), 2475-2494.
Sandbichler, M.; Krahmer, F.; Berer, T.; Burgholzer, P. & Haltmeier, M.
-
A Unified Framework for Linear Dimensionality Reduction in L1. Results in Mathematics, 70(1-2), 209-231.
Krahmer, Felix & Ward, Rachel
-
Compressive Sensing with Redundant Dictionaries and Structured Measurements. SIAM Journal on Mathematical Analysis, 47(6), 4606-4629.
Krahmer, Felix; Needell, Deanna & Ward, Rachel
-
Noise-Shaping Quantization Methods for Frame-Based and Compressive Sampling Systems. Applied and Numerical Harmonic Analysis, 157-184.
Chou, Evan; Güntürk, C. Sinan; Krahmer, Felix; Saab, Rayan & Yılmaz, Özgür
-
Quantization and compressive sensing. In Compressed Sensing and its Appl.: MATHEON Workshop 2013, pages 193–237. Springer, 2015
P. T. Boufounos et al.
-
An arithmetic–geometric mean inequality for products of three matrices. Linear Algebra and its Applications, 488, 1-12.
Israel, Arie; Krahmer, Felix & Ward, Rachel
-
Improved recovery guarantees for phase retrieval from coded diffraction patterns. Applied and Computational Harmonic Analysis, 42(1), 37-64.
Gross, D.; Krahmer, F. & Kueng, R.
-
On two Random Models in Data Analysis.
James, David
-
Optimal Injectivity Conditions for Bilinear Inverse Problems with Applications to Identifiability of Deconvolution Problems. SIAM Journal on Applied Algebra and Geometry, 1(1), 20-37.
Kech, Michael & Krahmer, Felix
-
The homotopy method revisited: Computing solution paths of $\ell _1$-regularized problems. Mathematics of Computation, 87(313), 2343-2364.
Bringmann, Bjoern; Cremers, Daniel; Krahmer, Felix & Moeller, Michael
-
Total Variation Minimization in Compressed Sensing. Applied and Numerical Harmonic Analysis, 333-358.
Krahmer, Felix; Kruschel, Christian & Sandbichler, Michael
-
Compressed sensing, sparsity, and related topics. PhD thesis, Univ. Innsbruck, 2018
M. Sandbichler
-
Phase Retrieval Without Small-Ball Probability Assumptions. IEEE Transactions on Information Theory, 64(1), 485-500.
Krahmer, Felix & Liu, Yi-Kai
-
Spectral Methods for Passive Imaging: Nonasymptotic Performance and Robustness. SIAM Journal on Imaging Sciences, 11(3), 2110-2164.
Lee, Kiryung; Krahmer, Felix & Romberg, Justin
-
Compressed Sensing and ΣΔ-Quantization.
Feng, J.-M.
-
Quantized compressed sensing for random circulant matrices. Applied and Computational Harmonic Analysis, 47(3), 1014-1032.
Feng, Joe-Mei; Krahmer, Felix & Saab, Rayan
-
Complex Phase Retrieval from Subgaussian Measurements. Journal of Fourier Analysis and Applications, 26(6).
Krahmer, Felix & Stöger, Dominik
-
High-order low-bit Sigma-Delta quantization for fusion frames. Analysis and Applications, 19(01), 1-20.
Gao, Zhen; Krahmer, Felix & Powell, Alexander M.
-
On the Convex Geometry of Blind Deconvolution and Matrix Completion. Communications on Pure and Applied Mathematics, 74(4), 790-832.
Krahmer, Felix & Stöger, Dominik
-
Sparse Harmonic Transforms: A New Class of Sublinear-Time Algorithms for Learning Functions of Many Variables. Foundations of Computational Mathematics, 21(2), 275-329.
Choi, Bosu; Iwen, Mark A. & Krahmer, Felix
-
Well-conditioned ptychographic imaging via lost subspace completion. Inverse Problems, 36(10), 105009.
Forstner, Anton; Krahmer, Felix; Melnyk, Oleh & Sissouno, Nada
-
A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions. Numerical Algorithms, 89(4), 1479-1520.
Kämmerer, Lutz; Krahmer, Felix & Volkmer, Toni
-
Group Testing for SARS-CoV-2 Allows for Up to 10-Fold Efficiency Increase Across Realistic Scenarios and Testing Strategies. Frontiers in Public Health, 9.
Verdun, Claudio M.; Fuchs, Tim; Harar, Pavol; Elbrächter, Dennis; Fischer, David S.; Berner, Julius; Grohs, Philipp; Theis, Fabian J. & Krahmer, Felix
-
On Recovery Guarantees for Angular Synchronization. Journal of Fourier Analysis and Applications, 27(2).
Filbir, Frank; Krahmer, Felix & Melnyk, Oleh
-
On Recovery Guarantees for One-Bit Compressed Sensing on Manifolds. Discrete & Computational Geometry, 65(4), 953-998.
Iwen, Mark A.; Krahmer, Felix; Krause-Solberg, Sara & Maly, Johannes
-
On the geometry of polytopes generated by heavy-tailed random vectors. Communications in Contemporary Mathematics, 24(03).
Guédon, Olivier; Krahmer, Felix; Kümmerle, Christian; Mendelson, Shahar & Rauhut, Holger
-
Optimal fast Johnson–Lindenstrauss embeddings for large data sets. Sampling Theory, Signal Processing, and Data Analysis, 19(1).
Bamberger, Stefan & Krahmer, Felix
-
Johnson–Lindenstrauss Embeddings with Kronecker Structure. SIAM Journal on Matrix Analysis and Applications, 43(4), 1806-1850.
Bamberger, Stefan; Krahmer, Felix & Ward, Rachel
-
On the robustness of noise-blind low-rank recovery from rank-one measurements. Linear Algebra and its Applications, 652, 37-81.
Krahmer, Felix; Kümmerle, Christian & Melnyk, Oleh
-
The Hanson–Wright inequality for random tensors. Sampling Theory, Signal Processing, and Data Analysis, 20(2).
Bamberger, Stefan; Krahmer, Felix & Ward, Rachel
-
Enhanced Digital Halftoning via Weighted Sigma-Delta Modulation. SIAM Journal on Imaging Sciences, 16(3), 1727-1761.
Krahmer, Felix & Veselovska, Anna
-
Quantization of Bandlimited Functions Using Random Samples. 2023 International Conference on Sampling Theory and Applications (SampTA), 1-5.
Joy, Rohan; Krahmer, Felix; Lupoli, Alessandro & Ramakrishan, Radha
-
Quantization of Bandlimited Graph Signals. 2023 International Conference on Sampling Theory and Applications (SampTA), 1-5.
Krahmer, Felix; Lyu, He; Saab, Rayan; Veselovska, Anna & Wang, Rongrong
-
Representing and Recovering Structured High-Dimensional Data: Fast Dimension Reduction, Recovery Guarantees, and Neural Network Representation. PhD thesis, TUM, 2023
S. Bamberger
-
Scalability in Ill-posed Machine Learning Problems: Bridging Least Squares Methods with (Non-) convex Algorithms. PhD thesis, TUM, 2023
C. Mayrink Verdun
-
A one-bit quantization approach for low-dose Poisson phase retrieval. 2024 International Workshop on the Theory of Computational Sensing and its Applications to Radar, Multimodal Sensing and Imaging (CoSeRa), 42-46.
Römer, Patricia & Krahmer, Felix
-
Background Removal for Ptychography via Wigner Distribution Deconvolution. SIAM Journal on Imaging Sciences, 17(3), 1978-2014.
Melnyk, Oleh & Römer, Patricia
-
Fast, blind, and accurate: Tuning-free sparse regression with global linear convergence. In 37th CoLT, pages 3823–3872. PMLR, 2024
C. Mayrink Verdun et al.
-
NON-INTRUSIVE SURROGATE MODELLING USING SPARSE RANDOM FEATURES WITH APPLICATIONS IN CRASHWORTHINESS ANALYSIS. International Journal for Uncertainty Quantification.
Herold, Maternus; Jehle, Jonas; Krahmer, Felix & Veselovska, Anna
