Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties)

We study the k-level uncapacitated facility location problem (k-level UFL) in which clients need to be connected with paths crossing open facilities of k types (levels). In this paper we first propose an approximation algorithm that for any constant k, in polynomial time, delivers solutions of cost at most α _k times OPT, where α _k is an increasing function of k, with \(\lim _{k\to \infty } \alpha _{k} = 3\). Our algorithm rounds a fractional solution to an extended LP formulation of the problem. The rounding builds upon the technique of iteratively rounding fractional solutions on trees (Garg, Konjevod, and Ravi SODA’98) originally used for the group Steiner tree problem. We improve the approximation ratio for k-level UFL for all k ≥ 3, in particular we obtain the ratio equal 2.02, 2.14, and 2.24 for k = 3,4, and 5.     

Verifiable threshold quantum secret sharing with sequential communication

A (t, n) threshold quantum secret sharing (QSS) is proposed based on a single d-level quantum system. It enables the (t, n) threshold structure based on Shamir’s secret sharing and simply requires sequential communication in d-level quantum system to recover secret. Besides, the scheme provides a verification mechanism which employs an additional qudit to detect cheats and eavesdropping during secret reconstruction and allows a participant to use the share repeatedly. Analyses show that the proposed scheme is resistant to typical attacks. Moreover, the scheme is scalable in participant number and easier to realize compared to related schemes. More generally, our scheme also presents a generic method to construct new (t, n) threshold QSS schemes based on d-level quantum system from other classical threshold secret sharing.     

Enhanced chemosensing of ammonia based on the novel molecular semiconductor-doped insulator (MSDI) heterojunctions

A series of new molecular semiconductor-doped insulator (MSDI) heterojunctions as conductimetric transducers to NH₃ sensing were fabricated based on a novel semiconducting molecular material, an amphiphilic tris(phthalocyaninato) rare earth triple-decker complex, Eu₂[Pc(15C5)₄]₂[Pc(OC₁₀H₂₁)₈], quasi-Langmuir-Shäfer (QLS) film, as a top-layer, and vacuum-deposited and cast film of CuPc as well as copper tetra-tert-butyl phthalocyanine (CuTTBPc) QLS film as a sub-layer, named as MSDIs 1, 2 and 3, respectively. MSDIs 1-3 and respective sub-layers prepared from three different methods were characterized by X-ray diffraction, electronic absorption spectra and current-voltage (I-V) measurements. Depending on the sub-layer film-forming method used, α-phase CuPc film structure, β-phase CuPc crystallites and H-type aggregates of CuTTBPc have been obtained, respectively. An increasing sensitivity to NH₃ at varied concentrations in the range of 15-800 ppm, follows the order MSDI 2 < MSDI 3 < MSDI 1, revealing the effect of sub-layer film structures on sensing performance of the MSDIs. In particular, the time-dependent current plot of the MSDI 1, with α-phase CuPc film as a sub-layer, clearly shows an excellent separation of the different ammonia concentration levels and nearly complete reversibility and reproducibility even at room temperature, which is unique among the phthalocyanine-based ammonia sensors thus far reported in the literature. This provides a general method to improve sensor response of organic heterojunctions by controlling and tuning the film structure of sub-layer with appropriate fabrication techniques. On the other hand, the enhanced sensitivity, stability and reproducible response of the MSDI 1 heterostructure in comparison with the respective single-layer films have also been obtained. A judicious combination of materials and molecular architectures has led to enhanced sensing properties of the MSDI 1, in which control at the molecular level can be achieved.     

Study of the characteristics of random errors in measurements by MEMS inertial sensors

This paper considers a stochastic analysis of measurement errors in MotionNode inertial measurement units (IMUs). The sensors of this device are based on the microelectromechanical system (MEMS) technology. The use of the Allan variance algorithm for identifying the error’s nature and the stochastic modeling of this error make it possible to substantially reduce the measurement errors by sensors. Based on the results of this study, we elaborated a number of recommendations for increasing the efficiency of the use of MEMS inertial sensors for problems of the navigation of moving objects.     

Error Analysis and Stochastic Modeling of Low-cost MEMS Accelerometer

