Mathematics of Information
4:00-5:00 pm in Annenberg 213
(except where otherwise noted)
Not held fall 2016-17
CMI Faculty Lunches
October 13, 2016
Learning Semidefinite Regularizers via Matrix Factorization
Regularization techniques are widely employed in the solution of inverse problems in data analysis and scientific computing due to their effectiveness in addressing difficulties arising from ill-posedness. In their most common manifestation, these methods take the form of penalty functions added to the objective in optimization-based approaches for solving inverse problems. The purpose of the penalty function is to induce a desired structure in the solution, and these functions are specified based on prior domain-specific expertise. We consider the problem of learning suitable regularization functions from data in settings in which precise domain knowledge is not directly available. Previous work under the title of 'dictionary learning' or 'sparse coding' may be viewed as learning a regularization function that can be computed via linear programming. We describe generalizations of these methods to learn regularizers that can be computed and optimized via semidefinite programming. Our approach for learning such semidefinite regularizers is based on computing structured factorizations of data matrices, and our algorithmic approach for computing these factorizations combines recent techniques for rank minimization problems along with operator analogs of Sinkhorn scaling. The regularizers obtained using our framework can be employed effectively in semidefinite programming relaxations for solving inverse problems. (Joint work with Yong Sheng Soh.)
November 10, 2016
Universal laws and architectures: brains, bugs, guts, hearts, nets, grids, and zombies
We'll do some live demos to motivate new math explaining the extremes of human sensorimotor control, the laws and physiology that constrain it, and the architectures needed to achieve what remains possible. Time permitting we'll see how the same laws and architectures are universal in highly evolvable systems from bacterial cells to the Internet, and what tragic side effects so far seem unavoidable. There are lots of videos online, with links from http://www.cds.caltech.edu/~doyle
December 8, 2016
I will discuss recent work on the problem of testing quantum devices. We focus on the basic problem of testing dimension.
An ideal system of n qubits has 2^n dimensions, and this exponential scaling grants quantum computers their power. In a real system, however, the qubits will not be perfect. They can "overlap," in the sense that an operation on one qubit might slightly affect the others. We show that, allowing for slight overlaps, n qubits can fit in just polynomially many dimensions. (Defined in a natural way, all pairwise overlaps can be at most epsilon in n^O(1/\epsilon^2) dimensions.) Our results show that real systems with only apparently small imperfections could have much less power than one would have expected.
On the other hand, we also provide an efficient test to certify exponential dimensionality. Unfortunately, the test is sensitive to noise. It is important to devise more robust tests on the arrangements of qubits in quantum devices.
Joint work with Rui Chao, Chris Sutherland, and Ben Reichardt.
February 9, 2017
Sketchy decisions: Low-rank matrix optimization with optimal storage
Convex matrix optimization problems with low-rank solutions play a fundamental role in signal processing, statistics, and related disciplines. These problems are difficult to solve because of the cost of maintaining the matrix decision variable, even though the low-rank solution has few degrees of freedom. This talk presents the first algorithm that provably solves these problems using optimal storage. The algorithm produces high-quality solutions to large problem instances that, previously, were intractable.
Joint with Volkan Cevher, Roarke Horstmeyer, Quoc Tran-Dinh, Madeleine Udell, and Alp Yurtsever.
March 9, 2017
April 13, 2017
May 11, 2017