AG Numerik

Seminar Wintersemester 2009/10

Prof. Dr. S. Dahlke
Prof. Dr. H. Holzmann
Prof. Dr. E. Kostina
Prof. Dr. B. Schmitt

"Sparse Solutions and Sparse Modeling"

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:

Termin Thema Vortragende Betreuer
16.10.2009Dünne Lösungen linearer Gleichungssysteme: Existenz und EindeutigkeitSängerFriedrich
23.10.2009Orthogonal Matching PursuitZhouFriedrich
30.10.2009Stabilität und StörungssätzeEckhardtKinzel
13.11.2009Iterativ gewichtete Kleinste-Quadrate-MethodenFeiseKinzel
20.11.2009AnwendungenPieperKinzel
04.12.2009Least angle regression (LARS), Teil IReuterHolzmann
11.12.2009Least angle regression (LARS), Teil IIKriwetHolzmann
15.01.2010Äquivalenz der Probleme (P0) und (P1) im störungsfreien Fall, Teil IMannesWerner
22.01.2010Äquivalenz der Probleme (P0) und (P1) im störungsfreien Fall, Teil IIWittekindWerner
29.01.2010Äquivalenz der Probleme (P0) und (P1) im Fall von DatenstörungenBilgeSchmitt
24.02.2010Iterative Tresholding-Verfahren, Teil IHenkelDahlke
24.02.2010Iterative Tresholding-Verfahren, Teil IIKrenzerDahlke
24.02.2010Halbglatte Newton-Verfahren, Teil ISchleipenKostina
24.02.2010Halbglatte Newton-Verfahren, Teil IISchreyerKostina

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 l1 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.