This paper presents the error analysis and stochastic modeling of commercial low-cost MEMS Accelerometer. Although Micro Electro Mechanical Systems (MEMS) based sensors have been utilized for the development of low-cost integrated navigation systems on the benefits of low inherent cost, small size, low power consumption, and solid reliability, it is significantly important to characterize the error behaviors of MEMS-based sensors and to construct more sophisticated mathematical modeling methods. The errors of MEMS-based accelerometer have been identified into deterministic and stochastic error sources and the stochastic error part was the focus to be discussed in this paper using discrete parameter models of stationary random process. Appropriate Autoregressive (AR) models have been analyzed which can be used to help the development of appropriate optimal algorithm for multiple sensor integration.     

On the passivity properties of a new family of repetitive (hyperbolic) controllers

This paper studies the passivity properties of three recently reported repetitive schemes (Escobar et al. 2007a Bollen, MHJ and Gu, I. 2006. Signal Processing of Power Quality Disturbances, Piscataway, NJ: Wiley-IEEE Press.  [Google Scholar], b). They are referred as negative feedback, positive feedback and 6?±1 repetitive compensators. The first two controllers are composed of a feedback array of a single delay line, while the third controller comprises the feedback array of two delay lines. As most repetitive schemes, these three schemes are intended for the compensation or tracking of periodic signals, which are composed of harmonic components of a fundamental frequency. In particular, the negative feedback scheme is aimed for the compensation of odd-harmonic components, the positive feedback scheme for the compensation of all harmonics, and the 6?±1 scheme for the compensation of 6?±1 (??=?0,1,2,…,∞) harmonics. These schemes are usually included as an additional block to a stabilising compensator, introducing refining terms to guarantee harmonic compensation. For instance they can serve as the harmonic compensation mechanism in a inner loop in several power electronics applications such as active rectifiers, active filters, etc. It is shown here that all three schemes also have equivalent expressions in terms of hyperbolic functions. The main contribution of the present work is to show that these three schemes are discrete-time positive real and thus passive. Moreover, it is shown that, after a modification, motivated by practical issues, these schemes become strictly passive.     

基于压力补偿的高精度智能变送器的设计

为在不同大气压力环境下,精确测量热式差压传感器采集的差压信号,设计了基于压力补偿的高精度智能变送器.系统由热式差压传感器、压力补偿放大器模块、变送输出模块组成.给出了完整的系统低功耗设计框图,提出了一种在传统变送器基础上复合绝压传感器进行大气压力补偿的方法,实现了变送器的自校准功能.描述了压力补偿放大器模块和变送输出模...     

Temporal synchronization in mobile sensor networks using image sequence analysis

This paper addresses the problem of estimating the temporal synchronization in mobile sensors’ networks, by using image sequence analysis of their corresponding scene dynamics. Unlike existing methods, which are frequently based on adaptations of techniques originally designed for wired networks with static topologies, or even based on solutions specially designed for ad hoc wireless sensor networks, but that have a high energy consumption and a low scalability regarding the number of sensors, this work proposes a novel approach that reduces the problem of synchronizing a general number $N$ of sensors to the robust estimation of a single line in ${\mathbb {R}}^{N+1}$ . This line captures all temporal relations between the sensors and can be computed without any prior knowledge of these relations. It is assumed that (1) the network’s mobile sensors cross the field of view of a stationary calibrated camera that operates with constant frame rate and (2) the sensors trajectories are estimated with a limited error at a constant sampling rate, both in the world coordinate system and in the camera’s image plane. Experimental results with real-world and synthetic scenarios demonstrate that our method can be successfully used to determine the temporal alignment in mobile sensor networks.     

Three iteratively reweighted least squares algorithms for $$L_1$$-norm principal component analysis

Principal component analysis (PCA) is often used to reduce the dimension of data by selecting a few orthonormal vectors that explain most of the variance structure of the data. \(L_1\) PCA uses the \(L_1\) norm to measure error, whereas the conventional PCA uses the \(L_2\) norm. For the \(L_1\) PCA problem minimizing the fitting error of the reconstructed data, we propose three algorithms based on iteratively reweighted least squares. We first develop an exact reweighted algorithm. Next, an approximate version is developed based on eigenpair approximation when the algorithm is near convergent. Finally, the approximate version is extended based on stochastic singular value decomposition. We provide convergence analyses, and compare their performance against benchmark algorithms in the literature. The computational experiment shows that the proposed algorithms consistently perform the best and the scalability is improved as we use eigenpair approximation and stochastic singular value decomposition.     

