Understanding the conformation of protein-bound DNA is extremely important for biological and medical research, including improvement of drug creation and administration methods. Many protein-bound DNA conformations have been catalogued in the Protein Data Base; however the process of cataloging larger complexes can prove extremely difficult or unsuccessful. When standard lab techniques fail to determine a conformation, we turn to a branch of mathematical knot theory, tangle analysis, used in conjunction with difference topology experiments to analyze the topology of protein- bound DNA. In this talk, we will discuss these techniques and explain why topology alone is not enough. We will introduce preliminary software which can be used to determine likely DNA geometries consistent with protein-bound DNA topologies. Combining geometric and topological solutions will allow us to more accurately describe conformations for large protein-bound DNA complexes.

Mathematical knot theory is an exciting branch of topology that is relevant to physics, chemistry and biology. After a brief introduction to knot theory, we will explore several applications where computational methods play a useful role. When experimenting with knots on a computer, it is helpful to have powerful tools for the creation of initial conformations, for performing simulations on those conformations and also to compute topological and geometric properties of any resulting products. One such tool is the software KnotPlot, developed by the speaker over a period of many years. KnotPlot permits a wide range of interesting experiments to be performed. Several of these will be discussed, one important area being the tangling and untangling of DNA. Finally, we will dip into the more esoteric realm of higher dimensional knotting.

We consider two-stage risk-averse stochastic optimization problems with a stochastic ordering constraint on the recourse function. Two new characterizations of the increasing convex order relation are provided. They are based on conditional expectations and on integrated quantile functions: a counterpart of the Lorenz function. We propose two decomposition methods to solve the problems and prove their convergence. Our methods exploit the decomposition structure of the risk-neutral two-stage problems and construct successive approximations of the stochastic ordering constraints. Numerical results confirm the efficiency of the methods

We will discuss techniques for approximating a point in high-dimensional Euclidean space which is close to a known low-dimensional compact submanifold when only a compressed linear sketch of the point is available. More specifically, given a point, x, in R^D we will consider linear measurement operators, M: R^D -> R^m, which have associated nonlinear inverses, A: R^m -> R^D, so that || x - A(Mx) || is small even when m << D. Both the design of good linear operators, M, and the design of stable nonlinear inverses, A, will be discussed. More specifically, an algorithmic implementation a particular nonlinear inverse will be presented, along with related stability bounds for the approximation of manifold data.

The Johnson-Lindenstrauss (JL) Lemma states that any set of p points in high dimensional Euclidean space can be embedded into O<(δ ⁻² log(p)) dimensions, without distorting the distance between any two points by more than a factor between 1 − δ and 1 + δ . We establish a new connection between the JL Lemma and the Restricted Isometry Property (RIP), a well-known concept in the theory of sparse recovery often used for showing the success of ℓ₁-minimization.

Consider an m X N matrix satisfying the (k, δ_k)-RIP and an arbitrary set E of O(e^k) points in R^N. We show that with high probability, such a matrix with randomized column signs maps E into R^m without distorting the distance between any two points by more than a factor of 1±4δ_k. Consequently, matrices satisfying the Restricted Isometry of optimal order provide optimal Johnson-Lindenstrauss embeddings up to a logarithmic factor in N. Moreover, our results yield the best known bounds on the necessary embedding dimension m for a wide class of structured random matrices. In particular, for partial circulant, partial Fourier, and partial Hadamard matrices, our method optimizes the dependence of m on the distortion δ: We improve the recent bound m = O(δ⁻⁴ log(p) log⁴(N)) of Ailon and Liberty (2010) to m = O(δ⁻² log(p) log⁴(N)), which is optimal up to the logarithmic factors in N. Our results also have a direct application in the area of compressed sensing for redundant dictionaries.

This is joint work with Rachel Ward.

In this talk we discuss a nonconforming finite element approximation of the vibration modes of an acoustic fluid-structure interaction. Displacement variables are used for both the fluid and the solid. The numerical scheme is based on the irrotational fluid displacement formulation; hence it is free of spurious eigenmodes. The method uses weakly continuous P₁ vector fields for the fluid and classical piecewise linear elements for the solid; and it satisfies optimal order error estimates on properly graded meshes. The theoretical results are confirmed by numerical experiments.

This is joint work with Susanne Brenner, Aycil Cesmelioglu and Li-yeng Sung.

It is well known that standard Monte Carlo estimates of small probabilities are unreliable in the sense that under fixed computational effort, the relative error (i.e., the sample standard deviation divided by the sample average) is expected to become unbounded as the probability being estimated approaches zero. We consider the problem of estimating small probabilities of the Langevin stochastic differential equation in various asymptotic regimes. As an example, we consider the probability of exiting a deep potential well.

