New least squares and singular value decomposition based methods for the estimation of the frequencies of complex sinusoids in white noise are presented. The methods are based on a new symmetric prediction problem tha...
详细信息
New least squares and singular value decomposition based methods for the estimation of the frequencies of complex sinusoids in white noise are presented. The methods are based on a new symmetric prediction problem that has some very useful properties leading to algorithms that have considerably reduced complexity. The new symmetric predictor is superior in performance as compared to the well known symmetric Smoother and has a performance comparable to other well known methods. Finally a new LS based method, which combines the new prediction technique with the FBLP method is proposed. This method performs slightly better than the FBLP offering at the same time a significant computational saving. As a by-product in the derivation of the new methods is the establishment of some useful properties concerning the eigenstructure of Hermitian and Persymmetric matrices.
The cycle-complete solution introduced by Trudeau (2012) is a solution concept for minimum cost spanning tree games and was proved to have desirable properties such as core-selection and sensitivity to change of the c...
详细信息
The cycle-complete solution introduced by Trudeau (2012) is a solution concept for minimum cost spanning tree games and was proved to have desirable properties such as core-selection and sensitivity to change of the cost function. The cycle-complete solution is defined as the Shapley value of the minimum cost spanning tree game associated with the subdominant cycle-complete cost function of a given cost function. In this study, we characterize subdominant cycle-complete cost functions and provide an O(n(2) log n) time algorithm for computing such functions, where n is the number of players. This algorithm leads to a new algorithm for computing the cycle-complete solution of a minimum cost spanning tree game with an O(n(2) log n) time bound. (C) 2017 Elsevier B.V. All rights reserved.
The complexity of the model checking problem for various fragments of fi rst-order logic (FO) has attracted much attention over the last two decades, in particular for the fragment induced by (sic) and Lambda and that...
详细信息
The complexity of the model checking problem for various fragments of fi rst-order logic (FO) has attracted much attention over the last two decades, in particular for the fragment induced by (sic) and Lambda and that induced by (sic), and Lambda, which are better known as the constraint satisfaction problem and the quantified constraint satisfaction problem, respectively. The former was conjectured to follow a dichotomy between P and NP-complete by Feder and Vardi [SIAM J. Comput., 28 (1998), pp. 57{104]. For the latter, there are several partial trichotomy results between P, NP-complete, and Pspace-complete, and Chen [Meditations on quantified constraint satisfaction, in Logic and Program Semantics, Springer, Heidelberg, 2012, pp. 35{49] ventured a conjecture regarding Pspace-completeness vs. membership in NP in the presence of constants. We give a comprehensive account of the whole fi eld of the complexity of model checking similar syntactic fragments of FO. The above two fragments are in fact the only ones for which there is currently no known complexity classi fi cation. Indeed, we consider all other similar syntactic fragments of FO, induced by the presence or absence of quanti fi ers and connectives, and fully classify the complexities of the parameterization of the model-checking problem by a fi nite model D, that is, the expression complexities for certain fi nite D. Perhaps surprisingly, we show that for most of these fragments, "tractability" is witnessed by a generic solving algorithm which uses quanti fi er relativization. Our classi fi cation methodology relies on tailoring suitably the algebraic approach pioneered by Jeavons, Cohen, and Gyssens [J. ACM, 44 (1997), pp. 527{548] for the constraint satisfaction problem and by Borner et al. [Inform. and Comput., 207 (2009), pp. 923{944] for the quanti fi ed constraint satisfaction problem. Most fragments under consideration can be relatively easily classi fi ed, either directly or using Schaefer's dichoto
This paper overviews the research investigations pertaining to stability and stabilization of control systems with time-delays. The prime focus is the fundamental results and recent progress in theory and applications...
详细信息
This paper overviews the research investigations pertaining to stability and stabilization of control systems with time-delays. The prime focus is the fundamental results and recent progress in theory and applications. The overviewsheds light on the contemporary development on the linear matrix inequality (LMI) techniques in deriving both delay-independent and delay-dependent stability results for time-delay systems. Particular emphases will be placed on issues concerned with the conservatism and the computational complexity of the results. Key technical bounding lemmas and slack variable introduction approaches will be presented. The results will be compared and connections of certain delay-dependent stability results are also discussed.
We investigate uninorm algebras satisfying a strong version of involutiveness. More precisely, we require that negation is an order reversing monoid isomorphism between the positive cone and the negative cone. A rathe...
详细信息
We investigate uninorm algebras satisfying a strong version of involutiveness. More precisely, we require that negation is an order reversing monoid isomorphism between the positive cone and the negative cone. A rather surprising consequence of this property is that the negative cones of these algebras are BL-algebras which do not admit MV-components with more than two elements. Among other things, we prove standard completeness and co-NP completeness of the logic corresponding to these algebras.
The Road Coloring Problem (RCP) originates in [1 ] and it was stated explicitly in the paper by Adler et al. [2]. It can be formulated as follows: let C be a strongly connected, constant out-degree finite digraph such...
详细信息
The Road Coloring Problem (RCP) originates in [1 ] and it was stated explicitly in the paper by Adler et al. [2]. It can be formulated as follows: let C be a strongly connected, constant out-degree finite digraph such that the greatest common divisor (gcd) of the lengths of all cycles in C equals 1. Is there an edge labeling, turning C into a deterministic finite synchronizing automaton? The problem is of great importance in automata theory, because the synchronizing property makes the automaton behavior resistant to errors that could occur in an input word: after the error is detected, the synchronizing word can reset the automaton to its initial state, as if there were no error. In this way we regain the control over automaton action.
Three-dimensional convolutions and correlations are used for three-dimensional image-processing applications. Their calculation involves extensive computation, which makes the use of fast transforms very advantageous....
详细信息
Three-dimensional convolutions and correlations are used for three-dimensional image-processing applications. Their calculation involves extensive computation, which makes the use of fast transforms very advantageous. As the number of arithmetic operations is very large, the accumulation of rounding or truncation errors arising in the use of the fast Fourier and Hartley transforms tends to increase. Number theoretic transforms are calculated module an integer and hence they are not subject to these errors. Recently a one-dimensional transform called the new Mersenne number transform (NMNT) was introduced and applied successfully to the calculation of 1-D convolutions/correlations. Unlike other Mersenne number transforms, the NMNT can handle long data sequences and has fast algorithms. In the paper, the 1-D definitions are first extended to the 3-D case in detail for use in 3-D image processing applications. The concept and derivation of the 3-D vector radix algorithm is then introduced for the fast calculation of the 3-D NMNT. The proposed algorithm is found to offer substantial savings over the row-column approach in terms of arithmetic operations. Examples are given showing the validity of both transform and algorithm.
The low hierarchy within NP and the extended low hierarchy have turned out to be very useful in classifying many interesting language classes. We relocate P/poly from the third Sigma-level EL(3)(P,Sigma) (Balcazar et ...
详细信息
The low hierarchy within NP and the extended low hierarchy have turned out to be very useful in classifying many interesting language classes. We relocate P/poly from the third Sigma-level EL(3)(P,Sigma) (Balcazar et al., 1986) to the third Theta-level EL(3)(P,Theta) of the extended low hierarchy. The location of P/poly in EL(3)(P,Theta) is optimal since, as shown by Allender and Hemachandra (1992), there exist sparse sets that are not contained in the next lower level EL(2)(P,Sigma). As a consequence of our result, all NP sets in P/poly are relocated from the third Sigma-level L(3)(P,Sigma) (Ko and Schoning, 1985) to the third Theta-level L(3)(P,Theta) of the low hierarchy.
We consider the problem of linear transceiver design to achieve max-min fairness in a downlink MIMO multicell network. This problem can be formulated as maximizing the minimum rate among all the users in an interferin...
详细信息
We consider the problem of linear transceiver design to achieve max-min fairness in a downlink MIMO multicell network. This problem can be formulated as maximizing the minimum rate among all the users in an interfering broadcast channel (IBC). In this paper we show that when the number of antennas is at least two at each of the transmitters and the receivers, the min rate maximization problem is NP-hard in the number of users. Moreover, we develop a low-complexity algorithm for this problem by iteratively solving a sequence of convex subproblems. We theoretically establish the global convergence of the proposed algorithm to the set of stationary points, which may be suboptimal due to the non-convexity of the original minimum rate maximization problem. Numerical simulations show that this algorithm is efficient in achieving fairness among all the users. (c) 2013 Elsevier B.V. All rights reserved.
A novel simplified multilevel space vector pulse-width modulation (SVM) scheme is proposed based on the two-level SVM. The voltage vectors with same amplitude and phase angle are applied to the various power units of ...
详细信息
A novel simplified multilevel space vector pulse-width modulation (SVM) scheme is proposed based on the two-level SVM. The voltage vectors with same amplitude and phase angle are applied to the various power units of cascaded multilevel inverter (CMLI), and the refresh times of various vectors are delayed in order, thus the corresponding multilevel output voltage waveform is formatted. During every sampling period, only the on-times of main and auxiliary voltage vectors of one-stage unit are calculated based on a two-level SVM algorithm, so the computational complexity is independent on the unit-cascaded number. Then the algorithm is simplified, and the expandability is enhanced. The simulation and experimental results prove the validity and feasibility of the novel scheme.
暂无评论