# Master Projects (Masterarbeiten)

If you are interested in one of the following topics, please contact the person listed with the respective topic.

If you don't find a compelling topic in our list, we are always keen on hearing about your ideas in the area of our research interests (see the Research section of our website). You are most welcome to discuss your interests with us.

Also, we have a list of finished diploma theses on our website.

## List of Projects

- Approximation-theoretic properties of deep neural networks
- Distribution-preserving lossy compression
- Phase transitions for matrix separation
- Estimation of fractal dimensions
- Analyzing cost functions for generative adversarial networks

### Approximation-theoretic properties of deep neural networks (DA)

Deep neural networks approximate functions by arranging neurons in layers that are connected by weighted edges. In deep learning [1, 2] the edge weights of such networks are learned by "training" the network on examples. Deep learning-based methods have recently shown stellar performance in various practical applications, such as speech recognition [3], image classification [4], handwritten digit recognition [5], and game intelligence [6]. This success led to a renewed interest in understanding theoretical properties of (deep) neural networks.

In this project, you will study various theoretical advances in deep neural network theory. Specifically, you will first familiarize yourself with a new theory [7] which characterizes the relation between connectivity and memory requirements of deep neural networks and the complexity of the function class the networks are to approximate. Tight bounds on the Vapnik–Chervonenkis dimension of deep networks were obtained recently in [8]; these results quantify the ability of the trained network to generalize, i.e, to perform well on test data. Finally, in [9] the relation between network architecture and the structure of the function classes the network approximates is analyzed. The aim of this project is to put these different theories into perspective with each other.

Type of project: 100% theory

Prerequisites: Strong mathematical background, knowledge on (deep) neural networks

Supervisor: Recep Gül

Professor:
Helmut Bölcskei

References:

[1]
Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” *Nature*, vol. 521, pp. 436–444, 2015.
[Link to Document]

[2]
I. Goodfellow, Y. Bengio, and A. Courville, "Deep learning," *MIT Press*, 2016.
[Link to Document]

[3]
G. Hinton, L. Deng, D. Yu, et al., "Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups," *IEEE Signal Process. Mag.*, vol. 29, no. 6, pp. 82–97, 2012.
[Link to Document]

[4]
A. Krizhevsky, I. Sutskever, and G. E. Hinton, "Imagenet classification with deep con- volutional neural networks," in *Advances in Neural Information Processing Systems 25*, Curran Associates, Inc., pp. 1097–1105, 2012.
[Link to Document]

[5]
Y. LeCun, L. D. Jackel, L. Bottou, et al., "Comparison of learning algorithms for handwrit- ten digit recognition," *International Conference on Artificial Neural Networks*, pp. 53–60, 1995.
[Link to Document]

[6]
D. Silver, A. Huang, C. J. Maddison, et al., "Mastering the game of Go with deep neural networks and tree search," *Nature*,vol. 529, no. 7587, pp. 484–489, 2016.
[Link to Document]

[7]
H. Bölcskei, P. Grohs, G. Kutyniok, and P. Petersen, "Optimal approximation with sparsely connected deep neural networks," *arXiv:1705.01714*, 2018.
[Link to Document]

[8]
P. L. Bartlett, N. Harvey, C. Liaw, and A. Mehrabian, "Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks," * arXiv:1703.02930*, 2017.
[Link to Document]

[9]
P. Petersen, M. Raslan, and F. Voigtlaender, "Topological properties of the set of functions generated by neural networks of fixed size," *arXiv:1806.08459*, 2018.
[Link to Document]

### Distribution-preserving lossy compression (SA/DA)

Recent advances in extreme image compression [1] allow artifact-free image reconstruction even at very low bitrates. Motivated by these results, [2] formalizes the concept of distribution-preserving lossy compression (DPLC), which optimizes the compression rate-distortion tradeoff under the constraint of the reconstructed (decompressed) samples following the empirical distribution of the training data. Specifically, a DPLC system (almost) perfectly reconstructs the training data when enough bits are allocated to the compressed representation. When zero bits are assigned to the compressed representation it learns a (deep) generative model of the data, and for intermediate bitrates DPLC smoothly interpolates between matching the distribution of the training data and perfectly reconstructing the training samples (cf. the figure on the left; the numbers at the top correspond to different rates (in bits per pixel) and each row corresponds to a different decoder realization). The DPLC framework introduced in [2] was so far applied to images only. This project shall explore new applications.

Type of project: 20%-40% theory, 60%-80% programming, depending on the student's preference

Prerequisites: Programming, linear algebra, experience with deep learning software is a plus

Supervisor: Michael Tschannen

Professor:
Helmut Bölcskei

References:

[1]
E. Agustsson, M. Tschannen, F. Mentzer, R. Timofte, and L. Van Gool, "Generative adversarial networks for extreme learned image compression," arXiv:1804.02958, 2018.
[Link to Document]

[2] M. Tschannen, E. Agustsson, and M. Lučić, "Deep generative models for distribution-preserving lossy compression," arXiv:1805.11057, 2018. [Link to Document]

### Phase transitions for matrix separation (DA)

A phase transition is a sharp division of the parameter space of a data processing problem into a region of success and a region of failure. This phenomenon was studied for the matrix separation problem [1, 2] and for the matrix completion problem [3] under specific recovery algorithms. Information-theoretic phase transitions do not depend on specific recovery algorithms and reveal what is possible in principle. Recently, information-theoretic phase transitions were obtained for the matrix completion problem [4] and for the signal separation problem [5].