DG-IMEX Stochastic Galerkin Schemes for Linear Transport Equation with Random Inputs and Diffusive Scalings

In this paper, we consider the linear transport equation under diffusive scaling and with random inputs. The method is based on the generalized polynomial chaos approach in the stochastic Galerkin framework. Several theoretical aspects will be addressed. A uniform numerical stability with respect to the Knudsen number \(\epsilon \), and a uniform in \(\epsilon \) error estimate is given. For temporal and spatial discretizations, we apply the implicit–explicit scheme under the micro–macro decomposition framework and the discontinuous Galerkin method, as proposed in Jang et al. (SIAM J Numer Anal 52:2048–2072, 2014) for deterministic problem. We provide a rigorous proof of the stochastic asymptotic-preserving (sAP) property. Extensive numerical experiments that validate the accuracy and sAP of the method are conducted.     

Weak Convergence of Finite Element Method for Stochastic Elastic Equation Driven By Additive Noise

In this paper we study the weak convergence of the semidiscrete and full discrete finite element methods for the stochastic elastic equation driven by additive noise, based on $C^0$ or $C^1$ piecewise polynomials. In order to simplify the analysis of weak convergence, we rewrite the stochastic elastic equation in an abstract problem and the solutions of the semidiscrete and full discrete problems in a unified form. We obtain that the weak order is twice the strong order, both in time and in space. Numerical experiments are carried out to verify the theoretical results.     

Three-dimensional stochastic modeling using sonar sensing for undersea robotics

This paper describes an approach to the construction of three-dimensional stochastic models for intelligent systems exploring an underwater environment. Important characteristics shared by such applications are: (1) real-time constraints; (2) unstructured, three-dimensional terrain; (3) high-bandwidth sensors providing redundant, overlapping coverage; (4) lack of prior knowledge about the environment; and (5) inherent inaccuracy or ambiguity in sensing and interpretation. The paper develops an underlying theory of stochastic backprojection and demonstrates how such an approach satisfies these five needs for undersea robotics.Models are cast as three-dimensional spatial decompositions of stochastic feature vectors. A numerical approach to incorporating new sensor information is derived from an incremental adaptation of the summation method for image reconstruction. Error and ambiguity are accounted for by blurring a spatial projection of remote-sensor data before combining them stochastically with the model. By exploiting the redundancy in high-bandwidth sensing, model certainty and resolution are enhanced as more data accumulate. In the case of a three-dimensional profiling sonar, the model converges to a fuzzy surface distribution from which a deterministic surface map is extracted.To verify the fundamental properties of stochastic backprojection and the resulting models, computer simulations are used to demonstrate: impulse and ramp responses; mitigation of artifacts caused by deterministic processing; incremental increase in accuracy and reduction of uncertainty; and convergence. Two examples illustrate how this approach has been successfully applied in the field for three-dimensional modeling of a sunken shipwreck by a remote undersea vehicle and for backscatter modeling of undersea terrain.     

Fractional Wishart processes and ε-fractional Wishart processes with applications

In this paper, we introduce two new matrix stochastic processes: fractional Wishart processes and $\epsilon$-fractional Wishart processes with integer indices which are based on the fractional Brownian motions and then extend $\epsilon$-fractional Wishart processes to the case with non-integer indices. Both processes include classic Wishart processes (if the Hurst index $H$ equals $\frac{1}{2}$) and present serial correlation of stochastic processes. Applying $\epsilon$-fractional Wishart processes to financial volatility theory, the financial models account for the stochastic volatilities of the assets and for the stochastic correlations not only between the underlying assets’ returns but also between their volatilities and for stochastic serial correlation of the relevant assets.     

A general scheme for log-determinant computation of matrices via stochastic polynomial approximation

