Search

An Algebraic Circuit for a multivariate polynomial P is a computational model for constructing the polynomial P using only additions and multiplications. It is a syntactic model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be easier to prove than lower bounds for Boolean circuits. Despite this, we do not have superpolynomial lower bounds against general algebraic circuits of depth 3 (except over constant-sized finite fields) and depth 4 (over any field other than F2), while constant-depth Boolean circuit lower bounds have been known since the early 1980s. In this paper, we prove the first superpolynomial lower bounds against algebraic circuits of all constant depths over all fields of characteristic 0. We also observe that our super-polynomial lower bound for constant-depth circuits implies the first deterministic sub-exponential time algorithm for solving the Polynomial Identity Testing (PIT) problem for all small-depth circuits using the known connection between algebraic hardness and randomness. [ABSTRACT FROM AUTHOR]

The paper studies digital redesign of linear time-invariant analog controllers under intermittent sampling. The sampling pattern is only assumed to be uniformly bounded, but otherwise irregular and unknown a priori. The contribution of the paper is twofold. First, it proposes a constructive algorithm to redesign any analog stabilizing controller so that the closed-loop stability is preserved. Second, it is shown that when applied to (sub) optimal \boldsymbolH^2 and \boldsymbolH^\infty controllers, the algorithm produces (sub) optimal sampled-data solutions under any a priori unknown sampling pattern. The proposed solutions are analytic, computationally simple, implementable, and transparent. Transparency pays off in showing the optimality, under a fixed sampling density, of uniform sampling for both performance measures studied. [ABSTRACT FROM AUTHOR]

Abstract In covering-based rough sets, many basic issues are related to minimal and maximal descriptions. For a covering approximation space with a large cardinal, it would be tedious and complicated to use set representations to solve the issues about minimal and maximal descriptions. Therefore it is necessary to study matrix representations by which calculations will become algorithmic and can be easily implemented by computers. In this paper, we use matrix approaches to investigate some issues about minimal and maximal descriptions in covering-based rough sets. Firstly, several new matrices and matrix operations are defined by which one can compute the minimal description and the approximation operator about the minimal description. Inspired by this result, a matrix method is presented to judge whether a covering is unary. Secondly, the maximal description and the approximation operator about the maximal description are also computed by these new matrices and matrix operations. Finally, based on the above results, we propose a matrix method to efficiently compute reductions of coverings. Moreover, we propose two types of reducts of covering information systems via minimal and maximal descriptions respectively, and we use matrix approaches to compute them. In a word, these results show an interesting view to investigate the combination between matrices and covering-based rough sets. [ABSTRACT FROM AUTHOR]

Abstract The benefits of automating design cycles for Bayesian inference-based algorithms are becoming increasingly recognized by the machine learning community. As a result, interest in probabilistic programming frameworks has much increased over the past few years. This paper explores a specific probabilistic programming paradigm, namely message passing in Forney-style factor graphs (FFGs), in the context of automated design of efficient Bayesian signal processing algorithms. To this end, we developed "ForneyLab" 2 as a Julia toolbox for message passing-based inference in FFGs. We show by example how ForneyLab enables automatic derivation of Bayesian signal processing algorithms, including algorithms for parameter estimation and model comparison. Crucially, due to the modular makeup of the FFG framework, both the model specification and inference methods are readily extensible in ForneyLab. In order to test this framework, we compared variational message passing as implemented by ForneyLab with automatic differentiation variational inference (ADVI) and Monte Carlo methods as implemented by state-of-the-art tools "Edward" and "Stan". In terms of performance, extensibility and stability issues, ForneyLab appears to enjoy an edge relative to its competitors for automated inference in state-space models. [ABSTRACT FROM AUTHOR]

