Search

The control input derived from model predictive control (MPC) scheme depends on the receding horizon whose length needs to be determined. Design length is also a trade-off between computational complexity and optimization metrics. To this end, a framework for adaptive selection of the horizon length has been developed for discrete systems in previous works. In this paper, this framework is extended to continuous nonlinear systems. A new algorithm is presented to solve the problem of how to adaptively select the horizon length. Then, according to the traditional method and the robust MPC scheme based on tubes, the recursive feasibility and robustness of the algorithm (the adaptive horizon nonlinear model predictive control, called AH-NMPC) for quasi-infinite time domain adaptive horizontal continuous-time nonlinear systems are proved. Finally, the NMPC controller is used to perform path-tracking experiments on an autonomous vehicle to verify the good effects of the algorithm (AH-NMPC). [ABSTRACT FROM AUTHOR]

In recent years, the multitask diffusion least mean square (MD-LMS) algorithm has been extensively applied in distributed parameter estimation and target tracking of multitask network. However, its performance degrades under colored input signals or impulsive noises. To overcome these two drawbacks, this paper introduces the subband adaptive filter (SAF) into a multitask network for the first time, and a robust multitask diffusion normalized M-estimate subband adaptive filtering (MD-NMSAF) algorithm is proposed, which solves the global network optimization problem based on the modified Huber (MH) function in a distributed manner, achieves robustness to impulsive noise, and significantly improves the convergence performance of the MD-LMS algorithm. Compared with existing robust multitask diffusion affine projection algorithms (MD-APAs), the computational complexity of the proposed MD-NMSAF algorithm is greatly reduced. In addition, we analyze the mean and mean-square stability conditions of MD-NMSAF, provide theoretical models characterizing the network mean square deviation (MSD) behaviors of transient and steady-state, and further verify their correctness by computer simulations. Simulation results under different network topologies, input signals, filter lengths and impulsive noise types fully demonstrate the performance advantages of the proposed MD-NMSAF algorithm over its competitors in terms of steady-state estimation accuracy and convergence speed. [ABSTRACT FROM AUTHOR]

This paper solves the finite-time consensus problem for discrete time multi-agent systems (MASs) where agents update their values via linear iteration and the interactions between them are described by signed digraphs. A sufficient condition is presented that the agents can reach consensus on any given linear function of multiple initial signals in finite time, i.e., there exists an eventually positive Laplacian-based matrix associated with the underlying graph. We prove that the linear iterative framework "ratio consensus" developed for unsigned graphs in the literature can be extended to the computation for signed graphs with appropriate modifications. Our method weakens the limitation of the iterative framework on the "marginal Schur stability" of the weight matrix without increasing the computational complexity. Reaching average consensus on unsigned graphs as in the literature is regarded as a special case of our algorithm. Two illustrative examples are presented to demonstrate the correctness of the proposed results. [ABSTRACT FROM AUTHOR]

• A kernel-based feature selection algorithm is proposed, based on primary normalized cross-covariance operator (NOCCO). • A fast version is implemented via combining approximated NOCCO with column recursive method for Moore-Penrose inverse matrix. • Their effectiveness and efficiency are validated using detailed experimental comparison and analysis for nine benchmark data sets. Supervised feature selection (FS) for classification aims at finding a more discriminative subset from original features, to facilitate classifier training, improve classification performance and enhance model interpretability. Primary normalized cross-covariance operator (NOCCO) is a nonlinear kernel-based dependency measure between features and labels, including two inverse matrices, and its approximated version (ANOCCO) is simplified via exploiting linear kernel for features, delta kernel for labels and Moore–Penrose inverse. In this paper, we apply NOCCO and ANOCCO to FS task. According to sequential forward selection, a forward NOCCO-based FS algorithm (i.e., FoNOCCO) is directly implemented via various accelerating strategies, but its computational complexity is extremely high. To this end, we propose its fast version via maximizing ANOCCO (i.e., FoANOCCO), where each candidate feature is evaluated efficiently according to column recursive algorithm for Moore–Penrose inverse. Theoretical analysis shows that evaluating a candidate feature needs a time complexity of O (N 2) in FoANOCCO and O (N 3) in FoNOCCO, where N is the number of instances. On eight small-size high-dimensional benchmark data sets, our detailed experiments illustrate that our two forward FS algorithms are superior to six state-of-the-art FS methods with four baseline classifiers, and FoANOCCO runs 70 times faster than FoNOCCO with a 1.79 % accuracy drop. [ABSTRACT FROM AUTHOR]

This paper proposes two kinds of algorithms to achieve privacy-preserving consensus of multi-agent systems over undirected graphs via node decomposition mechanism and homomorphic cryptography technique. Based on the number of neighboring nodes (|Ni|), every agent is decomposed into |Ni| subagents, which are connected as a chain graph. Note that every subagent connects one and only one non-homologous subagent (generated by different agents). Information interaction between non-homologous subagents is encrypted by a homomorphic cryptography algorithm, and homologous subagents exchange information directly. In this regard, the proposed node decomposition mechanism enhances the privacy of the initial values without increasing the computational complexity of encryption. The first privacy-preserving algorithm can achieve the accurate average consensus, which means that the agreement value of every subagent is consistent with the original average consensus value. The second algorithm studies the privacy-preserving scaled consensus problem without a priori knowledge about the underlying graph. Although the final convergence values of subagents do not keep exactly the same, homologous subagents can compute the original group decision value by resorting to the product of the limit value and agent’s degree. Importantly, this algorithm also guarantees the privacy of group decision value of the whole system. Besides, it is proved that the privacy of the initial value can be preserved if the agent has at least one neutral neighbor. [ABSTRACT FROM AUTHOR]

As a blind equalization algorithm, the fractional lower-order statistics based multimodulus algorithm (FLOS-MMA) is suitable for equalizing multilevel quadrature amplitude modulation (QAM) signals in impulsive noise. However, the equalization performance of FLOS-MMA is severely degraded in strong impulsive noise because the first-order gradient of the cost function constrains the ability of FLOS to suppress large outliers in the equalizer output signal and is sensitive to large outliers in the equalizer input signal. To enhance the robustness of multimodulus blind equalization algorithm against impulsive noise, a FLOS based momentum fractional-order multimodulus algorithm (FLOS-MFOMMA) is proposed in this paper. The proposed algorithm mitigates the adverse effects of impulsive noise on the updating of equalizer coefficients by utilizing the fractional-order gradient and accelerates the convergence speed by incorporating a momentum term. Then, the steady-state excess mean square error and the computational complexity of FLOS-MFOMMA are analyzed theoretically. Finally, numerical simulations, for equalizing 16-QAM signals under impulsive noise environments, show that the proposed algorithm is superior to FLOS-MMA in terms of robustness and convergence speed. [ABSTRACT FROM AUTHOR]

