More Like this

1. Holey Substrate-Directed Strain Patterning in Bilayer MoS2

   https://doi.org/10.1021/acsnano.1c08348  

   Zhang, Yichao ; Choi, Moon-Ki ; Haugstad, Greg ; Tadmor, Ellad B. ; Flannigan, David J. ( November 2021 , ACS Nano)

   null (Ed.)

   Key properties of two-dimensional (2D) layered materials are highly strain tunable, arising from bond modulation and associated reconfiguration of the energy bands around the Fermi level. Approaches to locally controlling and patterning strain have included both active and passive elastic deformation via sustained loading and templating with nanostructures. Here, by float-capturing ultrathin flakes of single-crystal 2H-MoS₂ on amorphous holey silicon nitride substrates, we find that highly symmetric, high-fidelity strain patterns are formed. The hexagonally arranged holes and surface topography combine to generate highly conformal flake-substrate coverage creating patterns that match optimal centroidal Voronoi tessellation in 2D Euclidean space. Using TEM imaging and diffraction, as well as AFM topographic mapping, we determine that the substrate-driven 3D geometry of the flakes over the holes consists of symmetric, out-of-plane bowl-like deformation of up to 35 nm, with in-plane, isotropic tensile strains of up to 1.8% (measured with both selected-area diffraction and AFM). Atomistic and image simulations accurately predict spontaneous formation of the strain patterns, with van der Waals forces and substrate topography as the input parameters. These results show that predictable patterns and 3D topography can be spontaneously induced in 2D materials captured on bare, holey substrates. The method also enables electron scattering studies of precisely aligned, substrate-free strained regions in transmission mode. 

   more » « less
2. Balanced centroidal power diagrams for redistricting

   https://doi.org/10.1145/3274895.3274979  

   Cohen-Addad, Vincent ; Klein, Philip N. ; Young, Neal E. ( November 2018 , Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems)

   We consider the problem of political redistricting: given the locations of people in a geographical area (e.g. a US state), the goal is to decompose the area into subareas, called districts, so that the populations of the districts are as close as possible and the districts are ``compact'' and ``contiguous,'' to use the terms referred to in most US state constitutions and/or US Supreme Court rulings. We study a method that outputs a solution in which each district is the intersection of a convex polygon with the geographical area. The average number of sides per polygon is less than six. The polygons tend to be quite compact. Every two districts differ in population by at most one (so we call the solution balanced). In fact, the solution is a centroidal power diagram: each polygon has an associated center in ℝ³ such that * the projection of the center onto the plane z = 0 is the centroid of the locations of people assigned to the polygon, and * for each person assigned to that polygon, the polygon's center is closest among all centers. The polygons are convex because they are the intersections of 3D Voronoi cells with the plane. The solution is, in a well-defined sense, a locally optimal solution to the problem of choosing centers in the plane and choosing an assignment of people to those 2-d centers so as to minimize the sum of squared distances subject to the assignment being balanced. * A practical problem with this approach is that, in real-world redistricting, exact locations of people are unknown. Instead, the input consists of polygons (census blocks) and associated populations. A real redistricting must not split census blocks. We therefore propose a second phase that perturbs the solution slightly so it does not split census blocks. In our experiments, the second phase achieves this while preserving perfect population balance. The district polygons are no longer convex at the fine scale because their boundaries must follow the boundaries of census blocks, but at a coarse scale they preserve the shape of the original polygons. 

   more » « less
