Event-triggered sampling using signal extrema for instantaneous amplitude and instantaneous frequency estimation

Event-triggered sampling (ETS) is a new approach towards efficient signal analysis. The goal of ETS need not be only signal reconstruction, but also direct estimation of desired information in the signal by skillful design of event. We show a promise of ETS approach towards better analysis of oscillatory non-stationary signals modeled by a time-varying sinusoid, when compared to existing uniform Nyquist-rate sampling based signal processing. We examine samples drawn using ETS, with events as zero-crossing (ZC), level-crossing (LC), and extrema, for additive in-band noise and jitter in detection instant. We find that extrema samples are robust, and also facilitate instantaneous amplitude (IA), and instantaneous frequency (IF) estimation in a time-varying sinusoid. The estimation is proposed solely using extrema samples, and a local polynomial regression based least-squares fitting approach. The proposed approach shows improvement, for noisy signals, over widely used analytic signal, energy separation, and ZC based approaches (which are based on uniform Nyquist-rate sampling based data-acquisition and processing). Further, extrema based ETS in general gives a sub-sampled representation (relative to Nyquistrate) of a time-varying sinusoid. For the same data-set size captured with extrema based ETS, and uniform sampling, the former gives much better IA and IF estimation. (C) 2015 Elsevier B.V. All rights reserved.

Robust Savitzky-Golay Filters

Local polynomial approximation of data is an approach towards signal denoising. Savitzky-Golay (SG) filters are finite-impulse-response kernels, which convolve with the data to result in polynomial approximation for a chosen set of filter parameters. In the case of noise following Gaussian statistics, minimization of mean-squared error (MSE) between noisy signal and its polynomial approximation is optimum in the maximum-likelihood (ML) sense but the MSE criterion is not optimal for non-Gaussian noise conditions. In this paper, we robustify the SG filter for applications involving noise following a heavy-tailed distribution. The optimal filtering criterion is achieved by l(1) norm minimization of error through iteratively reweighted least-squares (IRLS) technique. It is interesting to note that at any stage of the iteration, we solve a weighted SG filter by minimizing l(2) norm but the process converges to l(1) minimized output. The results show consistent improvement over the standard SG filter performance.

A hybrid method for stochastic response analysis of a vibrating structure

Response analysis of a linear structure with uncertainties in both structural parameters and external excitation is considered here. When such an analysis is carried out using the spectral stochastic finite element method (SSFEM), often the computational cost tends to be prohibitive due to the rapid growth of the number of spectral bases with the number of random variables and the order of expansion. For instance, if the excitation contains a random frequency, or if it is a general random process, then a good approximation of these excitations using polynomial chaos expansion (PCE) involves a large number of terms, which leads to very high cost. To address this issue of high computational cost, a hybrid method is proposed in this work. In this method, first the random eigenvalue problem is solved using the weak formulation of SSFEM, which involves solving a system of deterministic nonlinear algebraic equations to estimate the PCE coefficients of the random eigenvalues and eigenvectors. Then the response is estimated using a Monte Carlo (MC) simulation, where the modal bases are sampled from the PCE of the random eigenvectors estimated in the previous step, followed by a numerical time integration. It is observed through numerical studies that this proposed method successfully reduces the computational burden compared with either a pure SSFEM of a pure MC simulation and more accurate than a perturbation method. The computational gain improves as the problem size in terms of degrees of freedom grows. It also improves as the timespan of interest reduces.

Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints

The 3-Hitting Set problem involves a family of subsets F of size at most three over an universe U. The goal is to find a subset of U of the smallest possible size that intersects every set in F. The version of the problem with parity constraints asks for a subset S of size at most k that, in addition to being a hitting set, also satisfies certain parity constraints on the sizes of the intersections of S with each set in the family F. In particular, an odd (even) set is a hitting set that hits every set at either one or three (two) elements, and a perfect code is a hitting set that intersects every set at exactly one element. These questions are of fundamental interest in many contexts for general set systems. Just as for Hitting Set, we find these questions to be interesting for the case of families consisting of sets of size at most three. In this work, we initiate an algorithmic study of these problems in this special case, focusing on a parameterized analysis. We show, for each problem, efficient fixed-parameter tractable algorithms using search trees that are tailor-made to the constraints in question, and also polynomial kernels using sunflower-like arguments in a manner that accounts for equivalence under the additional parity constraints.