This paper addresses a general method for parameter identification in distributed parameter systems (DPSs) based on a reference model and measurement information. Moreover, the developed identification method is used to deal with secure communication problems. Firstly, in combination with the historical information measured by sensors, an iterative approach based on an approximator is put forward. Meanwhile, an execution scheme for the iterative approach is provided by an optimization policy. Subsequently, by bringing new mechanisms into quantum particle swarm optimization (QPSO) algorithm to enhance its search capability, we propose quantum-leading-following-based optimization (QLFBO) algorithm, which serves the optimization policy. Further, the global convergence for QLFBO algorithm is proved combined with the parameter identification problem of DPSs, and the computational complexity on this algorithm is discussed in detail. Finally, simulation experiments on the diffusion-reaction model are carried out by the iterative approach based on QLFBO algorithm under different measurement ways. Simultaneously, secure communication depending on this model is performed in the double-scroll Chua’s circuit and a lotus image via the investigated iterative strategy and encryption-decryption scheme. Simulation results verify the validity and practicability of the developed method. [ABSTRACT FROM AUTHOR]

This paper presents a novel tensor completion method based on row-wise Hankel transformation for wireless missing data recovery problems. The received wireless data is modeled as a three-way tensor according to its time, space, and sensing information dimensions, which allows the proposed approach to fully capture the hidden space correlation and multi-attribute information of the received data. Furthermore, the wireless data recovery problem can be formulated as a simple core nuclear norm tensor completion problem based on Tucker decomposition, so that the computational complexity can be reduced. Furthermore, a Hankel transformation is introduced to enrich the structure of the core tensor, so that the new core tensor structure can exploit the underlying structure of tensor data to capture multiple correlations for data recovery. Hence, the recovery performance can be further improved. The proposed method offers significant advantages over the Tucker-based tensor completion methods. For example, (1) theoretical analysis shows that the proposed method has a lower computational complexity; (2) compared with the existing methods, it has better recovery performance even with a larger missing ratio or lower signal-to-noise ratio (SNR) scenario, etc. Simulation results demonstrate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper considers the problem of learning the unknown structure of a network with the underlying topology given by a polyforest (a collection of directed trees with potentially multiple roots). The main result is an algorithm that consistently learns the network structure using only second-order statistics of the data. The methodology is robust with respect to the presence of unmeasured (latent) nodes: the algorithm detects the exact number and location of the latent nodes, when they satisfy specific degree conditions in the actual network graph. It is shown that the same degree conditions are also necessary for a consistent reconstruction. Thus, the proposed reconstruction algorithm achieves the fundamental limitations in learning the structure of a polyforest network of linear dynamic systems in the presence of latent nodes. This paper overcomes the limitations of previous results that only addressed single-rooted trees, tackling the problem in an efficient way since the computational complexity of the derived algorithm is proven to be polynomial in the number of observed nodes. [ABSTRACT FROM AUTHOR]

Nonlinear adaptive filters, such as Volterra and functional link adaptive filter (FLAF), face increased computational complexity with rising input dimensionality or expansion order. To enhance computational efficiency, this paper introduces a nonlinear adaptive algorithm based on Rectified Linear Unit (ReLU). Applying ReLU to a tonal signal generates components corresponding to the original frequency and even harmonics. Additionally, applying ReLU to the sum of two tonal signals yields a spectrum encompassing intermodulation distortion frequencies. These traits enable the algorithm to mitigate harmonic and intermodulation distortions while maintaining judicious computational complexity. The numerical simulation results for the identification of nonlinear systems validate the algorithm's ability to fit harmonic and intermodulation nonlinear distortions. In simulations of nonlinear echo cancellation with diverse test signals and various distortion models, our proposed algorithm consistently demonstrates competitive performance, notably excelling in music and speech scenarios. [ABSTRACT FROM AUTHOR]

Aiming the extract micro-motion features of rotor targets when the flashes are in the echo, this paper proposes a method based on the GS-IRadon algorithm. At first, we analyze the time-frequency characteristics of rotor targets through a scattering point signal model. Then, we analyze and study the usage conditions of the algorithm and use the Moving Target Indication (MTI) algorithm to remove the direct-current (DC) frequency component in signal's time-frequency results. Finally, we utilize the Inverse Radon transform algorithm based on the golden section method (GS-IRadon) to extract the target micro-motion features. The estimation of speed, length, and number of blades in the presence of flashes phenomenon in rotor targets was achieved. Simulation results showed that the algorithm can significantly reduce computational complexity while maintaining high estimation accuracy and has a more stable performance than regular algorithms. [ABSTRACT FROM AUTHOR]

