Views
Reports of the Graduate School
The annual report of the Graduate School for the year 2008 contains a list of the publications of the Graduate School's members. Moreover, also the programmes of the workshops and conferences organised in the context of the Graduate School are listed there. In the former report for the university principal you may find as well short member profiles.
Forschungsaktivitäten im Rahmen des Kollegs
Funktionalanalysis und theoretische Physik
- Organisatoren: W. Arendt, F. Steiner
Ein Forschungsschwerpunkt in der angewandten Analysis bildet die Spektraltheorie. Zum einen handelt es sich zunächst einmal um operatorentheoretische Fragen. Man ordnet Operatoren ein Spektrum zu, eine abgeschlossene Teilmenge der komplexen Ebene, die diskret oder kontniuierlich sein kann. Im Fall von Schrödingeroperatoren stimmt das mathematische mit dem physikalischen Spektrum, wie es durch die Energieübergänge bei Atomen entsteht, überein. Eine wichtige mathematische Aufgabenstellung ist es, aus dem Spektrum mathematische oder auch physikalische oder geometrische Eigenschaften herzuleiten. Zum Beispiel sucht man Bedingungen an die Geometrie des Gebietes sowie die Randbedingungen oder an die Mannigfaltigkeit zu finden, die dazu führen, dass die Lösungen von Diffusionsgleichungen gegen ein Gleichgewicht streben. In der Quantenmechanik interessiert man sich dafür, wie die Geometrie der Mannigfaltigkeit das Langzeitverhalten von Lösungen der Schrödingergleichung beeinflusst.
Eine weitere sehr schwierige, berühmte Frage stellt ein inverses Problem dar: Kann man aus den Eigenwerten, d.h. den Eigenfrequenzen des Laplaceoperators auf einem Gebiet die Geometrie und Topologie des Gebietes ablesen. Mit den Worten von Marc Kac heisst die Frage: Kann man die Form eines Gebietes hören - can one hear the shape of a drum? - Diese Frage hat im Allgemeinen eine negative Antwort, aber die Lösungen der Diffusionsgleichung bestimmen das Gebiet und die Randbedingungen. Fragen von ähnlicher Natur treten auch in der Kosmologie auf. Da geht es um andere (hyperbolische) Geometrien und um die Lösungen der Einsteinschen Gravitationsgleichungen, welche die Evolution bzw. Expansion des Universums beschreiben. Auch bei der Beschreibung von Quantenchaos sind Varianten dieses inversen Problems bedeutsam.
Literatur
- W. Arendt: Does diffusion determine the body?, J. Reine Angew. Math. 550 (2002) 97-123.
- R. Aurich, S. Lustig, F. Steiner and H. Then: Can one hear the shape of the Universe?, published under the title: Indications about the Shape of the Universe from the Wilkinson Microwave Anisotropy Probe Data, Phys. Rev. Lett. 94 (2005) 021301.
Algorithmic information
- Organisors: M. Bossert, U. Schöning
The amount of information contained in a typical input of an algorithm can be measured in the sense of Shannon's concept of entropy, or alternatively, in terms of so called Kolmogorov complexity. Some algorithms, like sorting algorithms, can be interpreted as entropy-reducing devices since the output of the algoritrhm, the sorted sequence, contains less information than the unsorted input. Using such information-theoretic views on algorithms, it is often possible to prove sharp bounds on their (worst-case or average-case) complexity behaviour.
A different context where information-theoretic concepts play an important role are stochastic algorithms. Such algorithms need perfect (i.e. high entropy) random numbers. But in practice stochastic algorithms are operated with random numbers from some imperfect pseudo-random source. Here the question arises whether and to which extend such algorithms behave correctly in such a scenario.
Another important question concerns the asymptotics of certain recurrences describing the behaviour of stochastic algorithms. For the analysis of such recurrences several deep techniques from probability theory and statistics are required. The applications of such models cover a wide range, from algorithm analysis to financial mathematics.
Literature
- M. Li, P. Vitanyi: Kolmogorov Complexity and its Applications, Springer, 1997.
- R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press, 1995.
Complexity and learning in neuronal nets
- Organisors: G. Palm, U. Schöning, J. Toran
Neural networks, such as in the human brain, are highly complex dynamic systems which perform some kind of information processing. A more biologically adequate modelling and simulation of such processes will lead to a deeper understanding of the respective processes in neurobiology. For this modelling purpose, nonlinear differential equations are used.
In their simplest form, artificial neural networks can be understood as special kinds of Boolean switching circuits (perceptrons). Often polynomials are used for modelling such networks, and their analysis uses methods from spectral theory.
By modifying the input weights of such an artificial neural networks according to certain learning rules, it is possible to train such networks towards achieving some desired input-output behaviour. The possibilities and limitations of such learning processes are studied in statistical learning theory which requires methods from functional analysis, approximation theory, stochastics, and information theory.
Literature
- K.Y. Siu, V. Roychowdhury, T. Kailath: Discrete Neural Computation, Prentice-Hall, 1995.
- D.J.C. MacKay: Information Theory, Inference, and Learning Algorithms, Cambridge, 2003.
- M. Anthony, P.L. Barlet: Neural Network Learning: Theoretical Foundations, Cambridge University Press, 2001.
- T. Hastie, R. Tibshirani, J. Feldman: The Elements of Statistical Learning, Springer Verlag 2001.
Adaption und Lernen in Quantennetzen
- Organisatoren: W. Schleich, G. Palm, J. Toran
Neuronale Netze mit klassischen digitalen oder analogen Neuronen bilden ein intensiv untersuchtes Gebiet, das viele hochinteressante Fragestellungen beinhaltet. Im Rahmen der Quanteninformationsverarbeitung gibt es die Möglichkeit, diese klassischen Netze um quantenphysikalische Gesetzmässigkeiten zu erweitern. In erster Linie geht es dabei nicht um eine Modellierung biologischer Systeme, sondern um eine mögliche quantentechnologische Anwendung solcher Strukturen. Das schliesst aber nicht aus, dass aus einem besseren Verständnis dieser nichtklassischen Netze neue Ansatzpunkte für neurobiologische Betrachtungen gewonnen werden können.
Eine nahe liegende Verallgemeinerung klassischer Netze ist die Ersetzung klassischer Zwei-Zustands Neuronen durch ein Zwei-Niveau Quantensystem (Spin - System). Die Vernetzung kann dann durch Spin-Spin Kopplungen geschehen, wodurch sich ein komplexes Netzwerk vom Ising-Typ ergibt. Das "Feuern" der Quanten-Neuronen wird nun nicht mehr durch klassische Schwellenwertgatter bestimmt, sondern von quantenmechanisch interferierenden Wahrscheinlichkeitsamplituden. Eine wichtige Frage ist, welche adaptiven Lernverfahren für solche Quantennetze anwendbar sind. Selbstlernend adaptiert wird die Spin-Spin Kopplungsstärke mit dem Ziel, quantenmechanische Zustände ("Quantenmuster") an der Eingangsschicht des Netzes zu unterscheiden. Von besonderem Interesse ist dabei die komplexe Entwicklung nichtklassischer Korrelationen (Verschränkung) zwischen den Schichten des Netzwerks. Die Modellierung und Analyse dieser Systeme erfolgt mit Quanten-Monte-Carlo Methoden und mit den Ergebnissen aus Approximations- und Schätztheorie.
Realisierungen solcher Quantennetzwerke mit linearen quantenoptischen Elementen oder mit atomoptischen Verfahren sind experimentell möglich und werden heute schon zum Entwurf von Quantencomputern in Betracht gezogen.
Project outline in English
- Adaption and learning in quantum neural networks
Classical neural networks are a promising and highly interesting field of modern information processing and technology. The project focuses on the combination of this classical network paradigm with the idea to process information with the help of quantum systems. The emerging quantum neural networks will show completely new features and complexity as compared to their classical counterparts. The usual input / output structure will be dissolved. Information will now be represented by interfering probability amplitudes. Moreover, these quantum signals can be entangled. Hence, the correlations between substructures of a quantum net will be nonlocal and no longer describable by any classical model. We are particularly interested in possible learning procedures based on quantum feedback and adaption.
Literatur
- M. A. Nielsen und I. L. Chuang: Quantum Computation and Quantum Information, Cambridge University Press, 2000
- G. Mahler und V. A. Weberruss: Quantum Networks, Springer, Berlin, 1995
- M. Lewenstein und M. Olko: Network 2, 207 (1991), Phys. Rev. A 45, 8938 (1992)
Informationsübertragung bei fehlerbehafteten Kanälen
- Organisatoren: M. Bossert
Bei der zuverlässigen Datenübertragung sind auf die Problemstellung zugeschnittene statistische Methoden notwendig. Zum Teil können bekannte Verfahren der nichtparametrischen Statistik (Schätzung von bedingten Verteilungen u.ä.) angewandt werden, für andere Problemstellungen müssen neue Verfahren entwickelt werden. Mit M. Pawlak (Dept. of Electrical Engineering and Computing, University of Manitoba, Kanada) besteht ein längerfristiges Projekt zur Rekonstruktion von Signalen unter zufälligen Störungen, das in das Kolleg eingebaut werden kann.
Zur empirischen Untersuchung existieren noch viele ungelöste mathematische Probleme, um die Verfahren praxistauglich zu machen. Man verwendet Codes, die den Daten Redundanz zufügen und mit deren Hilfe dann Fehler korrigiert werden können. Die besten Codes zu finden scheitert ebenso an der Komplexität, wie gute Codes effizient zu decodieren. Deshalb verwendet man häufig Codes, die zwar nicht zu den besten bekannten gehören, jedoch mit geringer Komplexität effizient decodierbar sind. Die Decodierung ist eng verknüpft mit Verteilungen von Zufallsvariablen. Iterative Verfahren werden verwendet, aber deren Konvergenz kann noch nicht mathematisch erklärt werden.
Bei vielen Anwendungen, wie etwa optische Datenübertragung oder Magnetspeicher benötigt man die Garantie für Bitfehlerraten kleiner als $10^{-15}$. Dies kann nur durch mathematische Analyse, nicht durch Simulation, garantiert werden. Jedoch existieren viele Codeklassen, bei denen eine solche Analyse noch unbekannt ist.
Kanäle können aus verschiedenen Gründen fehlerbehaftet sein. Einer ist, dass in einem Mehrnutzersystem andere Nutzer gleichzeitig ihre Daten übertragen und als Störer wirken. Dieses Gebiet wird als Netzwerksinformationstheorie bezeichnet und steht an den Anfängen, was die mathematische Analyse betrifft. Es bedarf neuer Denk- und Beschreibungsweisen, um theoretische fundierte Aussagen treffen zu können.
Literatur
- M. Bossert, M. Breitbach: Digitale Netze, Teubner, 1999.
Algebra und Informationswissenschaft
- Organisatoren: M. Bossert, W. Lütkebohmert
Ein wesentlicher Kontaktpunkt von Algebra und Informationstheorie sind die theoretischen Grundlagen für die zuverlässige Übertragung von Daten; d.h. man will die Übermittelung von Daten stabil gegenüber kleinen Störungen wie z.B. Rauschen gestalten. Kleinere Verfälschungen sollen dabei automatisch korrigiert werden. Aus mathematischer Sicht hat man dazu Untervektorräume eines Tupelraums über einem endlichen Körper zu konstruieren, so dass jeder von Null verschiedene Vektor möglichst viele von Null verschiedene Koordinaten hat. Weiterhin hat man Algorithmen zu entwerfen, die aus einem gestörten Vektor, sofern nur wenige Fehler vorhanden sind, den ursprünglichen Informationsvektor extrahieren können. Die Konstruktionen solcher Strukturen basieren im Wesentlichen auf Methoden der Diskreten Mathematik (Kombinatorik, Algebra und Geometrie über endlichen Körpern).
Neueste Forschungsergebnisse interpretieren klassische Reed-Solomon Codes als solche Kurven und erhöhen dadurch die Anzahl der decodierbaren Fehler in einigen Fällen. Aus der Vergangenheit sind weitere Fälle bekannt, bei denen mathematische Ergebnisse vorteilhaft praktische Verfahren verbessert haben.
Literatur
- M. Bossert: Channel Coding for Telecommunications, Wiley, 1999
- W. Lütkebohmert: Codierungstheorie, Vieweg-Verlag 2003
Algorithmic number theory
- Organisors: W. Lütkebohmert, H. Maier, U. Schöning
Modern number theory has various applications in cryptography. Such methods are often based on the difficulty of factoring large natural numbers into their prime factors or on calculating discrete logarithms on elliptic curves. Here the theory of algebraic curves on finite fields plays an important role.
Since Shor has shown that factoring can be solved efficiently on quantum computers (if they can be built physically), algorithms on quantum computers have entered the scene. Other such algorithms concern the computation of periodic number theoretic structures such as class groups and groups of unities on finite number fields.
Further recent results concern the new polynomial-time algorithm for prime recognition by Agrawal et al. It should be analysed whether these new techniques have applications in cryptography.
Literatur
- S. Y. Yan. Number Theory for Computing, Springer, 2002.
- J. Buchmann: Einführung in die Kryptographie, Springer, 1999.
- P. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26:5 (1997) 1484--1509.
- M. Agrawal, N. Kayal, N. Saxena: PRIMES is in P. Tech. Repoirt, Dept. of Computer Science & Engineering, Indian Institute of Technoilogy, Kanpur, 2003.
Detektion mit nichtlinearen dynamischen Systemen
- Organisatoren: J. Lindner, W. Arendt
Künftige drahtlose Informationsübertragung wird zunehmend bedeuten, dass auf Sende- und Empfangsseite mehrere Antennen eingesetzt werden. Der Grund dafür ist, dass die Kapazität der so entstehenden MIMO-Kanäle (MIMO: Multiple-Input-Multiple-Output) linear mit der Zahl der Sende-Empfangsantennen-Paare anwächst, während im konventionellen Fall dies nur mit einem exponentiellen Anstieg der Sendeleistung möglich ist. Zum Ausschöpfen des entstehenden Potentials müssen Verfahren zum Einsatz kommen, bei denen die Energie der Sendesymbole von allen Teilnehmern in Raum, Zeit und Frequenz verteilt wird. Vektorwertige Übertragungsmodelle sind eine adäquate Beschreibung für derartige Systeme, wobei die Vektorkomponenten für einzelne Teilnehmer und/oder Antennen stehen. Die MIMO-Kanäle und das Spreizen führen dabei zu einem "Übersprechen" zwischen den Vektorkomponenten, das wegen des hinzukommenden additiven Rauschens nicht einfach rückgängig gemacht werden kann. Auf der Empfangseite bedeutet ein optimales Vorgehen vielmehr, Entscheidungen über die gesendeten Symbole im Sinne der statistischen Entscheidungstheorie zu treffen, was zu einem Realisierungsaufwand führt, der exponentiell mit der Zahl der Teilnehmer, dem Gedächtnis der vorliegenden Mehrwege-Kanäle und der Weite des Spreizens anwächst.
Gesucht sind deshalb suboptimale Detektionsmethoden, die bei tragbarem Realisierungsaufwand (Zahl der Rechenoperationen pro übertragenem Bit) in ihrer Leistungsfähigkeit möglichst nahe an die theoretischen Grenzen herankommen. Die Frage, welche Methoden dies sein können, lässt sich heute nicht theoretisch beantworten. Bekannt ist, dass iterative Verfahren, die die notwendige Vektor-Entzerrung und Vektor-Decodierung in einer Iterationsschleife durchführen (Turbo-Prinzip), mit einem nicht-exponentiellen Aufwand bereits gute Ergebnisse liefern können. Auch die Vektorentzerrung allein beinhaltet schon dieses Aufwandsproblem und auch hier sind es rekurrente nichtlineare dynamische Systeme die dem Ziel nahe kommen können. Der Detektionsvorgang bedeutet eine starke Informationsreduktion: Von der Vielfalt der möglichen Folgen von Eingangsvektoren existiert nach der Detektion nur noch die wesentlich kleinere, mit der Sendeseite vereinbarte. Während der inneren Iterationen ein Informationsaustausch (Entzerrer-Decoder) statt, der schließlich zu einer Entscheidung über die empfangenen Symbole führt. Mit den sog. EXIT-Charts gibt es erste Ansätze, den inneren Informationsaustausch bei rekurrenten Strukturen quantitativ zu beschreiben.
Ziel der Arbeiten soll sein, generelle Aussagen darüber zu finden, welche rückgekoppelten nichtlinearen dynamischen Systeme für derartige Detektionsaufgaben geeignet sind, wann Konvergenz gegeben ist und welche Bedeutung hierbei der interne Informationsaustausch hat.
Literatur
- E. Goles, S. Martinez: Neural and Automata Networks, Kluwer Academic Publishers, Dordrecht/Netherlands, 1990.
- C. Heegard, S. Wicker: Turbo Coding, Kluwer Academic Publishers, Boston, 1998.
- K. Chugg, A. Anastasopoulos, X. Chen: Iterative Detection, Kluwer Academic Publishers, Boston, 2000.
Analyse und Prognose der Evolution komplexer Systeme
- Organisation: M. Schulz, F. Steiner
Ein komplexes System besitzt gewöhnlich so viele Freiheitsgrade, dass eine vollständige Beschreibung praktisch ausgeschlossen ist. Man beschränkt sich daher auf intuitiv festgelegte relevante Freiheitsgrade, die entsprechend dem Problem und der gewünschten Beschreibungsebene gewählt werden. Mit der Wahl eines geeigneten Satzes relevanter Observablen ist stets ein Informationsverlust über die dynamische Situation des betrachteten Systems verbunden, so dass dessen Evolution nur noch im Rahmen einer statistischen Interpretation verstanden werden kann. Hieraus ergeben sich zwei Fragen:
- Wie kann man aus einer beschränkten Anzahl oder im Extremfall nur einer einzigen tatsächlichen Realisierung einer Zeitreihe von relevanten Observablen wesentliche und verlässliche Informationen über die intrinsische Dynamik des jeweiligen komplexen Systems gewinnen?
- Wie kann man aus geeigneten Charakteristika brauchbare Schlussfolgerungen über die zukünftige Entwicklung eines komplexen Systems treffen?
Beide Fragen lassen sich im Rahmen physikalischer Konzepte wenigstens formal beantworten. Allerdings erfordert die Analyse eines konkreten Systems die Bewältigung zahlreicher Probleme, deren Lösung ein weites und überaus aktuelles Forschungsgebiet der theoretischen Physik darstellt.
Literatur
- M.Schulz: Statistical Physics and Economics, Concepts, Tools, and Applications, Springer Tracts in Modern Physics, Vol.184, Springer, 2003.