Graphical models use graphs to compactly capture stochastic dependencies amongst a collection of random variables. Inference over graphical models corresponds to finding marginal probability distributions given joint probability distributions. In general, this is computationally intractable, which has led to a quest for finding efficient approximate inference algorithms. We propose a framework for generalized inference over graphical models that can be used as a wrapper for improving the estimates of approximate inference algorithms. Instead of applying an inference algorithm to the original graph, we apply the inference algorithm to a block-graph, defined as a graph in which the nodes are non-overlapping clusters of nodes from the original graph. This results in marginal estimates of a cluster of nodes, which we further marginalize to get the marginal estimates of each node. Our proposed block-graph construction algorithm is simple, efficient, and motivated by the observation that approximate inference is more accurate on graphs with longer cycles. We present extensive numerical simulations that illustrate our block-graph framework with a variety of inference algorithms (e.g., those in the libDAI software package). These simulations show the improvements provided by our framework. More details

I will talk about the problems of denoising images corrupted by impulsive noise and blind inpainting (i.e., inpainting when the deteriorated region is unknown). Our basic approach is to model the set of patches of pixels in an image as a union of low-dimensional subspaces, corrupted by sparse but perhaps large magnitude noise. For this purpose, we develop a robust and iterative method for single subspace modeling and extend it to an iterative algorithm for modeling multiple subspaces. I will also cover the convergence for the algorithm and demonstrate state of the art performance of our method for both imaging problems.

Finding a densely connected subset of nodes in a graph is a fundamental problem in combinatorial optimization, with many practical applications. We consider the problem and of identifying the most densely connected set of k nodes of a given graph. This problem is known to be NP-hard. We propose a new convex relaxation of this problem using principal component pursuit. In the special case that the input graph contains a single dense subgraph plus noise in the form of edge additions and deletions, this relaxation is exact: the densest k-subgraph can be recovered directly from the unique optimal solution of this tractable relaxation. We provide two analyses of when the algorithm succeeds. In the first, the diversionary edges are added or deleted deterministically by an adversary. In the second, edges are placed or removed independently at random. These results can be thought of generalizations of existing recovery guarantees for the maximum clique problem. In both cases, the bounds ensuring perfect recovery match the best existing in the literature for the maximum clique problem.

In this talk, we show how alternating direction methods are used recently in sparse and low-rank optimization problems. We also show the iteration complexity bounds for two specific types of alternating direction methods, namely alternating linearizaton and multiple splitting methods. We prove that the basic versions of both methods require $O(1/eps)$ iterations to obtain an eps-optimal solution, and the accelerated versions of these methods require $O(1/\sqrt{eps})$ iterations, while the computational effort needed at each iteration is almost unchanged. To the best of our knowledge, these complexity results are the first ones of this type that have been given for splitting and alternating direction type methods. Numerical results on problems with millions of variables and constraints arising from computer vision, machine learning and image processing are reported to demonstrate the efficiency of the proposed methods.

We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The $n^{\log n}$ bound on the time complexity for the general case has not been improved over the past four decades. We demonstrate that the obstacle to efficient algorithms is the presence of abelian normal subgroups; we show this by giving a polynomial-time isomomrphism test for "semisimple groups,'' defined as groups without abelian normal subgroups (joint work L. Babai, Y. Qiao, in preparation). This concludes a project started with with L. Babai, J. A. Grochow, Y. Qiao (SODA 2011). That paper gave an $n^{\log\log n}$ algorithm for this class, and gave polynomial-time algorithms assuming boundedness of certain parameters. The key ingredients for this algorithm are: (a) an algorithm to test permutational isomorphism of permutation groups in time polynomial in the order and simply exponential in the degree; (b) the introduction of the "twisted code equivalence problem," a generalization of the classical code equivalence problem (which asks whether two sets of strings over a finite alphabet are equivalent by permuting the coordinates), by admitting a group action on the alphabet; (c) an algorithm to test twisted code equivalence; (d) a reduction of semisimple group isomorphism to permutational isomorphism of transitive permutation groups under the given time limits via twisted code equivalence.

The twisted code equivalence problem and the problem of permutational isomorphism of permutation groups are of interest in their own right. In this talk I will give the definitions of the problems that make up the overall plan, show how they fit together, and then give some details on the algorithm to test permutational isomorphism of transitive groups.

This talk is based on joint work with: Laszlo Babai (University of Chicago), Joshua A. Grochow (University of Chicago) and Youming Qiao (Tsingua University).

We study maximum likelihood estimation in Gaussian graphical models from a geometric point of view. In current applications of statistics, we are often faced with problems involving a large number of random variables, but only a small number of observations. An algebraic elimination criterion allows us to find exact lower bounds on the number of observations needed to ensure that the maximum likelihood estimator exists with probability one. This is applied to bipartite graphs and grids, leading to the first instance of a graph for which the maximum likelihood estimator exists with probability one even when the number of observations equals the treewidth of the graph.

Graphical model selection, where the goal is to estimate the graph underlying a distribution, is known to be computationally intractable in general. An important issue is to study theoretical limits on the performance of graphical model selection algorithms. In particular, given parameters of the underlying distribution, we want to find a lower bound on the number of samples required for accurate graph estimation. When deriving these theoretical bounds, it is common to treat the learning problem as a communication problem where the observations correspond to noisy messages and the decoding problem infers the graph from the observations. Current analysis of graphical model selection algorithms is limited to studying graph estimators that output a unique graph. In this paper, we consider graph estimators that output a set of graphs, leading to set-based graphical model selection (SB-GMS). This has connections to list-decoding where a decoder outputs a list of possible codewords instead of a single codeword. Our main contribution is to derive necessary conditions for accurate SB-GMS for various classes of graphical models and show reduction in the number of samples required for consistent estimation. Further, we derive necessary conditions on the cardinality of the set-based estimates given graph parameters. /p>