The prediction-error expansion (PEE) based reversible data hiding (RDH) methods mainly contain two steps: prediction-error histogram (PEH) generation and PEH modification. Multiple histograms modification (MHM) and pairwise PEE are two efficient methods used in PEH modification, which can greatly reduce the distortion to the cover image under given payloads. However, these two effective methods are not used together for their conflict on causality and large computational complexity. To address the above two problems, in this paper, a group of non-causal predictors with a specially designed complexity metric are proposed so that the conflict on causality is resolved. Then, the original optimization problem to determine the parameters of MHM and pairwise PEE is decomposed into two easier ones, which are addressed by a step-by-step optimization. Several efficient constraints are used to narrow the search range for the optimal parameters while minimizing the performance degradation. As a result, the proposed method can obtain high quality on the embedded images, that is, the average PSNR of the 8 standard 512 × 512 sized grayscale images from the USC-SIPI image database can reach 60.43 dB for the payload of 10,000 bits, while the running time for the proposed algorithm is acceptable. Experimental results show that the proposed method outperforms many kinds of RDH schemes, and achieves an obvious increment in fidelity over a series of state-of-the-art RDH schemes. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to derive cubature formulas using bivariate degree-graded alternative shifted Jacobi polynomials and present some of their applications through a method for fast and explicit construction of operational integration matrices in this polynomial basis. First, we take the non-degree-graded alternative shifted Jacobi polynomial basis over the interval [ 0 , 1 ] and introduce a corresponding degree-graded polynomial basis. We then construct sparse and well-structured operational integration matrices in that basis. The main advantage of the proposed idea is the low computational complexity which is derived through vector–matrix multiplications without change of bases. As an application, a fast and accurate numerical algorithm based on the obtained cubature formula is developed for the approximate solution of nonlinear multi-dimensional integral equations which arise in the theory of nonlinear parabolic boundary value problems as well as the mathematical modeling of the spatio-temporal development of an epidemic. It is shown that such a matrix representation of cubature formula in terms of the bivariate degree-graded basis gives an approximate solution with a higher order accuracy. The experimental results also illustrate that smaller size and lower orders of the operational matrix and basis functions can obtain a favorable approximate solution. [ABSTRACT FROM AUTHOR]

Dynamic Bayesian networks have been well explored in the literature as discrete-time models: however, their continuous-time extensions have seen comparatively little attention. In this paper, we propose the first implementation of a constraint-based algorithm for learning the structure of continuous-time Bayesian networks. We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence. Furthermore, we analyze and discuss the computational complexity of the best and worst cases for the proposed algorithm. Finally, we validate its performance using synthetic data, and we discuss its strengths and limitations comparing it with the score-based structure learning algorithm from Nodelman et al. [23]. We find the latter to be more accurate in learning networks with binary variables, while our constraint-based approach is more accurate with variables assuming more than two values. Numerical experiments confirm that score-based and constraint-based algorithms are comparable in terms of computation time. [ABSTRACT FROM AUTHOR]

The data clustering problem can be described as the task of organizing data into groups, where in each group the objects share some similar attributes. Most of the problems clustering algorithms address do not have a prior solution. This paper addresses the algorithm selection challenge for data clustering, while taking the difficulty in evaluating clustering solutions into account. We present a new meta-learning method for recommending the most suitable clustering algorithm for a dataset. Based on concepts from the isolation forest algorithm, we propose a new similarity measure between datasets. Our proposed dataset characterization methods generate an embedding for a dataset using this similarity measure, which is then used to improve the quality of the problem's characterization. The method utilizes landmarking concepts to characterize the dataset and then, inspired by the DeepFM algorithm, applies meta-learning to rank the candidate algorithms that are expected to perform the best for the current dataset. This ranking could, among other things, support AutoML systems. Our approach is evaluated on a corpus of 100 publicly available benchmark datasets. We compare our method's ranking performance to that of existing meta-learning methods and show the dominance of our method in terms of predictive performance and computational complexity. [ABSTRACT FROM AUTHOR]

In this paper, we formulate and prove new results in the context of storage functions for lossless systems: we use these results to propose new algorithms to compute the storage function. The computation of the storage function for the lossless case is not possible using conventional algebraic Riccati equation-based algorithms, though the storage function itself is well-defined. This is because a certain “regularity condition” on the feedthrough term in the i/s/o representation of the lossless system does not hold. We formulate new results about the storage function matrix for the lossless case and use them to propose non-iterative and stable algorithms to compute the storage function directly from different representations of the given system, namely, a kernel representation, transfer function, and the i/s/o representation of the system. Across the methods, for randomly generated transfer functions, we compare: 1) the computational effort (in flops); 2) the computation time using numerical experiments; and 3) the computational error. [ABSTRACT FROM AUTHOR]

Highlights • In this paper, we focus on the recursive least-squares algorithm for bilinear forms, i.e., RLS-BF. • The bilinear term is defined with respect to the impulse responses of a spatiotemporal model. • Low-complexity versions of the RLS-BF algorithm are proposed, based on the DCD method. • A robust variable-regularized RLS-BF (VR-RLS-BF) algorithm is developed, using an estimate of the SNR. • Low-complexity versions of the VR-RLS-BF algorithm are derived, involving the DCD method. Abstract Due to its fast convergence rate, the recursive least-squares (RLS) algorithm is very popular in many applications of adaptive filtering, including system identification scenarios. However, the computational complexity of this algorithm represents a major limitation in applications that involve long filters. Moreover, when the parameter space becomes large, the system identification problem is more challenging and the adaptive filters should be able to cope with this aspect. In this paper, we focus on the identification of bilinear forms, where the bilinear term is defined with respect to the impulse responses of a spatiotemporal model. From this perspective, the solution requires a multidimensional adaptive filtering technique. Recently, the RLS algorithm tailored for bilinear forms (namely RLS-BF) was developed for this purpose. In this framework, the contribution of this paper is mainly twofold. First, in order to reduce the computational complexity of the RLS-BF algorithm, two versions based on the dichotomous coordinate descent (DCD) method are proposed; due to its arithmetic features, the DCD algorithm represents one of the most attractive alternatives to solve the normal equations. However, in the bilinear context, we need to consider the particular structure of the input data and the additional related challenges. Second, in order to improve the robustness of the RLS-BF algorithm in noisy environments, a regularized version is developed, together with a method to find the regularization parameters, which are related to the signal-to-noise ratio (SNR). Furthermore, using a proper estimation of the SNR, a variable-regularized RLS-BF algorithm is designed and two DCD-based low-complexity versions are proposed. Due to their nature, these variable-regularized algorithms have good robustness features against additive noise, which make them behave well in different noisy condition scenarios. Simulation results indicate the good performance of the proposed low-complexity RLS-BF algorithms, with appealing features for practical implementations. [ABSTRACT FROM AUTHOR]

This paper provides performance results using the SPERRY UNIVAC 1100 Series linear programming product FMPS to solve a set of 16 real-world linear programming problems. As such, this paper provides a data point for the actual performance of a commercial simplex algorithm on real-world linear programming problems and shows that the simplex algorithm is a linear time algorithm in actual performance. Correlations and performance relationships not previously available are also provided. [ABSTRACT FROM AUTHOR]

