• We present a mathematical analysis of a non-convex energy landscape for robust subspace recovery. We prove that an underlying subspace is the only stationary point and local minimizer in a specified neighborhood under a deterministic condition on a dataset. If the deterministic condition is satisfied, we further show that a geodesic gradient descent method over the Grassmannian manifold can exactly recover the underlying subspace when the method is properly initialized. Proper initialization by principal component analysis is guaranteed with a simple deterministic condition. Under slightly stronger assumptions, the gradient descent method with a piecewise constant step-size scheme achieves linear convergence. The practicality of the deterministic condition is demonstrated on some statistical models of data, and the method achieves almost state-of-the-art recovery guarantees on the Haystack Model for different regimes of sample size and ambient dimension. In particular, when the ambient dimension is fixed and the sample size is large enough, we show that our gradient method can exactly recover the underlying subspace for any fixed fraction of outliers (less than 1).
  • This note proves the following inequality: if $n=3k$ for some positive integer $k$, then for any $n$ positive definite matrices $A_1,A_2,\cdots,A_n$, \begin{equation} \frac{1}{n^3}\Big\|\sum_{j_1,j_2,j_3=1}^{n}A_{j_1}A_{j_2}A_{j_3}\Big\| \geq \frac{(n-3)!}{n!} \Big\|\sum_{\substack{j_1,j_2,j_3=1,\\\text{$j_1$, $j_2$, $j_3$ all distinct}}}^{n}A_{j_1}A_{j_2}A_{j_3}\Big\|, \end{equation} where $\|\cdot\|$ represents the operator norm. This inequality is a special case of a recent conjecture by Recht and R\'e.
  • This paper considers the problem of phase retrieval, where the goal is to recover a signal $z\in C^n$ from the observations $y_i=|a_i^* z|$, $i=1,2,\cdots,m$. While many algorithms have been proposed, the alternating minimization algorithm has been one of the most commonly used methods, and it is very simple to implement. Current work has proved that when the observation vectors $\{a_i\}_{i=1}^m$ are sampled from a complex Gaussian distribution $N(0, I)$, it recovers the underlying signal with a good initialization when $m=O(n)$, or with random initialization when $m=O(n^2)$, and it conjectured that random initialization succeeds with $m=O(n)$. This work proposes a modified alternating minimization method in a batch setting, and proves that when $m=O(n\log^{3}n)$, the proposed algorithm with random initialization recovers the underlying signal with high probability. The proof is based on the observation that after each iteration of alternating minimization, with high probability, the angle between the estimated signal and the underlying signal is reduced.
  • We establish exact recovery for the Least Unsquared Deviations (LUD) algorithm of Ozyesil and Singer. More precisely, we show that for sufficiently many cameras with given corrupted pairwise directions, where both camera locations and pairwise directions are generated by a special probabilistic model, the LUD algorithm exactly recovers the camera locations with high probability. A similar exact recovery guarantee was established for the ShapeFit algorithm by Hand, Lee and Voroninski, but with typically less corruption.
  • Thin sheets can exhibit nonlinear behaviors while the material response is purely linear. We separate two distinct mechanisms for geometric nonlinearities by studying the normal-force response of an indented polymer film floating on a liquid bath, using experiments, simulations, and theory. The first mechanism is due to the nonlinear relation between deflection and strain in slender bodies, which occurs even in Hookean solids. This causes the system to stiffen out of the typical linear response for small deflections, and it underlies a wrinkling instability. When wrinkles cover the sheet, the force is again linear with displacement, yet the mechanical properties of the film are irrelevant. A second nonlinearity causes the response to soften when the film reaches large slopes.
  • Genome-wide eQTL mapping explores the relationship between gene expression values and DNA variants to understand genetic causes of human disease. Due to the large number of genes and DNA variants that need to be assessed simultaneously, current methods for eQTL mapping often suffer from low detection power, especially for identifying trans-eQTLs. In this paper, we propose a new method that utilizes advanced techniques in large-scale signal detection to pursue the structure of eQTL data and improve the power for eQTL mapping. The new method greatly reduces the burden of joint modeling by developing a new ranking and screening strategy based on the higher criticism statistic. Numerical results in simulation studies demonstrate the superior performance of our method in detecting true eQTLs with reduced computational expense. The proposed method is also evaluated in HapMap eQTL data analysis and the results are compared to a database of known eQTLs.
  • This work tackles the automatic fine-grained slide quality assessment problem for digitized direct smears test using the Gram staining protocol. Automatic quality assessment can provide useful information for the pathologists and the whole digital pathology workflow. For instance, if the system found a slide to have a low staining quality, it could send a request to the automatic slide preparation system to remake the slide. If the system detects severe damage in the slides, it could notify the experts that manual microscope reading may be required. In order to address the quality assessment problem, we propose a deep neural network based framework to automatically assess the slide quality in a semantic way. Specifically, the first step of our framework is to perform dense fine-grained region classification on the whole slide and calculate the region distribution histogram. Next, our framework will generate assessments of the slide quality from various perspectives: staining quality, information density, damage level and which regions are more valuable for subsequent high-magnification analysis. To make the information more accessible, we present our results in the form of a heat map and text summaries. Additionally, in order to stimulate research in this direction, we propose a novel dataset for slide quality assessment. Experiments show that the proposed framework outperforms recent related works.
  • Topological defects (e.g. pentagons, heptagons and pentagon-heptagon pairs) have been widely observed in large scale graphene and have been recognized to play important roles in tailoring the mechanical and physical properties of two-dimensional materials in general. Thanks to intensive studies over the past few years, optimizing properties of graphene through topological design has become a new and promising direction of research. In this chapter, we review some of the recent advances in experimental, computational and theoretical studies on the effects of topological defects on mechanical and physical properties of graphene and applications of topologically designed graphene. The discussions cover out-of-plane effects, inverse problems of designing distributions of topological defects that make a graphene sheet conform to a targeted three-dimensional surface, grain boundary engineering for graphene strength, curved graphene for toughness enhancement and applications in engineering energy materials, multifunctional materials and interactions with biological systems. Despite the rapid developments in experiments and simulations, our understanding on the relations between topological defects and mechanical and physical properties of graphene and other 2D materials is still in its infancy. The intention here is to draw the attention of the research community to some of the open questions in this field.
  • We explore ways to use the ability to measure the populations of individual magnetic sublevels to improve the sensitivity of magnetic field measurements and measurements of atomic electric dipole moments (EDMs). When atoms are initialized in the $m=0$ magnetic sublevel, the shot-noise-limited uncertainty of these measurements is $1/\sqrt{2F(F+1)}$ smaller than that of a Larmor precession measurement. When the populations in the even (or odd) magnetic sublevels are combined, we show that these measurements are independent of the tensor Stark shift and the second order Zeeman shift. We discuss the complicating effect of a transverse magnetic field and show that when the ratio of the tensor Stark shift to the transverse magnetic field is sufficiently large, an EDM measurement with atoms initialized in the superposition of the stretched states can reach the optimal sensitivity.
  • Word embedding is a useful approach to capture co-occurrence structures in a large corpus of text. In addition to the text data itself, we often have additional covariates associated with individual documents in the corpus---e.g. the demographic of the author, time and venue of publication, etc.---and we would like the embedding to naturally capture the information of the covariates. In this paper, we propose CoVeR, a new tensor decomposition model for vector embeddings with covariates. CoVeR jointly learns a base embedding for all the words as well as a weighted diagonal transformation to model how each covariate modifies the base embedding. To obtain the specific embedding for a particular author or venue, for example, we can then simply multiply the base embedding by the transformation matrix associated with that time or venue. The main advantages of our approach is data efficiency and interpretability of the covariate transformation matrix. Our experiments demonstrate that our joint model learns substantially better embeddings conditioned on each covariate compared to the standard approach of learning a separate embedding for each covariate using only the relevant subset of data, as well as other related methods. Furthermore, CoVeR encourages the embeddings to be "topic-aligned" in the sense that the dimensions have specific independent meanings. This allows our covariate-specific embeddings to be compared by topic, enabling downstream differential analysis. We empirically evaluate the benefits of our algorithm on several datasets, and demonstrate how it can be used to address many natural questions about the effects of covariates.
  • We consider a wide range of regularized stochastic minimization problems with two regularization terms, one of which is composed with a linear function. This optimization model abstracts a number of important applications in artificial intelligence and machine learning, such as fused Lasso, fused logistic regression, and a class of graph-guided regularized minimization. The computational challenges of this model are in two folds. On one hand, the closed-form solution of the proximal mapping associated with the composed regularization term or the expected objective function is not available. On the other hand, the calculation of the full gradient of the expectation in the objective is very expensive when the number of input data samples is considerably large. To address these issues, we propose a stochastic variant of extra-gradient type methods, namely \textsf{Stochastic Primal-Dual Proximal ExtraGradient descent (SPDPEG)}, and analyze its convergence property for both convex and strongly convex objectives. For general convex objectives, the uniformly average iterates generated by \textsf{SPDPEG} converge in expectation with $O(1/\sqrt{t})$ rate. While for strongly convex objectives, the uniformly and non-uniformly average iterates generated by \textsf{SPDPEG} converge with $O(\log(t)/t)$ and $O(1/t)$ rates, respectively. The order of the rate of the proposed algorithm is known to match the best convergence rate for first-order stochastic algorithms. Experiments on fused logistic regression and graph-guided regularized logistic regression problems show that the proposed algorithm performs very efficiently and consistently outperforms other competing algorithms.
  • Low mass suspension systems with high-Q pendulum stages are used to enable quantum radiation pressure noise limited experiments. Utilising multiple pendulum stages with vertical blade springs and materials with high quality factors provides attenuation of seismic and thermal noise, however damping of these high-Q pendulum systems in multiple degrees of freedom is essential for practical implementation. Viscous damping such as eddy-current damping can be employed but introduces displacement noise from force noise due to thermal fluctuations in the damping system. In this paper we demonstrate a passive damping system with adjustable damping strength as a solution for this problem that can be used for low mass suspension systems without adding additional displacement noise in science mode. We show a reduction of the damping factor by a factor of 8 on a test suspension and provide a general optimisation for this system.
  • Robust PCA is a widely used statistical procedure to recover a underlying low-rank matrix with grossly corrupted observations. This work considers the problem of robust PCA as a nonconvex optimization problem on the manifold of low-rank matrices, and proposes two algorithms (for two versions of retractions) based on manifold optimization. It is shown that, with a proper designed initialization, the proposed algorithms are guaranteed to converge to the underlying low-rank matrix linearly. Compared with a previous work based on the Burer-Monterio decomposition of low-rank matrices, the proposed algorithms reduce the dependence on the conditional number of the underlying low-rank matrix theoretically. Simulations and real data examples confirm the competitive performance of our method.
  • The discrete moment problem is a foundational problem in distribution-free robust optimization, where the goal is to find a worst-case distribution that satisfies a given set of moments. This paper studies the discrete moment problems with additional "shape constraints" that guarantee the worst case distribution is either log-concave or has an increasing failure rate. These classes of shape constraints have not previously been studied in the literature, in part due to their inherent nonconvexities. Nonetheless, these classes of distributions are useful in practice. We characterize the structure of optimal extreme point distributions by developing new results in reverse convex optimization, a lesser-known tool previously employed in designing global optimization algorithms. We are able to show, for example, that an optimal extreme point solution to a moment problem with $m$ moments and log-concave shape constraints is piecewise geometric with at most $m$ pieces. Moreover, this structure allows us to design an exact algorithm for computing optimal solutions in a low-dimensional space of parameters. Moreover, We describe a computational approach to solving these low-dimensional problems, including numerical results for a representative set of instances.
  • This article describes the final solution of team monkeytyping, who finished in second place in the YouTube-8M video understanding challenge. The dataset used in this challenge is a large-scale benchmark for multi-label video classification. We extend the work in [1] and propose several improvements for frame sequence modeling. We propose a network structure called Chaining that can better capture the interactions between labels. Also, we report our approaches in dealing with multi-scale information and attention pooling. In addition, We find that using the output of model ensemble as a side target in training can boost single model performance. We report our experiments in bagging, boosting, cascade, and stacking, and propose a stacking algorithm called attention weighted stacking. Our final submission is an ensemble that consists of 74 sub models, all of which are listed in the appendix.
  • In the present paper, we studied a Dynamic Stochastic Block Model (DSBM) under the assumptions that the connection probabilities, as functions of time, are smooth and that at most $s$ nodes can switch their class memberships between two consecutive time points. We estimate the edge probability tensor by a kernel-type procedure and extract the group memberships of the nodes by spectral clustering. The procedure is computationally viable, adaptive to the unknown smoothness of the functional connection probabilities, to the rate $s$ of membership switching and to the unknown number of clusters. In addition, it is accompanied by non-asymptotic guarantees for the precision of estimation and clustering.
  • The missing phase problem in X-ray crystallography is commonly solved using the technique of molecular replacement, which borrows phases from a previously solved homologous structure, and appends them to the measured Fourier magnitudes of the diffraction patterns of the unknown structure. More recently, molecular replacement has been proposed for solving the missing orthogonal matrices problem arising in Kam's autocorrelation analysis for single particle reconstruction using X-ray free electron lasers and cryo-EM. In classical molecular replacement, it is common to estimate the magnitudes of the unknown structure as twice the measured magnitudes minus the magnitudes of the homologous structure, a procedure known as `twicing'. Mathematically, this is equivalent to finding an unbiased estimator for a complex-valued scalar. We generalize this scheme for the case of estimating real or complex valued matrices arising in single particle autocorrelation analysis. We name this approach "Anisotropic Twicing" because unlike the scalar case, the unbiased estimator is not obtained by a simple magnitude isotropic correction. We compare the performance of the least squares, twicing and anisotropic twicing estimators on synthetic and experimental datasets. We demonstrate 3D homology modeling in cryo-EM directly from experimental data without iterative refinement or class averaging, for the first time.
  • Motivated by a certain molecular reconstruction methodology in cryo-electron microscopy, we consider the problem of solving a linear system with two unknown orthogonal matrices, which is a generalization of the well-known orthogonal Procrustes problem. We propose an algorithm based on a semi-definite programming (SDP) relaxation, and give a theoretical guarantee for its performance. Both theoretically and empirically, the proposed algorithm performs better than the na\"{i}ve approach of solving the linear system directly without the orthogonal constraints. We also consider the generalization to linear systems with more than two unknown orthogonal matrices.
  • The main contribution of this paper is an invariant extended Kalman filter (EKF) for visual inertial navigation systems (VINS). It is demonstrated that the conventional EKF based VINS is not invariant under the stochastic unobservable transformation, associated with translations and a rotation about the gravitational direction. This can lead to inconsistent state estimates as the estimator does not obey a fundamental property of the physical system. To address this issue, we use a novel uncertainty representation to derive a Right Invariant error extended Kalman filter (RIEKF-VINS) that preserves this invariance property. RIEKF-VINS is then adapted to the multistate constraint Kalman filter framework to obtain a consistent state estimator. Both Monte Carlo simulations and real-world experiments are used to validate the proposed method.
  • In this paper, we investigate the convergence and consistency properties of an Invariant-Extended Kalman Filter (RI-EKF) based Simultaneous Localization and Mapping (SLAM) algorithm. Basic convergence properties of this algorithm are proven. These proofs do not require the restrictive assumption that the Jacobians of the motion and observation models need to be evaluated at the ground truth. It is also shown that the output of RI-EKF is invariant under any stochastic rigid body transformation in contrast to $\mathbb{SO}(3)$ based EKF SLAM algorithm ($\mathbb{SO}(3)$-EKF) that is only invariant under deterministic rigid body transformation. Implications of these invariance properties on the consistency of the estimator are also discussed. Monte Carlo simulation results demonstrate that RI-EKF outperforms $\mathbb{SO}(3)$-EKF, Robocentric-EKF and the "First Estimates Jacobian" EKF, for 3D point feature based SLAM.
  • With the recent discovery of Gravitational waves, marking the start of the new field of GW astronomy, the push for building more sensitive laser-interferometric gravitational wave detectors (GWD) has never been stronger. Balanced homodyne detection (BHD) allows for a quantum noise limited readout of arbitrary light field quadratures, and has therefore been suggested as a vital building block for upgrades to Advanced LIGO and third generation observatories. In terms of the practical implementation of BHD, we develop a full framework for analyzing the static optical high order modes (HOMs) occurring in the BHD paths related to the misalignment or mode matching at the input and output ports of the laser interferometer. We find the effects of HOMs on the quantum noise limited sensitivity is independent of the actual interferometer configuration, e.g. Michelson and Sagnac interferometers are effected in the same way. We show that output misalignment only effects the high frequency part of the quantum noise limited sensitivity. However, at low frequencies, HOMs reduce the interferometer response and the radiation pressure noise by the same amount and hence the quantum noise limited sensitivity is not negatively effected. We show that the input misalignment to the interferometer produces the same effect as output misalignment and additionally decreases the power inside the interferometer. We also analyze dynamic HOM effects, such as beam jitter created by the suspended mirrors of the BHD. Our analyses can be directly applied to any BHD implementation in a future GWD. Moreover, we apply our analytical techniques to the example of the speed meter proof of concept experiment under construction in Glasgow. We find that for our experimental parameters, the performance of our seismic isolation system in the BHD paths is compatible with the design sensitivity of the experiment.
  • An algorithm for computing the Karcher mean of $n$ positive definite matrices is proposed, based on the majorization-minimization (MM) principle. The proposed MM algorithm is parameter-free, does not need to choose step sizes, and has a theoretical guarantee of asymptotic linear convergence.
  • Since the first successful synthesis of graphene just over a decade ago, a variety of two-dimensional (2D) materials (e.g., transition metal-dichalcogenides, hexagonal boron-nitride, etc.) have been discovered. Among the many unique and attractive properties of 2D materials, mechanical properties play important roles in manufacturing, integration and performance for their potential applications. Mechanics is indispensable in the study of mechanical properties, both experimentally and theoretically. The coupling between the mechanical and other physical properties (thermal, electronic, optical) is also of great interest in exploring novel applications, where mechanics has to be combined with condensed matter physics to establish a scalable theoretical framework. Moreover, mechanical interactions between 2D materials and various substrate materials are essential for integrated device applications of 2D materials, for which the mechanics of interfaces (adhesion and friction) has to be developed for the 2D materials. Here we review recent theoretical and experimental works related to mechanics and mechanical properties of 2D materials. While graphene is the most studied 2D material to date, we expect continual growth of interest in the mechanics of other 2D materials beyond graphene.
  • Pre-deployment verification of software components with respect to behavioral specifications in the assume-guarantee form does not, in general, guarantee absence of errors at run time. This is because assumptions about the environment cannot be discharged until the environment is fixed. An intuitive approach is to complement pre-deployment verification of guarantees, up to the assumptions, with post-deployment monitoring of environment behavior to check that the assumptions are satisfied at run time. Such a monitor is typically implemented by instrumenting the application code of the component. An additional challenge for the monitoring step is that environment behaviors are typically obtained through an I/O library, which may alter the component's view of the input format. This transformation requires us to introduce a second pre-deployment verification step to ensure that alarms raised by the monitor would indeed correspond to violations of the environment assumptions. In this paper, we describe an approach for constructing monitors and verifying them against the component assumption. We also discuss limitations of instrumentation-based monitoring and potential ways to overcome it.
  • This paper considers the problem of robust subspace recovery: given a set of $N$ points in $\mathbb{R}^D$, if many lie in a $d$-dimensional subspace, then can we recover the underlying subspace? We show that Tyler's M-estimator can be used to recover the underlying subspace, if the percentage of the inliers is larger than $d/D$ and the data points lie in general position. Empirically, Tyler's M-estimator compares favorably with other convex subspace recovery algorithms in both simulations and experiments on real data sets.