Abstract In the research spectrum of rough set, the task of attribute reduction is obtaining a minimal attribute subset that preserves certain properties of the original data. Cost-sensitive attribute reduction aims at minimizing various types of costs. Approximate attribute reduction allows decision makers to leverage the advantages of knowledge discovery and their own preferences. This paper proposes the cost-sensitive approximate attribute reduction problem under both qualitative and quantitative criteria. The qualitative criterion refers to the indiscernibility, while the quantitative criterion refers to the approximate parameter ε and the cost. We present a framework based on three-way decisions and discernibility matrix to handle this new problem. First, a quality function for attribute subsets is designed with the interpretation of a hierarchical granular structure. Second, a fitness function is designed for cost performance index by investigating attribute significance. Third, three-way decision theory is applied to partition the attributes into three groups based on the fitness function and a threshold pair (α , β). Finally, deletion-based and addition-based cost-sensitive approximate reduction algorithms are designed under this framework. Experimental results indicate that our algorithms outperform the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

There are only a few learning algorithms applicable to stochastic dynamic teams and games which generalize Markov decision processes to decentralized stochastic control problems involving possibly self-interested decision makers. Learning in games is generally difficult because of the non-stationary environment in which each decision maker aims to learn its optimal decisions with minimal information in the presence of the other decision makers who are also learning. In stochastic dynamic games, learning is more challenging because, while learning, the decision makers alter the state of the system and hence the future cost. In this paper, we present decentralized Q-learning algorithms for stochastic games, and study their convergence for the weakly acyclic case which includes team problems as an important special case. The algorithms are decentralized in that each decision maker has access only to its own decisions and cost realizations as well as the state transitions; in particular, each decision maker is completely oblivious to the presence of the other decision makers. We show that these algorithms converge to equilibrium policies almost surely in large classes of stochastic games. [ABSTRACT FROM AUTHOR]

In this paper, a time-varying distributed convex optimization problem is studied for continuous-time multi-agent systems. The objective is to minimize the sum of local time-varying cost functions, each of which is known to only an individual agent, through local interaction. Here, the optimal point is time varying and creates an optimal trajectory. Control algorithms are designed for the cases of single-integrator and double-integrator dynamics. In both cases, a centralized approach is first introduced to solve the optimization problem. Then, this problem is solved in a distributed manner and a discontinuous algorithm based on the signum function is proposed in each case. In the case of single-integrator (respectively, double-integrator) dynamics, each agent relies only on its own position and the relative positions (respectively, positions and velocities) between itself and its neighbors. A gain adaption scheme is introduced in both algorithms to eliminate certain global information requirement. To relax the restricted assumption imposed on feasible cost functions, an estimator based algorithm using the signum function is proposed, where each agent uses dynamic average tracking as a tool to estimate the centralized control input. As a tradeoff, the estimator-based algorithm necessitates communication between neighbors. Then, in the case of double-integrator dynamics, the proposed algorithms are further extended. Two continuous algorithms based on, respectively, a time-varying and a fixed boundary layer are proposed as continuous approximations of the signum function. To account for interagent collision for physical agents, a distributed convex optimization problem with swarm tracking behavior is introduced for both single-integrator and double-integrator dynamics. It is shown that the center of the agents tracks the optimal trajectory, the connectivity of the agents is maintained, and interagent collision is avoided. [ABSTRACT FROM AUTHOR]

Diagnosability is an important property that determines at the design stage how accurate any diagnosis algorithm can be on a partially observable system and thus has significant economic impact on the improvement of performance and reliability of complex systems. Very recently distributed approaches for diagnosability began to be investigated since centralized approaches are not realistic for large systems due to the combinatorial explosion of the search space. In this paper, we propose a new optimized algorithm for pattern diagnosability analysis of distributed systems with modular structure, where we obtain the original pattern diagnosability information from the relative components before abstracting the sufficient and necessary information to be propagated to other connected components. Then, the diagnosability decision can be made after global consistency checking at the proper level of the subsystem involved. Our experimental results and complexity analysis illustrate the correctness and efficiency of our approach both in a practical and theoretical way. Finally, we distinguish our work by presenting related works before the conclusion. [ABSTRACT FROM AUTHOR]

How to propagate the label information from labeled examples to unlabeled examples is a critical problem for graph-based semisupervised learning. Many label propagation algorithms have been developed in recent years and have obtained promising performance on various applications. However, the eigenvalues of iteration matrices in these algorithms are usually distributed irregularly, which slow down the convergence rate and impair the learning performance. This paper proposes a novel label propagation method called Fick’s law assisted propagation (FLAP). Unlike the existing algorithms that are directly derived from statistical learning, FLAP is deduced on the basis of the theory of Fick’s First Law of Diffusion, which is widely known as the fundamental theory in fluid-spreading. We prove that FLAP will converge with linear rate and show that FLAP makes eigenvalues of the iteration matrix distributed regularly. Comprehensive experimental evaluations on synthetic and practical datasets reveal that FLAP obtains encouraging results in terms of both accuracy and efficiency. [ABSTRACT FROM AUTHOR]

