Opportunistic splitting for scheduling via stochastic approximation

We consider the problem of scheduling a wireless channel among multiple users. A slot is given to a user with a highest metric (e.g., channel gain) in that slot. The scheduler may not know the channel states of all the users at the beginning of each slot. In this scenario opportunistic splitting is an attractive solution. However this algorithm requires that the metrics of different users form independent, identically distributed (iid) sequences with same distribution and that their distribution and number be known to the scheduler. This limits the usefulness of opportunistic splitting. In this paper we develop a parametric version of this algorithm. The optimal parameters of the algorithm are learnt online through a stochastic approximation scheme. Our algorithm does not require the metrics of different users to have the same distribution. The statistics of these metrics and the number of users can be unknown and also vary with time. We prove the convergence of the algorithm and show its utility by scheduling the channel to maximize its throughput while satisfying some fairness and/or quality of service constraints.

Freezing of classical fluids in a quenched random potential

The phase diagram of a hard-sphere fluid in the presence of a random pinning potential is studied analytically and numerically. In the analytic work, replicas are introduced for averaging over the quenched disorder, and the hypernetted chain approximation is used to calculate density correlations in the replicated liquid. The freezing transition of the liquid into a nearly crystalline state is studied using a density-functional approach, and the liquid to glass transition is studied using a phenomenological replica symmetry breaking approach. In the numerical work, local minima of a discretized version of the Ramakrishnan-Yussouff free-energy functional are located and the phase diagram in the density-disorder plane is obtained from an analysis of the relative stability of these minima. Both approaches lead to similar results for the phase diagram. The first-order liquid to crystalline solid transition is found to change to a continuous liquid to glass transition as the strength of the disorder is increased above a threshold value.

Theory of polymer breaking under tension

We consider the breaking of a polymer molecule which is fixed at one end and is acted upon by a force at the other. The polymer is assumed to be a linear chain joined together by bonds which satisfy the Morse potential. The applied force is found to modify the Morse potential so that the minimum becomes metastable. Breaking is just the decay of this metastable bond, by causing it to go over the barrier. Increasing the force causes the potential to become more and more distorted and eventually leads to the disappearance of the barrier. The limiting force at which the barrier disappears is D(e)a/2,D-e with a the parameters characterizing the Morse potential. The rate of breaking is first calculated using multidimensional quantum transition state theory. We use the harmonic approximation to account for vibrations of all the units. It includes tunneling contributions to the rate, but is valid only above a certain critical temperature. It is possible to get an analytical expression for the rate of breaking. We have calculated the rate of breaking for a model, which mimics polyethylene. First we calculate the rate of breaking of a single bond, without worrying about the other bonds. Inclusion of other bonds under the harmonic approximation is found to lower this rate by at the most one order of magnitude. Quantum effects are found to increase the rate of breaking and are significant only at temperatures less than 150 K. At 300 K, the calculations predict a bond in polyethylene to have a lifetime of only seconds at a force which is only half the limiting force. Calculations were also done using the Lennard-Jones potential. The results for Lennard-Jones and Morse potentials were rather different, due to the different long-range behaviors of the two potentials. A calculation including friction was carried out, at the classical level, by assuming that each atom of the chain is coupled to its own collection of harmonic oscillators. Comparison of the results with the simulations of Oliveira and Taylor [J. Chem. Phys. 101, 10 118 (1994)] showed the rate to be two to three orders of magnitude higher. As a possible explanation of discrepancy, we consider the translational motion of the ends of the broken chains. Using a continuum approximation for the chain, we find that in the absence of friction, the rate of the process can be limited by the rate at which the two broken ends separate from one another and the lowering of the rate is at the most a factor of 2, for the parameters used in the simulation (for polyethylene). In the presence of friction, we find that the rate can be lowered by one to two orders of magnitude, making our results to be in reasonable agreement with the simulations.

Pseudodynamic systems approach based on a quadratic approximation of update equations for diffuse optical tomography

We explore a pseudodynamic form of the quadratic parameter update equation for diffuse optical tomographic reconstruction from noisy data. A few explicit and implicit strategies for obtaining the parameter updates via a semianalytical integration of the pseudodynamic equations are proposed. Despite the ill-posedness of the inverse problem associated with diffuse optical tomography, adoption of the quadratic update scheme combined with the pseudotime integration appears not only to yield higher convergence, but also a muted sensitivity to the regularization parameters, which include the pseudotime step size for integration. These observations are validated through reconstructions with both numerically generated and experimentally acquired data. (C) 2011 Optical Society of America

Theory of Gas Hydrates: Effect of the Approximation of Rigid Water Lattice