We analyze nonlinear stochastic optimization problems with joint probabilistic constraints using the concept of a $p$-efficient point of a probability distribution. If the problem is described by convex functions, we develop two algorithms based on first order optimality conditions and a dual approach to the problem. The algorithms yield an optimal solution for problems involving $\alpha$-concave probability distributions. For arbitrary distributions, the algorithms provide upper and lower bounds for the optimal value and nearly optimal solutions. When the problem is described by continuously differentiable non-convex functions, we describe the tangent and the normal cone to the level set of the underlying probability function. Furthermore, we formulate first order and second order conditions of optimality based on the notion of $p$-efficient points. For the case of discrete distribution functions, we developed an augmented Lagrangian method based on progressive inner approximation of the level set of the probability function by generation of $p$-efficient points. Numerical experience is provided.

Identifying clusters of similar objects in data plays a significant role in a wide range of applications such as information retrieval, pattern recognition, computational biology, and image processing. We consider as a model problem for clustering the average weight k-disjoint clique problem (WKDC), whose goal is to identify the collection of k disjoint cliques of a given weighted complete graph maximizing the sum of the average edge weights over the complete subgraphs induced by these cliques. We show that this problem can be formulated as a nonconvex quadratic maximization problem and subsequently relaxed to a semidefinite program using symmetric matrix lifting. Although the WKDC problem is NP-hard, we show that this relaxation is exact under certain assumptions on the input graph. That is, the optimal solution for the original hard combinatorial problem can be recovered directly from the solution of the relaxed problem for certain program inputs. In particular, the semidefinite relaxation is exact for input graphs corresponding to data consisting of k large, distinct clusters and a small number of outliers.

This approach also yields a semidefinite relaxation for the biclustering problem with similar recovery guarantees. Given a set of objects and a set of features exhibited by these objects, biclustering seeks to simultaneously group the objects and features according to their expression levels. We pose this problem as partitioning of a weighted complete bipartite graph such that the edge weight within the resulting bicliques is maximized. As in our analysis of the WKDC problem, we consider a nonconvex quadratic programming formulation for this problem, and relax to semidefinite programming using matrix lifting. As before, we show that the correct partition of the objects and features can be recovered from the optimal solution of the semidefinite relaxation, in the case that the input instance consists of several disjoint sets of objects exhibiting similar features.

We study a sequence of nearly critically loaded queueing networks, with time varying arrival and service rates and routing structure. The n^th network is described in terms of two independent finite state Markov processes {Xⁿ(t): t ≥ 0} and {Yⁿ(t) : t ≥ 0} which can be interpreted as the random environment in which the system is operating. The process Xⁿ changes states at a much higher rate than the typical arrival and service times in the system, while the reverse is true for Yⁿ. The variations in the routing mechanism of the network are governed by Xⁿ, whereas the arrival and service rates at various stations depend on the state process (i.e. queue length process) and both Xⁿ and Yⁿ. Denoting by Zⁿ the suitably normalized queue length process, it is shown that, under appropriate heavy traffic conditions, the pair Markov process (Zⁿ, Yⁿ) converges weakly to the Markov process (Z, Y), where Y is a finite state continuous time Markov process and the process Z is a reflected diffusion with drift and diffusion coefficients depending on (Z, Y) and the stationary distribution of Xⁿ. We also study stability properties of the limit process (Z, Y).

We formulate a convex minimization to robustly recover a subspace from a contaminated data set, partially sampled around it, and propose a fast iterative algorithm to achieve the corresponding minimum. We establish exact recovery by this minimizer, quantify the effect of noise and regularization, explain how to take advantage of a known intrinsic dimension and establish linear convergence of the iterative algorithm. We compare our method with many other algorithms for Robust PCA on synthetic and real data sets and demonstrate state-of-the-art speed and accuracy.

I will review a standard object recognition architecture, and discuss each of the components: SIFT features, sparse coding, pooling, and linear classifiers. I will then mention recent work of myself and collaborators on a fast version of this machine.

The eigenvalues of a symmetric operator play a significant role in many areas of mathematics and engineering. As such, it is important to understand the behaviour of the spectrum of a matrix under small perturbations. This talk is divided into two parts. In the first, I will review several important results from the literature regarding the sensitivity of the eigenvalues of a symmetric matrix. In particular, I will provide formulas for the directional derivatives of the spectrum of a symmetric matrix, and discuss how these formulas can be extended to obtain a series approximation of the spectrum of a symmetric matrix under small perturbations. The second half of the talk will focus on the sensitivity of functions of the spectrum of a symmetric matrix. If F(X) is a function that depends smoothly on the eigenvalues of X, I will provide conditions for when this smoothness is inherited by F. As examples, I will provide conditions for differentiability of spectral functions and primary matrix functions, as well as formulas for their gradients.