Feature combination selection is used in object classification to select complementary features that can produce a powerful combination. One active area of selecting feature combinations is genome-wide association studies (GWAS). However, selecting feature combinations from high-dimensional GWAS data faces a serious issue of high computational complexity. In this paper, a fast evolutionary optimization method named search-history-guided differential evolution (HGDE) is proposed to deal with the problem. This method applies the search history memorized in a binary space partitioning tree to enhance its power for selecting feature combinations. We perform a comparative study on the proposed HGDE algorithm and other state-of-the-art algorithms using synthetic datasets, and later employ the HGDE algorithm in experiments on a real age-related macular degeneration dataset. The experimental results show that this proposed algorithm has superior performance in the selection of feature combinations. Moreover, the results provide a reference for studying the functional mechanisms of age-related macular degeneration. [ABSTRACT FROM AUTHOR]

Hypergraph is popularly used for describing multi-relationships among objects in a unified manner, and spectral clustering is regarded as one of the most effective algorithms for partitioning those objects (vertices) into different communities. However, the traditional spectral clustering for hypergraph (HC) incurs expensive costs in terms of both time and space. In this paper, we propose a framework called GraphLSHC to tackle the scalability problem faced by the large scale hypergraph spectral clustering. In our solution, the hypergraph used in GraphLSHC is expanded into a general format to capture complicated higher-order relationships. Moreover, GraphLSHC is capable to simultaneously partition both vertices and hyperedges according to the "eigen-trick", which provides an approach for reducing the computational complexity of the clustering. To improve the performance further, several hyperedge-based sampling techniques are proposed, which can supplement the sampled matrix with the whole graph information. We also give a theoretical guarantee for the error boundary of the supplement. Several experiments show the superiority of the proposed framework over the state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Feature selection as an essential preprocessing step in multilabel classification has been widely researched. Due to the diversity and complexity of multilabel datasets, some feature selection methods are unstable and yield low predictive accuracy. To address these issues, this paper presents a novel multilabel feature selection method using multilabel ReliefF (ML-ReliefF) and neighborhood mutual information in multilabel neighborhood decision systems. First, to solve the problem of the few available randomly selected samples when searching the nearest samples in ReliefF, the coefficient of difference and the average distance among the nearest similar and heterogeneous samples are introduced to evaluate the differences among the samples, and then the average differences among the similar or heterogeneous samples are defined. Using the Jaccard correlation coefficient, a new formula for updating feature weights is presented. Second, the margin of the sample is studied to granulate all samples under each label, and the concept of the neighborhood is given. By combining algebra with information views, some neighborhood entropy-based uncertainty measures for multilabel classification are investigated, and new neighborhood mutual information is proposed. Furthermore, an optimization objective function is constructed to evaluate the candidate features in multilabel neighborhood decision systems, all the properties are discussed, and the relationships of these measures are established. Finally, an improved ML-ReliefF algorithm is designed for preliminarily eliminating unrelated features to decrease the computational complexity for multilabel classification, and a heuristic forward multilabel feature selection algorithm is developed to remove redundant features and improve classification performance. Experimental results conducted on thirteen multilabel datasets to verify the effectiveness of the proposed algorithms in multilabel neighborhood decision systems are compared with representative methods. [ABSTRACT FROM AUTHOR]

Multi-view clustering aims at integrating the complementary information between different views so as to obtain an accurate clustering result. In addition, the traditional clustering is a kind of unsupervised learning method, which does not take the label information into learning. In this paper, we propose a novel model, called semi-supervised multi-view clustering based on orthonormality-constrained nonnegative matrix factorization (MVOCNMF), to cluster the multi-view data into a number of categories. In the proposed model, based on the label information, we first learn the low-dimensional representations of data by the constrained NMF technique, and simultaneously cluster the samples with the same label into the clustering prototypes for each view. After that, we put forward a novel orthonormality constraint term to obtain the desirable representations for each view, and use the co-regularization to integrate the complementary information from different views. We further develop an alternating minimization algorithm to solve the proposed model, and present the convergence analysis and computational complexity of the proposed method. Extensive experimental results on several multi-view datasets have shown that the proposed MVOCNMF method outperforms the existing multi-view clustering methods. [ABSTRACT FROM AUTHOR]

Stereo vision is a methodology to obtain depth in a scene based on the stereo image pair. In this paper, we introduce a discrete wavelet transform (DWT)-based methodology for a state-of-the-art disparity estimation algorithm that resulted in significant performance improvement in terms of speed and computational complexity. In the initial stage of the proposed algorithm, we apply DWT to the input images, reducing the number of samples to be processed in subsequent stages by 50%, thereby decreasing computational complexity and improving processing speed. Subsequently, the architecture has been designed based on this proposed methodology and prototyped on a Xilinx Virtex-7 FPGA. The performance of the proposed methodology has been evaluated against four standard Middlebury Benchmark image pairs viz. Tsukuba, Venus, Teddy, and Cones. The proposed methodology results in the improvement of about 44.4% cycles per frame, 52% frames/s, and 61.5% and 59.6% LUT and register utilization, respectively, compared with state-of-the-art designs. [ABSTRACT FROM PUBLISHER]

This paper presents a family of robust set-membership normalized subband adaptive filtering (RSM-NSAF) algorithms for acoustic echo cancellation (AEC). By using a new robust set-membership error bound, the RSM-NSAF algorithm obtains improved robustness against impulsive noises and decreased steady-state misalignment relative to the conventional set-membership NSAF (SM-NSAF) algorithm. To exploit the sparsity of the impulse response, the L0 norm constraint robust set-membership NSAF ( L0 -RSM-NSAF), robust set-membership improved proportionate NSAF (RSM-IPNSAF), and L0 norm constraint robust set-membership improved proportionate NSAF ( L0 -RSM-IPNSAF) algorithms are derived by minimizing a differentiable cost function that utilizes the Riemannian distance between the updated and previous weight vectors as well as the L0 norm of the weighted updated weight vector. Simulations in AEC application confirm the improvements of the proposed algorithms in performance. [ABSTRACT FROM PUBLISHER]