Unique Covering Problems with Geometric Sets

The Exact Cover problem takes a universe U of n elements, a family F of m subsets of U and a positive integer k, and decides whether there exists a subfamily(set cover) F' of size at most k such that each element is covered by exactly one set. The Unique Cover problem also takes the same input and decides whether there is a subfamily F' subset of F such that at least k of the elements F' covers are covered uniquely(by exactly one set). Both these problems are known to be NP-complete. In the parameterized setting, when parameterized by k, Exact Cover is W1]-hard. While Unique Cover is FPT under the same parameter, it is known to not admit a polynomial kernel under standard complexity-theoretic assumptions. In this paper, we investigate these two problems under the assumption that every set satisfies a given geometric property Pi. Specifically, we consider the universe to be a set of n points in a real space R-d, d being a positive integer. When d = 2 we consider the problem when. requires all sets to be unit squares or lines. When d > 2, we consider the problem where. requires all sets to be hyperplanes in R-d. These special versions of the problems are also known to be NP-complete. When parameterizing by k, the Unique Cover problem has a polynomial size kernel for all the above geometric versions. The Exact Cover problem turns out to be W1]-hard for squares, but FPT for lines and hyperplanes. Further, we also consider the Unique Set Cover problem, which takes the same input and decides whether there is a set cover which covers at least k elements uniquely. To the best of our knowledge, this is a new problem, and we show that it is NP-complete (even for the case of lines). In fact, the problem turns out to be W1]-hard in the abstract setting, when parameterized by k. However, when we restrict ourselves to the lines and hyperplanes versions, we obtain FPT algorithms.

Experimental Study of Shape Transition in an Acoustically Levitated and Externally Heated Droplet

Experimental analyses of surface oscillations are reported in acoustically levitated, radiatively heated bicomponent droplets with one volatile and other being nonvolatile. Two instability pathways are observed: one being acoustically driven observed in low-vapor pressure fluid droplets and other being boiling driven observed in high-vapor pressure fluid droplets. The first pathway shows extreme droplets deformation and subsequent breakup by acoustic pressure and externally supplied heat. Also transition of instabilities from acoustically activated shape distortion regime to thermally induced boiling regime is observed with increasing concentration of volatile component in bicomponent droplets. Precursor phases of instabilities are investigated using Legendre's polynomial.

Lower Bounds for Sums of Powers of Low Degree Univariates

We consider the problem of representing a univariate polynomial f(x) as a sum of powers of low degree polynomials. We prove a lower bound of Omega(root d/t) for writing an explicit univariate degree-d polynomial f(x) as a sum of powers of degree-t polynomials.

Universality of the Stochastic Airy Operator

We introduce a new method for studying universality of random matrices. Let T-n be the Jacobi matrix associated to the Dyson beta ensemble with uniformly convex polynomial potential. We show that after scaling, Tn converges to the stochastic Airy operator. In particular, the top edge of the Dyson beta ensemble and the corresponding eigenvectors are universal. As a byproduct, these ideas lead to conjectured operator limits for the entire family of soft edge distributions. (C) 2015 Wiley Periodicals, Inc.

QoS Constrained Optimal Sink and Relay Placement in Planned Wireless Sensor Networks

We are given a set of sensors at given locations, a set of potential locations for placing base stations (BSs, or sinks), and another set of potential locations for placing wireless relay nodes. There is a cost for placing a BS and a cost for placing a relay. The problem we consider is to select a set of BS locations, a set of relay locations, and an association of sensor nodes with the selected BS locations, so that the number of hops in the path from each sensor to its BS is bounded by h(max), and among all such feasible networks, the cost of the selected network is the minimum. The hop count bound suffices to ensure a certain probability of the data being delivered to the BS within a given maximum delay under a light traffic model. We observe that the problem is NP-Hard, and is hard to even approximate within a constant factor. For this problem, we propose a polynomial time approximation algorithm (SmartSelect) based on a relay placement algorithm proposed in our earlier work, along with a modification of the greedy algorithm for weighted set cover. We have analyzed the worst case approximation guarantee for this algorithm. We have also proposed a polynomial time heuristic to improve upon the solution provided by SmartSelect. Our numerical results demonstrate that the algorithms provide good quality solutions using very little computation time in various randomly generated network scenarios.