One of the assumptions of the van der Waals and Platteeuw theory for gas hydrates is that the host water lattice is rigid and not distorted by the presence of guest molecules. In this work, we study the effect of this approximation on the triple-point lines of the gas hydrates. We calculate the triple-point lines of methane and ethane hydrates via Monte Carlo molecular simulations and compare the simulation results with the predictions of van der Waals and Platteeuw theory. Our study shows that even if the exact intermolecular potential between the guest molecules and water is known, the dissociation temperatures predicted by the theory are significantly higher. This has serious implications to the modeling of gas hydrate thermodynamics, and in spite of the several impressive efforts made toward obtaining an accurate description of intermolecular interactions in gas hydrates, the theory will suffer from the problem of robustness if the issue of movement of water molecules is not adequately addressed.

Polynomial Approximation, Local Polynomial convexity, and Degenerate CR Singularities- II

We provide some conditions for the graph of a Holder-continuous function on (D) over bar, where (D) over bar is a closed disk in C, to be polynomially convex. Almost all sufficient conditions known to date - provided the function (say F) is smooth - arise from versions of the Weierstrass Approximation Theorem on (D) over bar. These conditions often fail to yield any conclusion if rank(R)DF is not maximal on a sufficiently large subset of (D) over bar. We bypass this difficulty by introducing a technique that relies on the interplay of certain plurisubharmonic functions. This technique also allows us to make some observations on the polynomial hull of a graph in C(2) at an isolated complex tangency.

An Online Actor-Critic Algorithm with Function Approximation for Constrained Markov Decision Processes

We develop an online actor-critic reinforcement learning algorithm with function approximation for a problem of control under inequality constraints. We consider the long-run average cost Markov decision process (MDP) framework in which both the objective and the constraint functions are suitable policy-dependent long-run averages of certain sample path functions. The Lagrange multiplier method is used to handle the inequality constraints. We prove the asymptotic almost sure convergence of our algorithm to a locally optimal solution. We also provide the results of numerical experiments on a problem of routing in a multi-stage queueing network with constraints on long-run average queue lengths. We observe that our algorithm exhibits good performance on this setting and converges to a feasible point.

Stabilization of stochastic approximation by step size adaptation

A scheme for stabilizing stochastic approximation iterates by adaptively scaling the step sizes is proposed and analyzed. This scheme leads to the same limiting differential equation as the original scheme and therefore has the same limiting behavior, while avoiding the difficulties associated with projection schemes. The proof technique requires only that the limiting o.d.e. descend a certain Lyapunov function outside an arbitrarily large bounded set. (C) 2012 Elsevier B.V. All rights reserved.

Cumulus clouds and convective boundary layers: a tropical perspective on two turbulent shear flows

This paper is a review prepared for the second Marseille Colloquium on the mechanics of turbulence, held in 2011, 50 years after the first. The review covers recent developments in our understanding of the large-scale dynamics of cumulus cloud flows and of the atmospheric boundary layer in the low-wind convective regime that is often encountered in the tropics. It has recently been shown that a variety of cumulus cloud forms and life cycles can be experimentally realized in the laboratory, with the transient diabatic plume taken as the flow model for a cumulus cloud. The plume is subjected to diabatic heating scaled to be dynamically similar to heat release from phase changes in clouds. The experiments are complemented by exact numerical solutions of the Navier-Stokes-Boussinesq equations for plumes with scaled off-source heating. The results show that the Taylor entrainment coefficient first increases with heating, reaches a positive maximum and then drops rapidly to zero or even negative values. This reduction in entrainment is a consequence of structural changes in the flow, smoothing out the convoluted boundaries in the non-diabatic plume, including the tongues engulfing the ambient flow. This is accompanied by a greater degree of mixedness in the core flow because of lower dilution by the ambient fluid. The cloud forms generated depend strongly on the history of the diabatic heating profile in the vertical direction. The striking effects of heating on the flow are attributable to the operation of the baroclinic torque due to the temperature field. The mean baroclinic torque is shown to peak around a quasi-cylindrical sheet situated midway between the axis of the flow and the edges. This torque is shear-enhancing and folds down the engulfment tongues. The increase in mixedness can be traced to an explosive growth in the enstrophy, triggered by a strong fluctuating baroclinic torque that acts as a source, especially at the higher wave numbers, thus enhancing the mixedness. In convective boundary layers field measurements show that, under conditions prevailing in the tropics, the eddy fluxes of momentum and energy do not follow the Monin-Obukhov similarity. Instead, the eddy momentum flux is found to be linear in the wind speed at low winds; and the eddy heat flux is, to a first approximation, governed by free convection laws, with wind acting as a small perturbation on a regime of free convection. A new boundary layer code, based on heat flux scaling rather than wall-stress scaling, shows promising improvements in predictive skills of a general circulation model.

Confined fluids in a Janus pore: influence of surface asymmetry on structure and solvation forces

