Geometric Methods in the Probabilistic Analysis of Condition Numbers

• Applicant: Dr. Martin Lotz
• Subject Area: Mathematics
• Term: from 2008 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 76347084

• Final Report Year: 2011

Final Report Abstract

Das Stipendium hat es mir erlaubt, wichtige Fortschritte auf dem Gebiet der Komplexitätstheorie numerischer Probleme zu erziehlen. Insbesondere ist es gelungen, das Problem der geglätteten Analyse von konischen Konditionszahlen mit unterschiedlichen Verteilungen weitgehend zu lösen. Weitere Forschungsperspektiven sind entstanden. Ein Beispiel ist die Anwendung der Methoden aus der Analyse von Konditionszahlen aus der Optimierung auf neue Gebiete wie Compressed Sensing. Es ist mein Ziel die Anwendungen der probabilistischen Analyse von Konditionszahlen weiter voranzutreiben.

Publications

• Coverage Processes on Spheres and Condition Numbers for Linear Programming. Computational Mathematics and Applications Seminar, Oxford University Computing Laboratory, Januar 2009
  
  
• On the Probability Distribution of Condition Numbers in Linear Programming. 20th International Symposium on Mathematical Programming, Chicago, August 2009
  
  
• Probabilistic analysis of condition numbers in linear and conic programming. Edinburgh Research Group in Optimization (ERGO) Seminar, University of Edinburgh, November 2009
  
  
• Adversarial smoothed analysis. Journal of Complexity, 26:255–262, 2010
  Felipe Cucker, Raphael Hauser, and Martin Lotz
  
• Coverage Processes on Spheres and Condition Numbers for Linear Programming. Annals of Probability, 38(2):570–604, 2010
  Peter Bürgisser, Felipe Cucker, and Martin Lotz
  
• Introduction to Compressed Sensing. Computational Mathematics and Applications Seminar, University of Oxford, Januar 2010