Anomalous transport at weak coupling

We evaluate the contribution of chiral fermions in d = 2, 4, 6, chiral bosons, a chiral gravitino like theory in d = 2 and chiral gravitinos in d = 6 to all the leading parity odd transport coefficients at one loop. This is done by using finite temperature field theory to evaluate the relevant Kubo formulae. For chiral fermions and chiral bosons the relation between the parity odd transport coefficient and the microscopic anomalies including gravitational anomalies agree with that found by using the general methods of hydrodynamics and the argument involving the consistency of the Euclidean vacuum. For the gravitino like theory in d = 2 and chiral gravitinos in d = 6, we show that relation between the pure gravitational anomaly and parity odd transport breaks down. From the perturbative calculation we clearly identify the terms that contribute to the anomaly polynomial, but not to the transport coefficient for gravitinos. We also develop a simple method for evaluating the angular integrals in the one loop diagrams involved in the Kubo formulae. Finally we show that charge diffusion mode of an ideal 2 dimensional Weyl gas in the presence of a finite chemical potential acquires a speed, which is equal to half the speed of light.

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

We show here a 2(Omega(root d.log N)) size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree d on N variables (with N = d(3) in our case) with 0, 1-coefficients such that for any representation of a polynomial f in this family of the form f = Sigma(i) Pi(j) Q(ij), where the Q(ij)'s are homogeneous polynomials (recall that a polynomial is said to be homogeneous if all its monomials have the same degree), it must hold that Sigma(i,j) (Number of monomials of Q(ij)) >= 2(Omega(root d.log N)). The above mentioned family, which we refer to as the Nisan-Wigderson design-based family of polynomials, is in the complexity class VNP. Our work builds on the recent lower bound results 1], 2], 3], 4], 5] and yields an improved quantitative bound as compared to the quasi-polynomial lower bound of 6] and the N-Omega(log log (N)) lower bound in the independent work of 7].

Kernelization complexity of possible winner and coalitional manipulation problems in voting

In the POSSIBLE WINNER problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the POSSIBLE WINNER problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge 10]. In this paper, we settle this open question for many common voting rules. We show that the POSSIBLE WINNER problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that includes the Borda voting rule does not admit a polynomial kernel with the number of candidates as the parameter. We show however that the COALITIONAL MANIPULATION problem which is an important special case of the POSSIBLE WINNER problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the POSSIBLE WINNER problem is harder than the COALITIONAL MANIPULATION problem since the COALITIONAL MANIPULATION problem admits a polynomial kernel whereas the POSSIBLE WINNER problem does not admit a polynomial kernel. (C) 2015 Elsevier B.V. All rights reserved.

Magnetic structures and magnetic phase transitions in the Mn-doped orthoferrite TbFeO3 studied by neutron powder diffraction

The magnetic structures and the magnetic phase transitions in the Mn-doped orthoferrite TbFeO3 studied using neutron powder diffraction are reported. Magnetic phase transitions are identified at T-N(Fe/Mn) approximate to 295K where a paramagnetic-to-antiferromagnetic transition occurs in the Fe/Mn sublattice, T-SR(Fe/Mn) approximate to 26K where a spin-reorientation transition occurs in the Fe/Mn sublattice and T-N(R) approximate to 2K where Tb-ordering starts to manifest. At 295 K, the magnetic structure of the Fe/Mn sublattice in TbFe0.5Mn0.5O3 belongs to the irreducible representation Gamma(4) (G(x)A(y)F(z) or Pb'n'm). A mixed-domain structure of (Gamma(1) + Gamma(4)) is found at 250K which remains stable down to the spin re-orientation transition at T-SR(Fe/Mn) approximate to 26K. Below 26K and above 250 K, the majority phase (>80%) is that of Gamma(4). Below 10K the high-temperature phase Gamma(4) remains stable till 2K. At 2 K, Tb develops a magnetic moment value of 0.6(2) mu(B)/f.u. and orders long-range in F-z compatible with the Gamma(4) representation. Our study confirms the magnetic phase transitions reported already in a single crystal of TbFe0.5Mn0.5O3 and, in addition, reveals the presence of mixed magnetic domains. The ratio of these magnetic domains as a function of temperature is estimated from Rietveld refinement of neutron diffraction data. Indications of short-range magnetic correlations are present in the low-Q region of the neutron diffraction patterns at T < T-SR(Fe/Mn). These results should motivate further experimental work devoted to measure electric polarization and magnetocapacitance of TbFe0.5Mn0.5O3. (C) 2016 AIP Publishing LLC.

