Search

We study the low rank regression problem $\my = M\mx + \epsilon$, where $\mx$ and $\my$ are $d_1$ and $d_2$ dimensional vectors respectively. We consider the extreme high-dimensional setting where the number of observations $n$ is less than $d_1 + d_2$. Existing algorithms are designed for settings where $n$ is typically as large as $\Rank(M)(d_1+d_2)$. This work provides an efficient algorithm which only involves two SVD, and establishes statistical guarantees on its performance. The algorithm decouples the problem by first estimating the precision matrix of the features, and then solving the matrix denoising problem. To complement the upper bound, we introduce new techniques for establishing lower bounds on the performance of any algorithm for this problem. Our preliminary experiments confirm that our algorithm often out-performs existing baselines, and is always at least competitive., Comment: 36 pages

Discovering statistical structure from links is a fundamental problem in the analysis of social networks. Choosing a misspecified model, or equivalently, an incorrect inference algorithm will result in an invalid analysis or even falsely uncover patterns that are in fact artifacts of the model. This work focuses on unifying two of the most widely used link-formation models: the stochastic blockmodel (SBM) and the small world (or latent space) model (SWM). Integrating techniques from kernel learning, spectral graph theory, and nonlinear dimensionality reduction, we develop the first statistically sound polynomial-time algorithm to discover latent patterns in sparse graphs for both models. When the network comes from an SBM, the algorithm outputs a block structure. When it is from an SWM, the algorithm outputs estimates of each node's latent position., Comment: To appear in NIPS 2017

Discriminating between correct and incorrect substrates is a core process in biology but how is energy apportioned between the conflicting demands of accuracy ($\mu$), speed ($\sigma$) and total entropy production rate ($P$)? Previous studies have focussed on biochemical networks with simple structure or relied on simplifying kinetic assumptions. Here, we use the linear framework for timescale separation to analytically examine steady-state probabilities away from thermodynamic equilibrium for networks of arbitrary complexity. We also introduce a method of scaling parameters that is inspired by Hopfield's treatment of kinetic proofreading. Scaling allows asymptotic exploration of high-dimensional parameter spaces. We identify in this way a broad class of complex networks and scalings for which the quantity $\sigma\ln(\mu)/P$ remains asymptotically finite whenever accuracy improves from equilibrium, so that $\mu_{eq}/\mu \to 0$. Scalings exist, however, even for Hopfield's original network, for which $\sigma\ln(\mu)/P$ is asymptotically infinite, illustrating the parametric complexity. Outside the asymptotic regime, numerical calculations suggest that, under more restrictive parametric assumptions, networks satisfy the bound, $\sigma\ln(\mu/\mu_{eq})/P < 1$, and we discuss the biological implications for discrimination by ribosomes and DNA polymerase. The methods introduced here may be more broadly useful for analysing complex networks that implement other forms of cellular information processing.

This undergraduate thesis is concerned with developing the tools of differential geometry and semiclassical analysis needed to understand the the quantum ergodicity theorem of Schnirelman (1974), Zelditch (1987), and Colin de Verdi\`ere (1985) and the quantum unique ergodicity conjecture of Rudnick and Sarnak (1994). The former states that, on any Riemannian manifold with negative curvature or ergodic geodesic flow, the eigenfunctions of the Laplace-Beltrami operator equidistribute in phase space with density 1. Under the same assumptions, the latter states that the eigenfunctions induce a sequence of Wigner probability measures on fibers of the Hamiltonian in phase space, and these measures converge in the weak-* topology to the uniform Liouville measure. If true, the conjecture implies that such eigenfunctions equidistribute in the high-eigenvalue limit with no exceptional "scarring" patterns. This physically means that the finest details of chaotic Hamiltonian systems can never reflect their quantum-mechanical behaviors, even in the semiclassical limit. The main contribution of this thesis is to contextualize the question of quantum ergodicity and quantum unique ergodicity in an elementary analytic and geometric framework. In addition to presenting and summarizing numerous important proofs, such as Colin de Verdi\`ere's proof of the quantum ergodicity theorem, we perform graphical simulations of certain billiard flows and expositorily discuss several themes in the study of quantum chaos., Comment: 92 pages, 6 figures