Density distribution, fluid structure and solvation forces for fluids confined in Janus slit-shaped pores are investigated using grand canonical Monte Carlo simulations. By varying the degree of asymmetry between the two smooth surfaces that make up the slit pores, a wide variety of adsorption situations are observed. The presence of one moderately attractive surface in the asymmetric pore is sufficient to disrupt the formation of frozen phases observed in the symmetric case. In the extreme case of asymmetry in which one wall is repulsive, the pore fluid can consist of a frozen contact layer at the attractive surface for smaller surface separations (H) or a frozen contact layer with liquid-like and gas-like regions as the pore width is increased. The superposition approximation, wherein the solvation pressure and number density in the asymmetric pores can be obtained from the results on symmetric pores, is found to be accurate for H > 4 sigma(ff), where sigma(ff) is the Lennard-Jones fluid diameter and within 10% accuracy for smaller surface separations. Our study has implications in controlling stick slip and overcoming static friction `stiction' in micro and nanofluidic devices.

A constant factor approximation algorithm for boxicity of circular arc graphs

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional axis parallel boxes in Rk. Equivalently, it is the minimum number of interval graphs on the vertex set V such that the intersection of their edge sets is E. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below O(n0.5-ε)-factor, for any ε > 0 in polynomial time unless NP = ZPP. Till date, there is no well known graph class of unbounded boxicity for which even an nε-factor approximation algorithm for computing boxicity is known, for any ε < 1. In this paper, we study the boxicity problem on Circular Arc graphs - intersection graphs of arcs of a circle. We give a (2+ 1/k)-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where k ≥ 1 is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is O(mn+n2) in both these cases and in O(mn+kn2) which is at most O(n3) time we also get their corresponding box representations, where n is the number of vertices of the graph and m is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time.

Fast acoustic likelihood computation using low-rank matrix approximation

Acoustic modeling using mixtures of multivariate Gaussians is the prevalent approach for many speech processing problems. Computing likelihoods against a large set of Gaussians is required as a part of many speech processing systems and it is the computationally dominant phase for LVCSR systems. We express the likelihood computation as a multiplication of matrices representing augmented feature vectors and Gaussian parameters. The computational gain of this approach over traditional methods is by exploiting the structure of these matrices and efficient implementation of their multiplication.In particular, we explore direct low-rank approximation of the Gaussian parameter matrix and indirect derivation of low-rank factors of the Gaussian parameter matrix by optimum approximation of the likelihood matrix. We show that both the methods lead to similar speedups but the latter leads to far lesser impact on the recognition accuracy. Experiments on a 1138 word vocabulary RM1 task using Sphinx 3.7 system show that, for a typical case the matrix multiplication approach leads to overall speedup of 46%. Both the low-rank approximation methods increase the speedup to around 60%, with the former method increasing the word error rate (WER) from 3.2% to 6.6%, while the latter increases the WER from 3.2% to 3.5%.

Quadrature approximation properties of the spiral-phase quadrature transform

The notion of the 1-D analytic signal is well understood and has found many applications. At the heart of the analytic signal concept is the Hilbert transform. The problem in extending the concept of analytic signal to higher dimensions is that there is no unique multidimensional definition of the Hilbert transform. Also, the notion of analyticity is not so well under stood in higher dimensions. Of the several 2-D extensions of the Hilbert transform, the spiral-phase quadrature transform or the Riesz transform seems to be the natural extension and has attracted a lot of attention mainly due to its isotropic properties. From the Riesz transform, Larkin et al. constructed a vortex operator, which approximates the quadratures based on asymptotic stationary-phase analysis. In this paper, we show an alternative proof for the quadrature approximation property by invoking the quasi-eigenfunction property of linear, shift-invariant systems. We show that the vortex operator comes up as a natural consequence of applying this property. We also characterize the quadrature approximation error in terms of its energy as well as the peak spatial-domain error. Such results are available for 1-D signals, but their counter part for 2-D signals have not been provided. We also provide simulation results to supplement the analytical calculations.

Application of a modified jogged-screw model for creep of titanium aluminides: evaluation of the key substructural parameters

A modification of the jogged-screw model has been adopted recently by the authors to explain observations of 1/2[110]-type jogged-screw dislocations in equiaxed Ti-48Al under creep conditions. The aim of this study has been to verify and validate the parameters and functional dependencies that have been assumed in this previous work. The original solution has been reformulated to take into account the finite length of the moving jog. This is a better approximation of the tall jog. The substructural model parameters have been further investigated in light of the Finite Length Moving Line (FLML) source approximation. The original model assumes that the critical jog height (beyond which the jog is not dragged) is inversely proportional to the applied stress. By accounting for the fact that there are three competing mechanisms (jog dragging, dipole dragging, dipole bypass) possible, we can arrive at a modified critical jog height. The critical jog height was found to be more strongly stress dependent than assumed previously. The original model assumes the jog spacing to be invariant over the stress range. However, dynamic simulation using a line tension model has shown that the jog spacing is inversely proportional to the applied stress. This has also been confirmed by TEM measurements of jog spacings over a range of stresses. Taylor's expression assumed previously to provide the dependence of dislocation density on the applied stress, has now been confirmed by actual dislocation density measurements. Combining all of these parameters and dependencies, derived both from experiment and theory, leads to an excellent prediction of creep rates and stress exponents. The further application of this model to other materials, and the important role of atomistic and dislocation dynamics simulations in its continued development is also discussed.