3. How can classical multidimensional scaling go wrong?

   Sonthalia, Rishi ; Van Buskirk, Greg ; Raichel, Benjamin ; Gilbert, Anna ( January 2021 , Advances in neural information processing systems)

   Given a matrix D describing the pairwise dissimilarities of a data set, a common task is to embed the data points into Euclidean space. The classical multidimensional scaling (cMDS) algorithm is a widespread method to do this. However, theoretical analysis of the robustness of the algorithm and an in-depth analysis of its performance on non-Euclidean metrics is lacking. In this paper, we derive a formula, based on the eigenvalues of a matrix obtained from D, for the Frobenius norm of the difference between D and the metric Dcmds returned by cMDS. This error analysis leads us to the conclusion that when the derived matrix has a significant number of negative eigenvalues, then ∥D−Dcmds∥F, after initially decreasing, willeventually increase as we increase the dimension. Hence, counterintuitively, the quality of the embedding degrades as we increase the dimension. We empirically verify that the Frobenius norm increases as we increase the dimension for a variety of non-Euclidean metrics. We also show on several benchmark datasets that this degradation in the embedding results in the classification accuracy of both simple (e.g., 1-nearest neighbor) and complex (e.g., multi-layer neural nets) classifiers decreasing as we increase the embedding dimension.Finally, our analysis leads us to a new efficiently computable algorithm that returns a matrix Dl that is at least as close to the original distances as Dt (the Euclidean metric closest in ℓ2 distance). While Dl is not metric, when given as input to cMDS instead of D, it empirically results in solutions whose distance to D does not increase when we increase the dimension and the classification accuracy degrades less than the cMDS solution. 

   more » « less
4. Nested Hyperbolic Spaces for Dimensionality Reduction and Hyperbolic NN Design

   Xiran, Fan ; Chun-Hao, Yang ; Baba, C Vemuri ( June 2022 , IEEE Computer Society)

   Hyperbolic neural networks have been popular in the re- cent past due to their ability to represent hierarchical data sets effectively and efficiently. The challenge in develop- ing these networks lies in the nonlinearity of the embed- ding space namely, the Hyperbolic space. Hyperbolic space is a homogeneous Riemannian manifold of the Lorentz group which is a semi-Riemannian manifold, i.e. a mani- fold equipped with an indefinite metric. Most existing meth- ods (with some exceptions) use local linearization to de- fine a variety of operations paralleling those used in tra- ditional deep neural networks in Euclidean spaces. In this paper, we present a novel fully hyperbolic neural network which uses the concept of projections (embeddings) fol- lowed by an intrinsic aggregation and a nonlinearity all within the hyperbolic space. The novelty here lies in the projection which is designed to project data on to a lower- dimensional embedded hyperbolic space and hence leads to a nested hyperbolic space representation independently useful for dimensionality reduction. The main theoretical contribution is that the proposed embedding is proved to be isometric and equivariant under the Lorentz transforma- tions, which are the natural isometric transformations in hyperbolic spaces. This projection is computationally effi- cient since it can be expressed by simple linear operations, and, due to the aforementioned equivariance property, it al- lows for weight sharing. The nested hyperbolic space rep- resentation is the core component of our network and there- fore, we first compare this representation – independent of the network – with other dimensionality reduction methods such as tangent PCA, principal geodesic analysis (PGA) and HoroPCA. Based on this equivariant embedding, we develop a novel fully hyperbolic graph convolutional neural network architecture to learn the parameters of the projec- tion. Finally, we present experiments demonstrating com- parative performance of our network on several publicly available data sets. 

   more » « less
5. Practical Data-Dependent Metric Compression with Provable Guarantees

   Indyk, Piotr ; Razenshteyn, Ilya P. ; Wagner, Tal ( January 2017 , Annual Conference on Neural Information Processing Systems)

   We introduce a new distance-preserving compact representation of multi-dimensional point-sets. Given n points in a d-dimensional space where each coordinate is represented using B bits (i.e., dB bits per point), it produces a representation of size O( d log(d B/epsilon) +log n) bits per point from which one can approximate the distances up to a factor of 1 + epsilon. Our algorithm almost matches the recent bound of Indyk et al, 2017} while being much simpler. We compare our algorithm to Product Quantization (PQ) (Jegou et al, 2011) a state of the art heuristic metric compression method. We evaluate both algorithms on several data sets: SIFT, MNIST, New York City taxi time series and a synthetic one-dimensional data set embedded in a high-dimensional space. Our algorithm produces representations that are comparable to or better than those produced by PQ, while having provable guarantees on its performance. 

   more » « less