Georgia Institute of Technology College of Sciences

Motivated by the Dikin walk, we develop aspects of an interior-point

theory for sampling in high dimensions. Specifically, we introduce symmetric

and strong self-concordance. These properties imply that the corresponding

Dikin walk mixes in $\tilde{O}(n\bar{\nu})$ steps from a warm start

in a convex body in $\mathbb{R}^{n}$ using a strongly self-concordant barrier

with symmetric self-concordance parameter $\bar{\nu}$. For many natural

barriers, $\bar{\nu}$ is roughly bounded by $\nu$, the standard

self-concordance parameter. We show that this property and strong

self-concordance hold for the Lee-Sidford barrier. As a consequence,

we obtain the first walk to mix in $\tilde{O}(n^{2})$ steps for an

arbitrary polytope in $\mathbb{R}^{n}$. Strong self-concordance for other

barriers leads to an interesting (and unexpected) connection ---

for the universal and entropic barriers, it is implied by the KLS

conjecture.

We provide a martingale proof of the fact that the number of descents in random permutations is asymptotically normal with an error bound of order n^{-1/2}. The same techniques are shown to be applicable to other descent and descent-related statistics as they satisfy certain recurrence relation conditions. These statistics include inversions, descents in signed permutations, descents in Stirling permutations, the length of the longest alternating subsequences, descents in matchings and two-sided Eulerian numbers.

Geometric mechanics describes Lagrangian and Hamiltonian mechanics geometrically, and information geometry formulates statistical estimation, inference, and machine learning in terms of geometry. A divergence function is an asymmetric distance between two probability densities that induces differential geometric structures and yields efficient machine learning algorithms that minimize the duality gap. The connection between information geometry and geometric mechanics will yield a unified treatment of machine learning and structure-preserving discretizations. In particular, the divergence function of information geometry can be viewed as a discrete Lagrangian, which is a generating function of a symplectic map, that arise in discrete variational mechanics. This identification allows the methods of backward error analysis to be applied, and the symplectic map generated by a divergence function can be associated with the exact time-$h$ flow map of a Hamiltonian system on the space of probability distributions.

 The problem of phase retrieval for a set of functions $H$ can be thought of as being able to identify a function $f\in H$ or $-f\in H$ from the absolute value $|f|$.  Phase retrieval for a set of functions is called stable if when $|f|$ and $|g|$ are close then $f$ is proportionally close to $g$ or $-g$.  That is, we say that a set $H\subseteq L_2({\mathbb R})$ does stable phase retrieval if there exists a constant $C>0$ so that
$$\min\big(\big\|f-g\big\|_{L_2({\mathbb R})},\big\|f+g\big\|_{L_2({\mathbb R})}\big)\leq C \big\| |f|-|g| \big\|_{L_2({\mathbb R})} \qquad\textrm{ for all }f,g\in H.
$$
 It is known that phase retrieval for finite dimensional spaces is always stable.  On the other hand, phase retrieval for infinite dimensional spaces using a frame or a continuous frame is always unstable.  We prove that there exist infinite dimensional subspaces of $L_2({\mathbb R})$ which do stable phase retrieval.  This is joint work with Robert Calderbank, Ingrid Daubechies, and Nikki Freeman.