Distance metric learning (DML) is successful in discovering intrinsic relations in data. However, most algorithms are computationally demanding when the problem size becomes large. In this paper, we propose a discriminative metric learning algorithm, develop a distributed scheme learning metrics on moderate-sized subsets of data, and aggregate the results into a global solution. The technique leverages the power of parallel computation. The algorithm of the aggregated DML (ADML) scales well with the data size and can be controlled by the partition. We theoretically analyze and provide bounds for the error induced by the distributed treatment. We have conducted experimental evaluation of the ADML, both on specially designed tests and on practical image annotation tasks. Those tests have shown that the ADML achieves the state-of-the-art performance at only a fraction of the cost incurred by most existing methods. [ABSTRACT FROM AUTHOR]

Sparse representations using learned dictionaries are being increasingly used with success in several data processing and machine learning applications. The increasing need for learning sparse models in large-scale applications motivates the development of efficient, robust, and provably good dictionary learning algorithms. Algorithmic stability and generalizability are desirable characteristics for dictionary learning algorithms that aim to build global dictionaries, which can efficiently model any test data similar to the training samples. In this paper, we propose an algorithm to learn dictionaries for sparse representations from large scale data, and prove that the proposed learning algorithm is stable and generalizable asymptotically. The algorithm employs a 1-D subspace clustering procedure, the $K$ -hyperline clustering, to learn a hierarchical dictionary with multiple levels. We also propose an information-theoretic scheme to estimate the number of atoms needed in each level of learning and develop an ensemble approach to learn robust dictionaries. Using the proposed dictionaries, the sparse code for novel test data can be computed using a low-complexity pursuit procedure. We demonstrate the stability and generalization characteristics of the proposed algorithm using simulations. We also evaluate the utility of the multilevel dictionaries in compressed recovery and subspace learning applications. [ABSTRACT FROM AUTHOR]

In practical iris applications, the obtained iris images are inevitably affected by noises brought by uneven illumination, off-angle view, eyelids, and eyelashes etc. Such influences can lead to poor accuracy and low efficiency of iris localization. This paper presents a novel conformal geometric algebra (CGA) based algorithm for accurate and fast iris localization. Firstly, two thresholds are obtained adaptively to convert the gray image into three-value image and Sobel edge detector is used to generate the edge points. Then an improved CGA-based circle detection algorithm is applied to detect the limbic and pupillary boundaries of the iris. Candidate boundaries are found with a priori knowledge of the eye structure. Finally, the CGA inner product is used to decide whether an edge point from candidate boundaries is on the circle or not. A defect ratio is defined to represent the completeness of each candidate boundary, and only those with the lowest defect ratio are set as the pupillary and limbic boundaries. Our algorithm detects candidate boundaries that satisfy a priori constraints rapidly and ensures the accuracy of iris localization. Experimental results on different datasets demonstrate the effectiveness and robustness of the algorithm. [ABSTRACT FROM AUTHOR]

The phase-response property for the bounded-input bounded-output (BIBO) stability of a two-dimensional (2-D) causal recursive digital allpass filter (DAF) with nonsymmetric half-plane (NSHP) support region is presented. Both cases of filters with real coefficients and complex coefficients are explored. Moreover, the effect of the numerator polynomial of a 2-D NSHP DAF on stability is also considered. The presented phase-response property has several applications. A remarkable application is that it can be utilized to enforce stability for a 2-D NSHP DAF design by choosing an appropriate phase specification. The eigenfilter design of 2-D NSHP DAFs for this application is also presented. Design examples are given to show these applications and the stability of a 2-D NSHP DAF is also inspected by the 2-D spectral factorization-based algorithm and a zeros-examining method presented by Ekstrom and Woods for confirmation. [ABSTRACT FROM AUTHOR]