We investigate the problem of synthesizing dynamic masks that preserve the infinite-step opacity in the context of discrete-event systems. Dynamic mask is an information acquisition mechanism that controls the observability of the system's events dynamically online, e.g., by turning sensors on/off. A system equipped with a dynamic mask is said to be infinite-step opaque if an outside intruder that can access all acquired information can never infer that the system was at some secret state for any specific previous instant. Existing works on the dynamic mask synthesis problem can only preserve the current-state opacity. However, synthesizing dynamic masks for the infinite-step opacity, which is stronger than the current-state opacity, is much more challenging. The main reason is that the delayed information is involved in this problem and whether or not a current secret can be revealed depends on sensing decisions to be synthesized in the future. In this paper, a new type of information state is proposed to capture all the delayed information in the infinite-step opacity synthesis problem. An effective algorithm is then presented to solve the synthesis problem, which extends existing dynamic mask synthesis techniques from the current-state opacity to infinite-step opacity. Additionally, an information-state-reduction-based approach is proposed to further mitigate the computational complexity of the synthesis procedure. Finally, we discuss how to generalize our results to a class properties with delayed information including infinite-step $K$ -anonymity and infinite-step indistinguishability. [ABSTRACT FROM AUTHOR]

The traversal search of multi-dimensional parameter during the process of hypersonic target echo signal coherent integration, leads to the problem of large amounts of calculation and poor real-time performance. In view of these problems, a modified polynomial Radon-polynomial Fourier transform (MPRPFT) hypersonic target coherent integration detection algorithm based on Doppler feedback is proposed in this paper. Firstly, the Doppler estimation value of the target is obtained by using the target point information obtained by subsequent non-coherent integration detection. Then, the feedback adjustment of the coherent integration process is performed by using the acquired target Doppler estimation value. Finally, the coherent integration is completed after adjusting the search interval of compensation. The simulation results show that the algorithm can effectively reduce the computational complexity and improve the real-time performance on the basis of the effective coherent integration of hypersonic target echo signals. [ABSTRACT FROM AUTHOR]

This paper takes further insight into the sparse geometry which offers a larger array aperture than uniform linear array (ULA) with the same number of physical sensors. An efficient method based on closed-form robust Chinese remainder theorem (CFRCRT) is presented to estimate the direction of arrival (DOA) from their wrapped phase with permissible errors. The proposed algorithm has significantly less computational complexity than the searching method while maintaining similar estimation precision. Furthermore, we combine all phase discrete Fourier transfer (APDFT) and the CFRCRT algorithm to achieve a considerably high DOA estimation precision. Both the theoretical analysis and simulation results demonstrate that the proposed algorithm has a higher estimation precision as well as lower computation complexity. [ABSTRACT FROM AUTHOR]

• Based on tensor and matrix decomposition, a theoretical framework of multiscale co-clustering is proposed to extract coherent patterns along all modes of a tensor. • An alternative algorithm for tensor canonical decomposition with full-rank constraint on slice-wise factorization (FRSF) is developed to reduces the computational complexity. • A flexible and fast FRSF-based co-clustering algorithm is formulated. The analysis of tensor data is necessary in many applications. Similar to bi-clustering of matrix data, multiscale co-clustering can simultaneously extract coherent patterns along all or partial modes of a tensor. However, numerical methods for co-clustering have not reached the level of maturity of bi-clustering. In this paper, we present a theoretical framework to perform co-clustering for multidimensional data based on tensor and matrix decomposition. According to the proposed principle, we first develop an alternative algorithm for tensor canonical decomposition with full-rank constraint on slice-wise factorization (FRSF). Owing to the least squares principle and the constraint inherent in the resolution of multidimensional data, FRSF provides a natural way to avoid two-factor degeneracy and renders the resolved profiles stable with respect to high dimensionality. FRSF maintains a high convergence rate and greatly reduces the computational complexity with the compression technique based on matrix singular value decomposition. Furthermore, the algebraic expression of co-clusters in tensor data can be mapped to some linear structures in the factor spaces of FRSF. We employ a linear grouping algorithm to identify these geometrical patterns in the factor spaces. Finally, the combination of the linear grouping points along every mode successfully supports the detection of co-clusters in tensor data. On the basis of the proposed framework, a flexible and fast FRSF-based co-clustering algorithm is developed. Extensive simulations and experiment data analysis demonstrate the validity and efficiency of FRSF and the proposed co-clustering algorithm. [ABSTRACT FROM AUTHOR]

The article refers to a 1971 research paper by Steve Cook, "The Complexity of Theorem-Proving Procedures" and focuses on computational complexity. The Polynomial Time (P) versus Nondeterministic Polynomial-Time (NP) problem in computer science is discussed, as well as the theory of efficient algorithms for a solution to NP-complete problems. Integer programming, approaches to proving that P≠NP such as diagonalization, circuit and proof complexity with Boolean operators, brute force and heuristics, NP-complete optimization and the limits of approximation, hardness assumptions in cryptography, and the elimination of randomness are mentioned.

Influence Maximization (IM) is a key algorithmic problem that has been extensively studied in social influence analysis, but most of existing researches either make sacrifices in solution accuracy or suffer high computational complexity. In this paper, we propose a new Community-based Influence Maximization (CIM) algorithm for identifying a set of seed spreaders in a social network to maximize the expected number of influenced nodes. In CIM, the initial candidate seeds are first selected based on the proposed topological potential "peak-slope-valley" structure framework. Then, we propose a recursive clustering approach and a similarity indicator based on local resource allocation to partition communities. Finally, we design a community-based regional influence indicator to select seed nodes without using any prior knowledge. Experiment datasets include three artificial benchmarks with varying community strengths, as well as nine representative networks drawn from various fields. Extensive numerical simulations on both artificial and real networks indicate that (i) community-based techniques enrich the toolbox for addressing the IM problem and (ii) the derivative algorithm outperforms recent high-performing influence maximization algorithms in terms of influence propagation and coverage redundancy of the seed set with an acceptable complexity. Furthermore, our algorithm exhibits good stability on networks of varying scales and structural characteristics. • A new algorithm is proposed to further enrich the toolbox for influence maximization. • A topological potential "peak-slope-valley" structure is proposed to identify local communities. • This study uses a proposed recursive clustering approach to identify community partition. • Experiments show that this work is an effective and efficient influence maximization algorithm. [ABSTRACT FROM AUTHOR]