Magnetic structures and magnetic phase transitions in the Mn-doped orthoferrite TbFeO3 studied by neutron powder diffraction

The magnetic structures and the magnetic phase transitions in the Mn-doped orthoferrite TbFeO3 studied using neutron powder diffraction are reported. Magnetic phase transitions are identified at T-N(Fe/Mn) approximate to 295K where a paramagnetic-to-antiferromagnetic transition occurs in the Fe/Mn sublattice, T-SR(Fe/Mn) approximate to 26K where a spin-reorientation transition occurs in the Fe/Mn sublattice and T-N(R) approximate to 2K where Tb-ordering starts to manifest. At 295 K, the magnetic structure of the Fe/Mn sublattice in TbFe0.5Mn0.5O3 belongs to the irreducible representation Gamma(4) (G(x)A(y)F(z) or Pb'n'm). A mixed-domain structure of (Gamma(1) + Gamma(4)) is found at 250K which remains stable down to the spin re-orientation transition at T-SR(Fe/Mn) approximate to 26K. Below 26K and above 250 K, the majority phase (>80%) is that of Gamma(4). Below 10K the high-temperature phase Gamma(4) remains stable till 2K. At 2 K, Tb develops a magnetic moment value of 0.6(2) mu(B)/f.u. and orders long-range in F-z compatible with the Gamma(4) representation. Our study confirms the magnetic phase transitions reported already in a single crystal of TbFe0.5Mn0.5O3 and, in addition, reveals the presence of mixed magnetic domains. The ratio of these magnetic domains as a function of temperature is estimated from Rietveld refinement of neutron diffraction data. Indications of short-range magnetic correlations are present in the low-Q region of the neutron diffraction patterns at T < T-SR(Fe/Mn). These results should motivate further experimental work devoted to measure electric polarization and magnetocapacitance of TbFe0.5Mn0.5O3. (C) 2016 AIP Publishing LLC.

Tracking the migration of the Indian continent using the carbonate clumped isotope technique on Phanerozoic soil carbonates

Approximately 140 million years ago, the Indian plate separated from Gondwana and migrated by almost 90 degrees latitude to its current location, forming the Himalayan-Tibetan system. Large discrepancies exist in the rate of migration of Indian plate during Phanerozoic. Here we describe a new approach to paleo-latitudinal reconstruction based on simultaneous determination of carbonate formation temperature and delta O-18 of soil carbonates, constrained by the abundances of C-13-O-18 bonds in palaeosol carbonates. Assuming that the palaeosol carbonates have a strong relationship with the composition of the meteoric water, delta O-18 carbonate of palaeosol can constrain paleo-latitudinal position. Weighted mean annual rainfall delta O-18 water values measured at several stations across the southern latitudes are used to derive a polynomial equation: delta(18)Ow = -0.006 x (LAT)(2) - 0.294 x (LAT) - 5.29 which is used for latitudinal reconstruction. We use this approach to show the northward migration of the Indian plate from 46.8 +/- 5.8 degrees S during the Permian (269 M. y.) to 30 +/- 11 degrees S during the Triassic (248 M. y.), 14.7 +/- 8.7 degrees S during the early Cretaceous (135 M. y.), and 28 +/- 8.8 degrees S during the late Cretaceous ( 68 M. y.). Soil carbonate delta O-18 provides an alternative method for tracing the latitudinal position of Indian plate in the past and the estimates are consistent with the paleo-magnetic records which document the position of Indian plate prior to 135 +/- 3 M. y.