Project "Computational Geometric Learning"
- Prof. Dr. Christian Sohler
- Christiane Lammersen
Research supported by the EU within the 7th Framework Programme under contract No. 255827.
High dimensional geometric data are ubiquitous in science and engineering, and thus processing
and analyzing them is a core task in these disciplines. The proposed project aims at extending the
success story of geometric algorithms with guarantees to high-dimensions. This is not a straightforward
task. For many problems, no efficient algorithms exist that compute the exact solution
in high dimensions. This behavior is commonly called the curse of dimensionality. We plan to
address the curse of dimensionality by focusing on inherent structure in the data like sparsity or low
intrinsic dimension, and by resorting to fast approximation algorithms. The following two kinds of
approximation guarantees are particularly desirable: first, the solution approximates an objective
better if more time and memory resources are employed (algorithmic guarantee), and second, the
approximation gets better when the data become more dense and/or more accurate (learning theoretic
guarantee). We want to follow an integrated approach of developing the foundations of a new
field - computational geometric learning - theoretically, but also practically in the form of a high
quality software library and application software.
Alexander Munteanu, Christian Sohler, Dan Feldman: Smallest enclosing ball for probabilistic data. In Proceedings of SOCG 2014, pp. 214-223, 2014.
Hendrik Fichtenberger, Melanie Schmidt: PROBI: A Heuristic for the probabilistic k-median problem. CoRR abs/1309.5781, 2013.
E. Ehsanfar, D. Feldman, C. Sohler: Orthogonal Range Clustering. CGL Technical Report No.: CGL-TR-73, 2013.
Christiane Lammersen, Melanie Schmidt, Christian Sohler: Probabilistic k-Median Clustering in Data Streams. In Proceedings of WAOA 2012, pp. 70-81, 2012.
Christian Sohler, David Woodruff: Subspace Embeddings for the L1-norm with Applications. In Proceedings of STOC 2011, pp. 755-764, 2011.