This note presents further results based on the recent paper [J. Liang, H. Chen, and J. Lam, “An improved criterion for controllability of Boolean control networks,” IEEE Trans. Autom. Control, vol. 62, no. 11, pp. 6012–6018, Nov. 2017]. After some optimizations, the conventional method can be more efficient than the method used in the above paper. We also propose an improved method via combining the well known Tarjan's algorithm and depth-first search technique for the controllability analysis of Boolean control networks (BCNs). As a result, the computational complexity will not exceed $O(N^2)$ with $N=2^n$ , where $n$ is the number of state-variables in a BCN. [ABSTRACT FROM AUTHOR]

Highlights • A Quick Inclusion-Exclusion (QIE) technique is proposed. • The proposed QIE is for multi-state flow network reliability problems. • The proposed QIE is easy to code and only needs one comparision in each (intersection) term. • The proposed QIE is simpler than the traditional IE. • The proposed QIE is faster than the RSDP which is the most popular sum-of-disjoint product method. Abstract The reliability of modern information systems modeled as multi-state flow networks (MFNs) is a crucial concern the planning, design and control of these systems. The inclusion-exclusion technique (IET) is a popular tool for assessing MFN reliability because it is simple and easily understood. However, it is less efficient than other methods, like the sum-of-disjoint product method (SDP), for example. This paper proposes a new IET, called the Quick Inclusion-Exclusion technique (QIE) to increase the efficiency of the IET and reduce the amount of memory required in MFNs. The correctness and the time complexity of QIE is analyzed and proven. An MFN reliability example is implemented to illustrate the proposed QIE. In order to demonstrate its performance, the proposed QIE is compared with the most popular SDP, the recursive SDP (RSDP) in 20 benchmark networks taken from the literature. Numerical examples demonstrate that the proposed QIE outperforms RSDP in terms of both efficiency and memory use. This result differs significantly from those obtained by traditional methods. [ABSTRACT FROM AUTHOR]

Abstract The affine projection (AP) algorithm is one of the most celebrated adaptive filtering algorithms, and it achieves a good tradeoff between the convergence rate and computational complexity. However, the complexity of the AP algorithm increases with the projection order. A wealth of fast AP algorithms have been proposed to reduce the complexity in the last two decades. However, those low-complexity methods have not been well analyzed and compared. To fill this gap, this paper reviews the fast AP algorithms, including both fast filtering approaches and efficient solutions of the linear system of equations. The advantages and disadvantages of each fast implementation version are clarified based on an extensive performance evaluation, which could be useful to engineers when selecting a suitable algorithm for their specific applications and could also be a starting point for experts in this field to develop better solutions. [ABSTRACT FROM AUTHOR]

Unmanned aerial vehicles (UAVs) may play an important role in data collection and offloading in vast areas deploying wireless sensor networks, and the UAV's action strategy has a vital influence on achieving applicability and computational complexity. Dynamic programming (DP) has a good application in the path planning of UAV, but there are problems in the applicability of special terrain environment and the complexity of the algorithm. Based on the analysis of DP, this paper proposes a hierarchical directional DP (DDP) algorithm based on direction determination and hierarchical model. We compare our methods with Q-learning and DP algorithm by experiments, and the results show that our method can improve the terrain applicability, meanwhile greatly reduce the computational complexity. [ABSTRACT FROM AUTHOR]

This paper extends the application of compressive sensing (CS) to the radar reconnaissance receiver for receiving the multi-narrowband signal. By combining the concept of the block sparsity, the self-adaption methods, the binary tree search, and the residual monitoring mechanism, two adaptive block greedy algorithms are proposed to achieve a high probability adaptive reconstruction. The use of the block sparsity can greatly improve the efficiency of the support selection and reduce the lower boundary of the sub-sampling rate. Furthermore, the addition of binary tree search and monitoring mechanism with two different supports self-adaption methods overcome the instability caused by the fixed block length while optimizing the recovery of the unknown signal. The simulations and analysis of the adaptive reconstruction ability and theoretical computational complexity are given. Also, we verify the feasibility and effectiveness of the two algorithms by the experiments of receiving multi-narrowband signals on an analogto- information converter (AIC). Finally, an optimum reconstruction characteristic of two algorithms is found to facilitate efficient reception in practical applications. [ABSTRACT FROM AUTHOR]

For wideband array signals, existing self-calibration methods use a first order approximation to simplify the estimation procedure under the assumption of small sensor position errors. However, the performance will degrade severely as the position errors increase. In this paper, a novel self-calibration method based on the time-frequency distributions (TFDs) is proposed to relieve the small errors constraint. We firstly develop an approach for wideband signals to select the TFDs of each source. Then the TFDs are utilized to obtain the propagation delays, which have a simple linear relationship with the sensor positions. The direction of arrival (DOA) and positions are finally estimated by a two-step iteration without any approximation. Simulation results demonstrate that the proposed method can achieve accurate DOA and position estimation over a broad range of position errors with lower computational complexity, and outperforms existing self-calibration algorithms. [ABSTRACT FROM AUTHOR]

A communication and navigation receiver is required to remove hostile jamming signals and synchronize receiving signals effectively especially for satellite communication and navigation whose resources are becoming more and more limited. This paper proposes a novel signal receiving method by combining the processes of anti-jamming and synchronization to reduce the overall computational complexity at the expense of slightly affecting the detection probability, which is analyzed in detail by derivations. Furthermore, this paper introduces sparse Fourier transformation (SFT) into the proposed algorithm to replace fast Fourier transformation (FFT) so as to further reduce the calculation time especially in large frequency offset environments. [ABSTRACT FROM AUTHOR]

This paper first presents a decomposition scheme to reduce the computation time and make the first-order moment-based cyclic convolution well suited for hardware implementation. By decomposing the fixed convolution kernel into similar subparts and using their preprocessing results as control signals, each subpart of cyclic convolution can be calculated with a basic computing substructure. Due to the flexibility of decomposition, a trade-off between computation time and hardware complexity exists. And for a pair of fixed decomposition coefficients, the similarity among subparts leads to the time-efficient structure and the area-efficient structure for cyclic convolution without limitation on the convolution length N and the word length L. Since the basic computing substructure only contains a simple control module, several circularly right-shift registers and N accumulation units, there is no requirement for multipliers and large memory. Comparisons in terms of area-delay product, area-time product and power consumption with the existing memory-based structures have been made to demonstrate the efficiency and effectiveness of the proposed structures. Using the same metrics, the comparison results further show significant improvement of the proposed designs over the previous first-order moment-based structure. [ABSTRACT FROM AUTHOR]

