Seminar Wintersemester 2009/10

In diesem Seminar geht es um numerische Verfahren zur Lösung unterbestimmter linearer Gleichungssysteme Ax=b mit möglichst wenigen nichttrivialen Einträgen von x. Derartige Probleme treten bei verschiedenen praktischen Fragestellungen auf, z.B. bei Datenkompression, Entrauschung, Parameteridentifikations- oder Separationsaufgaben.
Für allgemeine Systemmatrizen A ist das Originalproblem NP-hart, d.h., es existieren keine Lösungsverfahren mit in dim(x) polynomieller Laufzeit. Unter gewissen Zusatzannahmen an A und x lässt sich jedoch ein äquivalentes konvexes Minimierungsproblem angeben, das effiziente Rekonstruktionsverfahren erlaubt. Neben dem direkten Einsatz von Optimierungsmethoden diskutieren wir verschiedene numerische Verfahren wie etwa Matching Pursuit, iteratives Shrinkage oder halbglatte Newton-Verfahren.

Die Vorbesprechung findet am Mittwoch, den 15.07.2009, um 16:30 Uhr s.t. in Hörsaal IV, Lahnberge, statt.

Vorausgesetzt werden die Vorlesungen Lineare Algebra I und II sowie Numerische Mathematik I. Für manche Vorträge sind Grundkenntnisse in Stochastik oder Linearer Optimierung hilfreich.
Das Seminar richtet sich an Studenten im Diplomstudiengang Mathematik/Wirtschaftsmathematik, im entsprechenden Bachelor- oder Masterstudiengang sowie an Lehramtsstudenten.

Die vorläufige (fortlaufend aktualisierte) Terminplanung sieht folgendermaßen aus:

Weitere Informationen, Neuigkeiten und was sonst noch wichtig ist:

• In der Vorbesprechung wurde als Termin grundsätzlich Freitag, 14:30-16:00 Uhr vereinbart, über eine eventuelle Blockveranstaltung wird im Verlauf des Seminars entschieden.
• Die Seminarvorträge finden in Hörsaal I statt. Dort ist neben einem Tafelvortrag auch die Nutzung von PC/Beamer oder Tageslichtprojektor möglich (wer einen Tageslichtprojektor verwenden möchte: Bitte vorab eine Mail an Jens)
• Die Blockveranstaltung am 24.02.2010 beginnt um 09:30 Uhr (s.t.).

Sonstige Fragen, Wünsche, Anregungen bitte an Jens.

Literatur:

• Bruckstein, A.M., Donoho, D.L. und Elad, M.: From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images, SIAM Rev. 51 (2009), Nr. 1, S. 34-81. 2005.
• Candes, E.J., Romberg, J.K. und Tao, T.: Stable Signal Recovery from Incomplete and Inaccurate Measurements, Commun. Pure Appl. Math. 59 (2006), Nr. 8, S. 1207-1223.
• Candes, E.J. und Tao, T.: Decoding by Linear Programming, IEEE Trans. Inform. Theory 51 (2005), Nr. 12, S. 4203-4215.
• Chen, S.S., Donoho, D.L. und Saunders, M.A.: Atomic Decomposition by Basic Pursuit, SIAM J. Sci. Comput. 20 (1998), Nr. 1, S. 33-61.
• Chen, X., Nashed, Z. und Qi, L.: Smoothing Methods and Semismooth Methods for Nondifferentiable Operator Equations, SIAM J. Numer. Anal. 38 (2000), Nr. 4, S. 1200-1216.
• Donoho, D.L. und Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via l₁ minimization, Proc. Natl. Acad. Sci. 100 (2003), S. 2197-2202.
• Donoho, D.L., Elad, M. und Temlyakov, V.N.: Stable Recovery of Sparse Overcomplete Representations in the Presence of Noise, IEEE Trans. Inform. Theory 52 (2006), Nr. 1, S. 6-18.
• Efron, B. Hastie, T., Johnstone, I.M. und Tibshirani, R.: Least angle regression, Ann. Statist. 32 (2004), S. 407-499.
• Elad, M., Matalon, B. und Zibulevsky, M.: Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization, Appl. Comput. Harmon. Anal. 23 (2007), S. 346-367.
• Griesse, R. und Lorenz D.A.: A semismooth Newton method for Tikhonov functionals with sparsity constraints, Inv. Problems 24 (2008), Nr. 3, 19.
• Rao, B.D. und Kreutz-Delgado, K.: An Affine Scaling Methodology for Best Basis Selection, IEEE Trans. Signal Process. 47 (1999), Nr. 1, S. 187-200.
• Tropp, J.A.: Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Inform. Theory 50 (2004), Nr. 10, S. 2231-2242.