Search

It is well known that any positive matrix can be scaled to have prescribed row and column sums by multiplying its rows and columns by certain positive scaling factors (which are unique up to a positive scalar). This procedure is known as matrix scaling, and has found numerous applications in operations research, economics, image processing, and machine learning. In this work, we investigate the behavior of the scaling factors and the resulting scaled matrix when the matrix to be scaled is random. Specifically, letting $\widetilde{A}\in\mathbb{R}^{M\times N}$ be a positive and bounded random matrix whose entries assume a certain type of independence, we provide a concentration inequality for the scaling factors of $\widetilde{A}$ around those of $A = \mathbb{E}[\widetilde{A}]$. This result is employed to bound the convergence rate of the scaling factors of $\widetilde{A}$ to those of $A$, as well as the concentration of the scaled version of $\widetilde{A}$ around the scaled version of $A$ in operator norm, as $M,N\rightarrow\infty$. When the entries of $\widetilde{A}$ are independent, $M=N$, and all prescribed row and column sums are $1$ (i.e., doubly-stochastic matrix scaling), both of the previously-mentioned bounds are $\mathcal{O}(\sqrt{\log N / N})$ with high probability. We demonstrate our results in several simulations.

Stochastic service network designs with uncertain demand represented by a set of scenarios can be modelled as a large-scale two-stage stochastic mixed-integer program (SMIP). The progressive hedging algorithm (PHA) is a decomposition method for solving the resulting SMIP. The computational performance of the PHA can be greatly enhanced by decomposing according to scenario bundles instead of individual scenarios. At the heart of bundle-based decomposition is the method for grouping the scenarios into bundles. In this paper, we present a fuzzy c-means-based scenario bundling method to address this problem. Rather than full membership of a bundle, which is typically the case in existing scenario bundling strategies such as k-means, a scenario has partial membership in each of the bundles and can be assigned to more than one bundle in our method., Comment: 2017 IEEE Symposium on Computational Intelligence (IEEE-SSCI 2017)

Rejecting the null hypothesis in two-sample testing is a fundamental tool for scientific discovery. Yet, aside from concluding that two samples do not come from the same probability distribution, it is often of interest to characterize how the two distributions differ. Given samples from two densities $f_1$ and $f_0$, we consider the task of localizing occurrences of the inequality $f_1 > f_0$. To avoid the challenges associated with high-dimensional space, we propose a general hypothesis testing framework where hypotheses are formulated adaptively to the data by conditioning on the combined sample from the two densities. We then investigate a special case of this framework where the notion of locality is captured by a random walk on a weighted graph constructed over this combined sample. We derive a tractable testing procedure for this case employing a type of scan statistic, and provide non-asymptotic lower bounds on the power and accuracy of our test to detect whether $f_1>f_0$ in a local sense. Furthermore, we characterize the test's consistency according to a certain problem-hardness parameter, and show that our test achieves the minimax detection rate for this parameter. We conduct numerical experiments to validate our method, and demonstrate our approach on two real-world applications: detecting and localizing arsenic well contamination across the United States, and analyzing two-sample single-cell RNA sequencing data from melanoma patients.

Microbially induced calcite precipitation (MICP) is a new and sustainable technology which utilizes biochemical processes to create barriers by calcium carbonate cementation; therefore, this technology has a potential to be used for sealing leakage zones in geological formations. The complexity of current MICP models and present computer power limit the size of numerical simulations. We describe a mathematical model for MICP suitable for field-scale studies. The main mechanisms in the conceptual model are as follow: suspended microbes attach themselves to the pore walls to form biofilm, growth solution is added to stimulate the biofilm development, the biofilm uses cementation solution for production of calcite, and the calcite reduces the pore space which in turn decreases the rock permeability. We apply the model to study the MICP technology in two sets of reservoir properties including a well-established field-scale benchmark system for CO$_2$ leakage. A two-phase flow model for CO$_2$ and water is used to assess the leakage prior to and with MICP treatment. Based on the numerical results, this study confirms the potential for this technology to seal leakage paths in reservoir-caprock systems.