This paper proposes a low-complexity min-sum algorithm for decoding low-density parity-check codes. It is an improved version of the single-minimum algorithm where the two-minimum calculation is replaced by one minimum calculation and a second minimum emulation. In the proposed one, variable correction factors that depend on the iteration number are introduced and the second minimum emulation is simplified, reducing by this way the decoder complexity. This proposal improves the performance of the single-minimum algorithm, approaching to the normalized min-sum performance in the water-fall region. Also, the error-floor region is analyzed for the code of the IEEE 802.3an standard showing that the trapping sets are decoded due to a slow down of the convergence of the algorithm. An error-floor free operation below BER=10-15 is shown for this code by means of a field-programmable gate array (FPGA)-based hardware emulator. A layered decoder is implemented in a 90-nm CMOS technology achieving 12.8 Gbps with an area of 3.84 mm2. [ABSTRACT FROM AUTHOR]

In real networks, clustering is of great value to the analysis, design, and optimization of numerous complex systems in natural science and engineering, e.g. power supply systems ,modern transportation networks, and real-world networks. However, the majority of them simply pay attention to the density of edges rather than the signs of edges as the attributes to cluster, which usually suffer a high-level computational complexity. In this paper, a new rule is proposed to update the attributes flow, which can guarantee network clustering reach a state of optimal convergence. The positive and negative update rule we introduced, represent the cooperative and hostile relationship, and the attribute configuration will convergence and one can identify the reasonable cluster configuration automatically. An algorithm with high efficiency is proposed: a nearly linear relationship is found between the time complexity and the size in sparse networks. Finally, we conduct the verification of the algorithmic performance by a representative simulations on Correlates of War data. [ABSTRACT FROM AUTHOR]

The semisupervised least squares support vector machine (LS-S3VM) is an important enhancement of least squares support vector machines in semisupervised learning. Given that most data collected from the real world are without labels, semisupervised approaches are more applicable than standard supervised approaches. Although a few training methods for LS-S3VM exist, the problem of deriving the optimal decision hyperplane efficiently and effectually has not been solved. In this paper, a fully weighted model of LS-S3VM is proposed, and a simple integer programming (IP) model is introduced through an equivalent transformation to solve the model. Based on the distances between the unlabeled data and the decision hyperplane, a new indicator is designed to represent the possibility that the label of an unlabeled datum should be reversed in each iteration during training. Using the indicator, we construct an extended candidate set consisting of the indices of unlabeled data with high possibilities, which integrates more information from unlabeled data. Our algorithm is degenerated into a special scenario of the previous algorithm when the extended candidate set is reduced into a set with only one element. Two strategies are utilized to determine the descent directions based on the extended candidate set. Furthermore, we developed a novel method for locating a good starting point based on the properties of the equivalent IP model. Combined with the extended candidate set and the carefully computed starting point, a fast algorithm to solve LS-S3VM quasi-optimally is proposed. The choice of quasi-optimal solutions results in low computational cost and avoidance of overfitting. Experiments show that our algorithm equipped with the two designed strategies is more effective than other algorithms in at least one of the following three aspects: 1) computational complexity; 2) generalization ability; and 3) flexibility. However, our algorithm and other algorithms have similar levels of performance in the remaining aspects. [ABSTRACT FROM AUTHOR]

Reducing samples through convex hull vertices selection (CHVS) within each class is an important and effective method for online classification problems, since the classifier can be trained rapidly with the selected samples. However, the process of CHVS is NP-hard. In this paper, we propose a fast algorithm to select the convex hull vertices, based on the convex hull decomposition and the property of projection. In the proposed algorithm, the quadratic minimization problem of computing the distance between a point and a convex hull is converted into a linear equation problem with a low computational complexity. When the data dimension is high, an approximate, instead of exact, convex hull is allowed to be selected by setting an appropriate termination condition in order to delete more nonimportant samples. In addition, the impact of outliers is also considered, and the proposed algorithm is improved by deleting the outliers in the initial procedure. Furthermore, a dimension convention technique via the kernel trick is used to deal with nonlinearly separable problems. An upper bound is theoretically proved for the difference between the support vector machines based on the approximate convex hull vertices selected and all the training samples. Experimental results on both synthetic and real data sets show the effectiveness and validity of the proposed algorithm. [ABSTRACT FROM PUBLISHER]

In this paper, we present complexity certification results for a distributed augmented Lagrangian (AL) algorithm used to solve convex optimization problems involving globally coupled linear constraints. Our method relies on the accelerated distributed AL (ADAL) algorithm, which can handle the coupled linear constraints in a distributed manner based on local estimates of the AL. We show that the theoretical complexity of ADAL to reach an $\epsilon$-optimal solution both in terms of suboptimality and infeasibility is O(\frac{1}{\epsilon }) iterations. Moreover, we provide a valid upper bound for the optimal dual multiplier, which enables us to explicitly specify these complexity bounds. We also show how to choose the step-size parameter to minimize the bounds on the convergence rates. Finally, we discuss a motivating example, a model predictive control problem, involving a finite number of subsystems, which interact with each other via a general network. [ABSTRACT FROM PUBLISHER]

This paper addresses the problem of reducing the required network load and computational power for the implementation of Set-Valued Observers (SVOs) in Networked Control System (NCS). Event- and self-triggered strategies for NCS, modeled as discrete-time Linear Parameter-Varying (LPV) systems, are studied by showing how the triggering condition can be selected. The methodology provided can be applied to determine when it is required to perform a full (“classical”) computation of the SVOs, while providing low-complexity state overbounds for the remaining time, at the expenses of temporarily reducing the estimation accuracy. As part of the procedure, an algorithm is provided to compute a suitable centrally symmetric polytope that allows to find hyper-parallelepiped and ellipsoidal overbounds to the exact set-valued state estimates calculated by the SVOs. By construction, the proposed triggering techniques do not influence the convergence of the SVOs, as at some subsequent time instants, set-valued estimates are computed using the conventional SVOs. Results are provided for the triggering frequency of the self-triggered strategy and two interesting cases: distributed systems when the dynamics of all nodes are equal up to a reordering of the matrix; and when the probability distribution of the parameters influencing the dynamics is known. The performance of the proposed algorithm is demonstrated in simulation by using a time-sensitive example. [ABSTRACT FROM AUTHOR]