We study the approximation of determinant for large scale matrices with low computational complexity. This paper develops a generalized stochastic polynomial approximation frame as well as a stochastic Legendre approximation algorithm to calculate log-determinants of large-scale positive definite matrices based on the prior eigenvalue distributions. The generalized frame is implemented by weighted $L_2$ orthogonal polynomial expansions with an efficient recursion formula and matrix–vector multiplications. So the proposed scheme is efficient both in computational complexity and data storage. Respective error bounds are given in theory which guarantee the convergence of the proposed algorithms. We illustrate the effectiveness of our method by numerical experiments on both synthetic matrices and counting spanning trees.     

Generation of singlet states with Rydberg blockade mechanism and driven by adiabatic passage

A single state is a special state that entangles multi-state quantum systems and plays a significant role in the field of quantum computation. In this paper, we propose a scheme to realize the generation of single states for Rydberg atoms, where one Rydberg atom is trapped in an optical potential and the others are trapped in an adjacent optical potential. Moreover, combining Rydberg blockade and adiabatic-passage technologies, an N-atom singlet state can be generated with the interaction of an N-dimensional Rydberg atom and an (\(N-1\))-atom singlet state. Compared to previous schemes, the advantage of our proposal is that an N-particle N-level singlet state with \(N\ge 3\) may be realized more simply.     

Robust H2/H∞ global linearization filter design for nonlinear stochastic time-varying delay systems

One can design a robust H_∞ filter for a general nonlinear stochastic system with external disturbance by solving a second-order nonlinear stochastic partial Hamilton-Jacobi inequality (HJI), which is difficult to be solved. In this paper, the robust mixed H₂/H_∞ globally linearized filter design problem is investigated for a general nonlinear stochastic time-varying delay system with external disturbance, where the state is governed by a stochastic Itô-type equation. Based on a globally linearized model, a stochastic bounded real lemma is established by the Lyapunov–Krasovskii functional theory, and the robust H_∞ globally linearized filter is designed by solving the simultaneous linear matrix inequalities instead of solving an HJI. For a given attenuation level, the H₂ globally linearized filtering problem with the worst case disturbance in the H_∞ filter case is known as the mixed H₂/H_∞ globally linearized filtering problem, which can be formulated as a linear programming problem with simultaneous LMI constraints. Therefore, this method is applicable for state estimation in nonlinear stochastic time-varying delay systems with unknown exogenous disturbance when state variables are unavailable. A simulation example is provided to illustrate the effectiveness of the proposed method.     

Comparison Between Reduced Basis and Stochastic Collocation Methods for Elliptic Problems

The stochastic collocation method (Babu?ka et al. in SIAM J Numer Anal 45(3):1005–1034, 2007; Nobile et al. in SIAM J Numer Anal 46(5):2411–2442, 2008a; SIAM J Numer Anal 46(5):2309–2345, 2008b; Xiu and Hesthaven in SIAM J Sci Comput 27(3):1118–1139, 2005) has recently been applied to stochastic problems that can be transformed into parametric systems. Meanwhile, the reduced basis method (Maday et al. in Comptes Rendus Mathematique 335(3):289–294, 2002; Patera and Rozza in Reduced basis approximation and a posteriori error estimation for parametrized partial differential equations Version 1.0. Copyright MIT, http://augustine.mit.edu, 2007; Rozza et al. in Arch Comput Methods Eng 15(3):229–275, 2008), primarily developed for solving parametric systems, has been recently used to deal with stochastic problems (Boyaval et al. in Comput Methods Appl Mech Eng 198(41–44):3187–3206, 2009; Arch Comput Methods Eng 17:435–454, 2010). In this work, we aim at comparing the performance of the two methods when applied to the solution of linear stochastic elliptic problems. Two important comparison criteria are considered: (1), convergence results of the approximation error; (2), computational costs for both offline construction and online evaluation. Numerical experiments are performed for problems from low dimensions $O(1)$ to moderate dimensions $O(10)$ and to high dimensions $O(100)$ . The main result stemming from our comparison is that the reduced basis method converges better in theory and faster in practice than the stochastic collocation method for smooth problems, and is more suitable for large scale and high dimensional stochastic problems when considering computational costs.