Hardware efficient transpilation of quantum circuits to a quantum devices native gateset is essential for the execution of quantum algorithms on noisy quantum computers. Typical quantum devices utilize a gateset with a single two-qubit Clifford entangling gate per pair of coupled qubits, however, in some applications access to a non-Clifford two-qubit gate can result in more optimal circuit decompositions and also allows more flexibility in optimizing over noise. We demonstrate calibration of a low error non-Clifford Controlled-$\frac{\pi}{2}$ phase (CS) gate on a cloud based IBM Quantum computing using the Qiskit Pulse framework. To measure the gate error of the calibrated CS gate we perform non-Clifford CNOT-Dihedral interleaved randomized benchmarking. We are able to obtain a gate error of $5.9(7) \times 10^{-3}$ at a gate length 263 ns, which is close to the coherence limit of the associated qubits, and lower error than the backends standard calibrated CNOT gate., Comment: 9 pages, 4 figures, references are updated, QPT curve in the Fig. 2 is updated based on new analysis procedure detailed in Appendix B. Conclusions unchanged

A fundamental step in many data-analysis techniques is the construction of an affinity matrix describing similarities between data points. When the data points reside in Euclidean space, a widespread approach is to from an affinity matrix by the Gaussian kernel with pairwise distances, and to follow with a certain normalization (e.g. the row-stochastic normalization or its symmetric variant). We demonstrate that the doubly-stochastic normalization of the Gaussian kernel with zero main diagonal (i.e., no self loops) is robust to heteroskedastic noise. That is, the doubly-stochastic normalization is advantageous in that it automatically accounts for observations with different noise variances. Specifically, we prove that in a suitable high-dimensional setting where heteroskedastic noise does not concentrate too much in any particular direction in space, the resulting (doubly-stochastic) noisy affinity matrix converges to its clean counterpart with rate $m^{-1/2}$, where $m$ is the ambient dimension. We demonstrate this result numerically, and show that in contrast, the popular row-stochastic and symmetric normalizations behave unfavorably under heteroskedastic noise. Furthermore, we provide examples of simulated and experimental single-cell RNA sequence data with intrinsic heteroskedasticity, where the advantage of the doubly-stochastic normalization for exploratory analysis is evident.

Alloys expand or contract as concentrations change, and the resulting relationship between atomic volume and alloy content is an important property of the solid. While a well-known approximation posits that the atomic volume varies linearly with concentration (Zen`s law), the actual variation is more complicated. Here we use an apparent size of the solute (solvent) atom and the elasticity to derive explicit analytical expressions for the atomic volume of binary solid alloys. Two approximations, continuum and terminal, are proposed. Deviations from Zen`s law are studied for 22 binary alloy systems.

We theoretically analyse the equation of topological solitons in a chain of particles interacting via a repulsive power-law potential and confined by a periodic lattice. Starting from the discrete model, we perform a gradient expansion and obtain the kink equation in the continuum limit for a power law exponent $n \ge 1$. The power-law interaction modifies the sine-Gordon equation, giving rise to a rescaling of the coefficient multiplying the second derivative (the kink width) and to an additional integral term. We argue that the integral term does not affect the local properties of the kink, but it governs the behaviour at the asymptotics. The kink behaviour at the center is dominated by a sine-Gordon equation and its width tends to increase with the power law exponent. When the interaction is the Coulomb repulsion, in particular, the kink width depends logarithmically on the chain size. We define an appropriate thermodynamic limit and compare our results with existing studies performed for infinite chains. Our formalism allows one to systematically take into account the finite-size effects and also slowly varying external potentials, such as for instance the curvature in an ion trap., Comment: 7 pages, 3 figures; typos corrected; abstract replaced with the one of the published version; version published in the special issue "Many Body Quantum Chaos" of Condensed Matter, in memory of Professor Shmuel Fishman

Iron-bearing oxides undergo a series of pressure-induced electronic, spin and structural transitions that can cause seismic anomalies and dynamic instabilities in Earth's mantle and outer core. We employ x-ray diffraction and x-ray emission spectroscopy along with state-of-the-art density functional plus dynamical mean-field theory (DFT+DMFT) to characterize the electronic structure and spin states, and crystal-structural properties of w\"ustite (Fe$_{1-x}$O) -- a basic oxide component of Earth's interior -- at high pressure-temperature conditions up to 140 GPa and 2100 K. We find that FeO exhibits complex polymorphism under pressure, with abnormal compression behavior associated with electron-spin and crystallographic phase transitions, and resulting in a substantial change of bulk modulus. Our results reveal the existence of a high-pressure phase characterized by a metallic high-spin state of iron at about the pressure-temperature conditions of Earth's core-mantle boundary. The presence of high-spin metallic iron near the base of the mantle can significantly influence the geophysical and geochemical properties of Earth's deep interior., Comment: 5 figures, with supplementary materials