The first goal of this project is to build on the techniques developed in [4, 5] to characterize information-theoretic phase transitions for the matrix separation problem, which in its traditional incarnation separates a low-rank matrix from a sparse matrix. The second goal is to investigate pairs of matrix structures (beyond low-rank and sparse) that allow for separation and to characterize their information-theoretic phase transitions.

Type of project: 80% theory, 20% simulation

Prerequisites: Strong mathematical background, measure theory, probability theory

Supervisor: Erwin Riegler

Professor:
Helmut Bölcskei

References:

[1] D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp, “Living on the edge: A geometric theory of phase transitions in convex optimization,” *Information and Inference*, vol. 3, no. 3, pp. 224–294, Jun. 2014.
[Link to Document]

[2] V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky, “Rank-sparsity incoherence for matrix decomposition,” *SIAM Journal on Optimization*, vol. 21, no. 2, pp. 572–596, Jun. 2011.
[Link to Document]

[3] E. J. Candés and B. Recht, “Exact matrix completion via convex optimization,” *Foundations of Computational Mathematics*, vol. 9, no. 6, pp. 717–772, Dec. 2009.
[Link to Document]

[4]
E. Riegler, D. Stotz, and H. Bölcskei, “Information-theoretic limits of matrix completion,” *Proc. IEEE Int. Symp. on
Inf. Theory (ISIT)*, pp. 106–110, Jun. 2015. [Link to Document]

[5]
D. Stotz, E. Riegler, E. Agustsson, and H. Bölcskei, “Almost lossless analog signal separation and probabilistic uncertainty relations,” *IEEE Trans. Inf. Theory*, vol. 63, no. 9, pp. 5445-5460, Sep. 2017.
[Link to Document]

### Estimation of fractal dimensions (DA)

Fractal dimensions such as the box-counting dimension or the Rényi information dimension of a random vector often appear as a measure of the vector's description complexity. Recently, fractal dimensions were shown to characterize fundamental limits in information-theoretic problems such as analog data compression [2, 3] and communication over interference channels [4 - 6]. The exact computation of fractal dimensions is, in general, hard, as explicit formulae are available only for certain classes of well-behaved probability distributions.

The goal of this project is to develop, based on the results in [1], a statistical theory and corresponding algorithms for the estimation of fractal dimensions. The resulting estimation procedures shall then be used to gain insights into the fractal dimension of sources with structure relevant to information-theoretic problems.

Type of project: 60% theory, 40% simulation

Prerequisites: Strong mathematical background, measure theory, probability theory

Supervisor: Erwin Riegler

Professor:
Helmut Bölcskei

References:

[1] C. D. Cutler, “A review of the theory and estimation of fractal dimension,” in *Dimension estimation and models*, H. Tong, Ed., Nonlinear Time Series and Chaos, vol. 1, pp. 1–107, World Scientific, 1993.

[2] Y. Wu and S. Verdú, “Rényi information dimension: Fundamental limits of almost lossless analog compression,” *IEEE Trans. Inf. Theory*, vol. 56, no. 8, pp. 3721–3748, Aug. 2010. [Link to Document]

[3]
D. Stotz, E. Riegler, E. Agustsson, and H. Bölcskei, “Almost lossless analog signal separation and probabilistic uncertainty relations,” *IEEE Trans. Inf. Theory*, vol. 63, no. 9,\
pp. 5445-5460, Sep. 2017.
[Link to Document]

[4]
Y. Wu, S. Shamai (Shitz), and S. Verdú, “Information dimension and the degrees of freedom of the interference channel,” *IEEE Trans. Inf. Theory*, vol. 61, no. 1, pp. 256–279, Jan. 2015. [Link to Document]

[5]
D. Stotz and H. Bölcskei, “Degrees of freedom in vector interference channels,” *IEEE Transactions on Information Theory*, vol. 62, no. 7, pp. 4172–4197, Jul. 2016.
[Link to Document]

[6]
D. Stotz and H. Bölcskei, “Characterizing degrees of freedom through additive combinatorics,” *IEEE Transactions on Information Theory*, vol. 62, no. 11, pp. 6423–6435, Nov. 2016.
[Link to Document]

### Analyzing cost functions for generative adversarial networks (SA/DA)

Generative adversarial networks (GANs) [1] have led to remarkable results in machine learning, in particular in image generation tasks [2]. The GAN-learning problem is a two-player game between the so-called generator, who learns how to generate samples resembling the training data, and the discriminator, who learns how to discriminate between real and fake data points. Both players aim at minimizing their own cost function until a Nash-equilibrium is established.

The goal of this project is to analyze–-mathematically and possibly experimentally–-different cost functions in the context of GAN-learning for image generation tasks.

Type of project: 80%-90% theory, 10-20% simulation

Prerequisites: Analysis, linear algebra, probability theory, Python

Supervisor: Michael Tschannen

Professor:
Helmut Bölcskei

References:

[1] I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” *Proc. of Neural Information Processing Systems (NIPS), pp. 2672–2680*, 2014. [Link to Document]

[2] A. Radford, L. Metz, and S. Chintala “Unsupervised representation learning with deep convolutional generative adversarial networks,” *arXiv:1511.06434*, 2015. [Link to Document]