Networking between autonomously flying aerial vehicles requires efficient control and sustainable path for data transmission. Aerial nodes are extremely dynamic and provide a vast range of applications especially focusing on surveillance and data acquisition. However, these dynamic nodes are prone to unstable connectivity which hinders network operations, and also decreases the network lifetime. Such issues directly influence the control and relaying over aerial vehicles. Thus, it becomes essential to have an efficient strategy for controller selection and autonomous relaying. In this paper, a quaternion based neural model is proposed, which uses Decision Making Trial and Evaluation Laboratory Technique (DEMATEL) for the selection of network controllers and relays. The proposed algorithms are capable of selecting controller with a complexity O ( n ), and provide cooperative relaying with a complexity O ( n  ×  k ). The effectiveness of the proposed model is demonstrated by using simulations. The results show that the proposed approach reduces delays by 25% during the selection of controller, and increases the transfer speed by 20% compared to existing approaches. [ABSTRACT FROM AUTHOR]

Modulated and extended lapped transforms (MLT, ELT) are shift-orthogonal transforms generated from parametric window functions. In this paper, new recursive algorithms are presented for the MLT and ELT. These invertible sliding lapped transforms are non-decimated and thus oversampled subband systems. The analysis bank input signal can be complex-valued and the optional filtering modes are even/odd-stacked subchannelization and real/complex-valued subsignals. The developed filter structure is similar to sliding discrete cosine and Fourier transform (DFT) filters but provides better frequency selectivity. In the presented running-sum implementation, the computations can be carried out with a bank of simple recursive filters as the windowing is embedded into the structure. The second objective is to propose a Goertzel-type of recursive algorithm for critically-sampled exponentially-modulated filter bank (EMFB). Since the basic Goertzel algorithm is a recursive filter implementation for the DFT it requires the following modifications: modulation phase shifting to meet the perfect reconstruction requirement and frequency shifting to accommodate odd-stacked configuration. The Goertzel-EMFB suits well for problems where only a few subbands are processed from a much larger set of available subchannels. [ABSTRACT FROM AUTHOR]

This paper presents a low-complexity algorithm and architecture to compute power spectral density (PSD) using the Welch method. The Welch algorithm provides a good estimate of the spectral power at the cost of high computational complexity. We propose a new modified approach to reduce the computational complexity of the Welch PSD computation for a 50% overlap. In the proposed approach, an N/2-point FFT is computed, where N is the length of the window and is merged with the FFT of the previous N/2-point to generate an N-point FFT of the overlapped segment. This requires replacing the windowing operation as a convolution in the frequency domain. Fortunately, the frequency-domain filtering requires a symmetric 3-tap or 5-tap FIR filter for raised cosine windows. The proposed method needs to compute (L+1) N/2-point FFTs instead of L N-point FFTs, where L is the number of overlapping segments. In the proposed novel merged FFT approach, the even samples are computed exactly, while the odd samples require a shift by a half-sample delay and are estimated using a bidirectional fractional-delay filter. The complexity reduction comes at the cost of slight performance loss due to the approximation used for the implementation of the fractional-delay filter. The performance loss is about 8% using fractional-delay filter with 2 multipliers. A novel architecture is presented based on the proposed algorithm. The proposed architecture not only consumes 33% less energy compared to the original method but also reduces the latency by about 44% for 8 overlapping segments. Further a low-complexity architecture is presented to compute a special case of the short-time Fourier transform based on the proposed PSD computation algorithm. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents the implementation of two hardware architectures, i.e., A2 Lattice Vector Quantization (LVQ) and Multistage A2LVQ (MA2LVQ), using a Field-Programmable Gate Array (FPGA). First, the renowned LVQ quantizer by Conway and Sloane is implemented followed by a low-complexity A2LVQ based on a new A2LVQ algorithm. It is revealed that the implementation requires high number of multiplier circuits. Then the implementation of a low-complexity A2LVQ is presented. This implementation uses only the first quadrant of the A2 lattice Voronoi region formed by W and T regions. This paper also presents the implementation of a multistage A2LVQ (MA2LVQ) with an architecture built from successive A2 quantizer blocks. Synthesis results show that the execution time of the low-complexity A2LVQ reaches up to 35.97 ns. The MA2LVQ is implemented using both low-complexity A2LVQ and ordinary A2 architectures. The system with the former architecture utilizes less logic and register elements by 47%. [Copyright &y& Elsevier]

Active noise control (ANC) requires a controller with a small delay. However, in most ANC applications, this delay is significant due to the typically low sample rate, the anti-aliasing (AA), and reconstruction filters (RC) of the analog to digital (AD) and digital to analog (DA) converters. This delay can be reduced by increasing the sampling frequency at the expense of a significant increase in computational complexity. Sigma-delta AD and DA converters work at high sampling frequencies, but their use in ANC is limited due to the delay of AA and RC filters. This work proposes removing the AA and RC filters of the sigma-delta converters and using the oversampled signals directly in an ANC system. This proposal allows the ANC system to be implemented at a large sample frequency but using signals with fewer bits per sample (word-length). This is the first short-word length implementation of the least mean squares (LMS) algorithm to the authors’ knowledge. Gains of up to 6 times may be achieved in the computational complexity when compared with a long-word length implementation. Theoretical and simulation results validate the current solution. [ABSTRACT FROM AUTHOR]

In order to improve the filter׳s performance when identifying sparse system, this paper develops two sparse-aware algorithms by incorporating the l 0 -norm constraint of the weight vector into the conventional normalized subband adaptive filter (NSAF) algorithm. The first algorithm is obtained from the principle of the minimum perturbation; and the second one is based on the gradient descent principle. The resulting algorithms have almost the same convergence and steady-state performance while the latter saves computational complexity. What׳s more, the performance of both algorithms is analyzed by resorting to some assumptions commonly used in the analyses of adaptive algorithms. Simulation results in the context of sparse system identification not only demonstrate the effectiveness of the proposed algorithms, but also verify the theoretical analyses. [ABSTRACT FROM AUTHOR]