Wednesday, 13 June

Abstract:
We consider basic questions in information and communication theory on the value of randomness as a resource. We start with Shannon´s problem of transmission of messages over noisy channels. Shannon’s famous solution of this problem was one of the starting points of our information society. Shannon used deterministic encoding and decoding of messages. It is clear that randomized encoding and decoding cannot increase the Shannon capacity for message transmission over noisy channels. Even if we use common randomness between the transmitter and receiver, it is not possible to increase the Shannon capacity for message transmission. As a next step, we consider the problem of secure message transmission of wiretap channels. In this case we discuss that it is already necessary to use local randomness at the transmitter to achieve the capacity for secure message transmission. We further discuss the problem of message transmission and secure message transmission of noisy channels with jammers. For these type of channels, local randomness at the transmitter is a very important resource that increases the capacity and stabilizes the communication from the transmitter to the receiver. In the second part of the talk we will introduce the communication task of identification. In the identification task, the receiver is interested in testing whether a specific message has been transmitted. The transmitter has no idea which message is interesting to the receiver. The identification task is very important for new applications, e.g. car to car, car to infrastructure, sensor networks, and for the tactile internet. If we only use deterministic encoding and decoding, then the capacity for identification over noisy channels is equal to the Shannon capacity for message transmission. So the number of messages that the receiver can identify grows exponentially with the block length. The situation changes dramatically if we can use local randomness at the transmitter. In this case we will show that the number of messages that the receiver can correctly identify grows doubly exponentially. We will show that the same is true for the secure identification task. We will extend this to the identification of noisy channels with a jammer. Here additional gains can be achieved by using a common randomness transmitter and receiver. We will further discuss storage of data and secure storage of private data on public databases. At the end of the talk we will discuss applications for big data.

This is joint work with Christian Deppe from TU Munich-LNT.

Abstract:
We consider the question of estimating a solution to a system of equations that involve convex nonlinearities, a problem that is common in machine learning and signal processing. Because of these nonlinearities, conventional estimators based on empirical risk minimization generally involve solving a non-convex optimization program. We propose a method (called “anchored regression”) that is based on convex programming and amounts to maximizing a linear functional (perhaps augmented by a regularizer) over a convex set. 

The proposed convex program is formulated in the natural space of the problem, and avoids the introduction of auxiliary variables, making it computationally favorable. Working in the native space also provides us with the flexibility to incorporate structural priors (e.g., sparsity) on the solution.

For our analysis, we model the equations as being drawn from a fixed set according to a probability law.  Our main results provide guarantees on the accuracy of the estimator in terms of the number of equations we are solving, the amount of noise present, a measure of statistical complexity of the random equations, and the geometry of the regularizer at the true solution. We also provide recipes for constructing the anchor vector (that determines the linear functional to maximize) directly from the observed data.

We will discuss applications of this technique to nonlinear problems including phase retrieval, blind deconvolution, and inverting the action of a neural network.

This is joint work with Sohail Bahmani.