Search

We propose a novel semi-supervised learning (SSL) assumption—the high separation probability (HSP) assumption—that is complementary to the common low density separation (LDS) assumption, and a highly accurate and efficient SSL algorithm, the transductive minimax probability machine (TMPM). Under the HSP assumption, a preferred classifier should ensure that with high probability the samples are far away from the decision boundary. Similarly, the LDS assumption states that the decision boundary should lie in a low-density region. A remarkable property of HSP is that it provides an elegant theoretical framework for analyzing the generalization performance of SSL, while it remains difficult for the LDS assumption to have a quantitative criterion on how it fits the data. Moreover, it has the same paradigm as the minimax probability machine (MPM) and yields an intractable mixed-integer optimization for solving the transductive label assignment problem. Consequently, we propose TMPM with a label-switching strategy and iterative manner to formalize our approximate solution. Theoretically, we analyze the computational complexity, convergence property, and generalization error bound of TMPM. Empirically, we show that TMPM achieves competitive performance on a wide range of datasets, while being almost one order of magnitude faster than existing SSL approaches. [ABSTRACT FROM AUTHOR]

In this article, we consider the problem of estimating diffraction attenuation from the approximation of terrain using a multiple bridged knife-edge model. This model can be considered as a generalization of the well-known multiple knife-edge (MKE) one where spaces between knife-edges are bridged by reflecting surfaces. A series-based-standard solution is presented in the literature but suffers from its very high computational complexity. We, thus, propose to generalize the recursive Vogler algorithm developed for the MKE model to tackle this problem. To reduce complexity, the proposed algorithm exploits the recursive form to avoid repeated calculations of the existing solution. Moreover, we provide a complexity analysis of both the standard algorithm and the proposed algorithm based on the number of computed integrals. Both theoretical and numerical results show that our proposed algorithm is faster than the original one while having identical accuracy, hence proving the effectiveness of our solution. [ABSTRACT FROM AUTHOR]

In this article, we propose a fast algorithm to generate a rank-minimized $\mathcal {H}^{2}$ -representation for solving electrically large volume integral equations (VIEs). Unlike existing methods whose complexity is as high as quadratic, the proposed algorithm has linearithmic complexity, and thus, it can handle problems with large electrical sizes. Furthermore, the algorithm is purely algebraic and kernel independent. Numerical experiments on electrically large 3-D arrays of dielectric cubes having over 33 million unknowns demonstrate the efficiency and accuracy of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this letter, to improve the performance of the space-time adaptive processing (STAP) filter with finite training samples, a novel algorithm with multiple measurement vectors (MMV) based on sparse recovery (SR) is proposed. Compared with traditional SR STAP algorithms, we utilize the knowledge of Capon spectrum to design a weighted ${\ell }_2{\rm{ - norm}}$ penalty which can better approximate the original ${\ell }_0{\rm{ - norm}}$. Besides, the proposed algorithm has fast convergence performance and closed-form analytic solution in each iteration. Simulation results demonstrate the effectiveness and great performance of the proposed method. [ABSTRACT FROM AUTHOR]

This letter investigates reconfigurable intelligent surface (RIS)-assisted full-duplex multiple-input single-output wireless system, where the beamforming and RIS phase shifts are optimized to maximize the sum-rate for both single and distributed RIS deployment schemes. The preference of using the single or distributed RIS deployment scheme is investigated through three practical scenarios based on the links’ quality. The closed-form solution is derived to optimize the beamforming vectors and a novel deep reinforcement learning (DRL) algorithm is proposed to optimize the RIS phase shifts. Simulation results illustrate that the choice of the deployment scheme depends on the scenario and the links’ quality. It is further shown that the proposed algorithm significantly improves the sum-rate compared to the non-optimized scenario in both single and distributed RIS deployment schemes. Besides, the proposed beamforming derivation achieves a remarkable improvement compared to the approximated derivation in previous works. Finally, the complexity analysis confirms that the proposed DRL algorithm reduces the computation complexity compared to the DRL algorithm in the literature. [ABSTRACT FROM AUTHOR]

In this paper, we investigate an intelligent reflecting surface (IRS) assisted multi-user multiple-input multiple-output (MIMO) full-duplex (FD) system. We jointly optimize the active beamforming matrices at the access point (AP) and uplink users, and the passive beamforming matrix at the IRS to maximize the weighted sum-rate of the system. Since it is practically difficult to acquire the channel state information (CSI) for IRS-related links due to its passive operation and large number of elements, we conceive a mixed-timescale beamforming scheme. Specifically, the high-dimensional passive beamforming matrix at the IRS is updated based on the channel statistics while the active beamforming matrices are optimized relied on the low-dimensional real-time effective CSI at each time slot. We propose an efficient stochastic successive convex approximation (SSCA)-based algorithm for jointly designing the active and passive beamforming matrices. Moreover, due to the high computational complexity caused by the matrix inversion computation in the SSCA-based optimization algorithm, we further develop a deep-unfolding neural network (NN) to address this issue. The proposed deep-unfolding NN maintains the structure of the SSCA-based algorithm but introduces a novel non-linear activation function and some learnable parameters induced by the first-order Taylor expansion to approximate the matrix inversion. In addition, we develop a black-box NN as a benchmark. Simulation results show that the proposed mixed-timescale algorithm outperforms the existing single-timescale algorithm and the proposed deep-unfolding NN approaches the performance of the SSCA-based algorithm with much reduced computational complexity when deployed online. [ABSTRACT FROM AUTHOR]

Existing wideband beampattern synthesis methods usually require multiple beamformers, each corresponding to one frequency bin, which results in excessive resource consumption in engineering practice. To alleviate the resource consumption of wideband array beamforming, we propose a novel time-domain wideband digital beamformer that can control the beam shape over the whole bandwidth for interference mitigation by using only one set of amplitude–phase weights and integer time delay filters. To tackle the resultant optimization problem, two effective algorithms are introduced, and both can solve the problem within polynomial time. One is an alternating optimization algorithm that decomposes the original problem into multiple tractable subproblems iteratively. The other is the convex approximation algorithm that transforms the original problem into a series of second-order cone programming problems iteratively. The two algorithms exhibit their respective advantages in terms of convergence and computational complexity. Extensive numerical examples are presented to evaluate the proposed time-domain wideband beamforming strategy, highlighting that it can form a deep notch in any interested spatial–spectral region to suppress the strong interferences. [ABSTRACT FROM AUTHOR]

This article presents a novel Bayesian approach for hyperspectral image unmixing. The observed pixels are modeled by a linear combination of material signatures weighted by their corresponding abundances. A spike-and-slab abundance prior is adopted to promote sparse mixtures and an Ising prior model is used to capture spatial correlation of the mixture support across pixels. We approximate the posterior distribution of the abundances using the expectation-propagation (EP) method. We show that it can significantly reduce the computational complexity of the unmixing stage and meanwhile provide uncertainty measures, compared to expensive Monte Carlo strategies traditionally considered for uncertainty quantification. Moreover, many variational parameters within each EP factor can be updated in a parallel manner, which enables mapping of efficient algorithmic architectures based on graphics processing units (GPUs). Under the same approximate Bayesian framework, we then extend the proposed algorithm to semi-supervised unmixing, whereby the abundances are viewed as latent variables and the expectation-maximization (EM) algorithm is used to refine the endmember matrix. Experimental results on synthetic data and real hyperspectral data illustrate the benefits of the proposed framework over state-of-art linear unmixing methods. [ABSTRACT FROM AUTHOR]

Nonlinear estimation in robotics and vision is typically plagued with outliers due to wrong data association or incorrect detections from signal processing and machine learning methods. This article introduces two unifying formulations for outlier-robust estimation, generalized maximum consensus ($\text{G}$ - $\text{MC}$) and generalized truncated least squares ($\text{G-TLS}$), and investigates fundamental limits, practical algorithms, and applications. Our first contribution is a proof that outlier-robust estimation is inapproximable: In the worst case, it is impossible to (even approximately) find the set of outliers, even with slower-than-polynomial-time algorithms (particularly, algorithms running in quasi-polynomial time). As a second contribution, we review and extend two general-purpose algorithms. The first, adaptive trimming ($\text{ADAPT}$), is combinatorial and is suitable for $\text{G}$ - $\text{MC}$ ; the second, graduated nonconvexity ($\text{GNC}$), is based on homotopy methods and is suitable for $\text{G-TLS}$. We extend $\text{ADAPT}$ and $\text{GNC}$ to the case where the user does not have prior knowledge of the inlier-noise statistics (or the statistics may vary over time) and is unable to guess a reasonable threshold to separate inliers from outliers (as the one commonly used in RANdom SAmple Consensus $(\text{RANSAC})$. We propose the first minimally tuned algorithms for outlier rejection, which dynamically decide how to separate inliers from outliers. Our third contribution is an evaluation of the proposed algorithms on robot perception problems: mesh registration, image-based object detection (shape alignment), and pose graph optimization. $\text{ADAPT}$ and $\text{GNC}$ execute in real time, are deterministic, outperform $\text{RANSAC}$ , and are robust up to 80–90% outliers. Their minimally tuned versions also compare favorably with the state of the art, even though they do not rely on a noise bound for the inliers. [ABSTRACT FROM AUTHOR]

An algorithm for the fast computation of multistatic scattering patterns, produced by low-contrast inhomogeneous volumetric objects, which satisfy the Born approximation assumption, is presented. The algorithm relies on hierarchical interpolation and aggregation of optimally sampled phase-compensated partial contributions to the scattered field integral. The Born approximation enables the efficient simultaneous computation for ranges of incident and observation angles, as well as excitation frequencies. This leads to a reduction in the asymptotic computational complexity by several polynomial orders of the problem’s acoustical size. The algorithm’s error controllability and favorable computation time are demonstrated via representative examples. [ABSTRACT FROM AUTHOR]

Under finite-alphabet inputs, the mutual information (MI) and minimum mean-square error (MMSE) matrix have no closed-form solutions, and numerical integrations, e.g., Monte Carlo simulation, endure prohibitive computational burden for massive multiple-input multiple-output (MIMO) systems. In this letter, we propose a new method based on the approximate message passing (AMP) algorithm for estimating the MI and MMSE matrix. By the new method, the computational complexity is reduced from ${\mathcal{ O}}(N_{\mathrm{ sa}}N_{r}N_{t}M^{2N_{t}})$ to ${\mathcal{ O}}({N_{r}N_{t}})$ for a $N_{r}\times N_{t}$ MIMO system, where $M$ is the cardinality of the input and $N_{\mathrm{ sa}}$ is the number of samples. Simulation results also demonstrate the effectiveness and high-performance of the proposed new method. [ABSTRACT FROM AUTHOR]

In this paper, we extend the bilinear generalized approximate message passing (BiG-AMP) approach, originally proposed for high-dimensional generalized bilinear regression, to the multi-layer case for the handling of cascaded problem such as matrix-factorization problem arising in relay communication among others. Assuming statistically independent matrix entries with known priors, the new algorithm called ML-BiGAMP could approximate the general sum-product loopy belief propagation (LBP) in the high-dimensional limit enjoying a substantial reduction in computational complexity. We demonstrate that, in large system limit, the asymptotic MSE performance of ML-BiGAMP could be fully characterized via a set of simple one-dimensional equations termed state evolution (SE). We establish that the asymptotic MSE predicted by ML-BiGAMP’ SE matches perfectly the exact MMSE predicted by the replica method, which is well-known to be Bayes-optimal but infeasible in practice. This consistency indicates that the ML-BiGAMP may still retain the same Bayes-optimal performance as the MMSE estimator in high-dimensional applications, although ML-BiGAMP's computational burden is far lower. As an illustrative example of the general ML-BiGAMP, we provide a detector design that could estimate the channel fading and the data symbols jointly with high precision for the two-hop amplify-and-forward relay communication systems. [ABSTRACT FROM AUTHOR]

Novel sparse reconstruction algorithms are proposed for beamspace channel estimation in massive multiple-input multiple-output systems. The proposed algorithms minimize a least-squares objective having a nonconvex regularizer. This regularizer removes the penalties on a few large-magnitude elements from the conventional $\ell _{1}$ -norm regularizer, and thus it only forces penalties on the remaining elements that are expected to be zeros. Accurate and fast reconstructions can be achieved by performing gradient projection updates within the framework of difference of convex functions (DC) programming. A double-loop algorithm and a single-loop algorithm are proposed via different DC decompositions, and these two algorithms have distinct computational complexities and convergence rates. An extension algorithm is further proposed by designing new step sizes for the single-loop algorithm. The extension algorithm has a faster convergence rate and can achieve approximately the same level of accuracy as the proposed double-loop algorithm. Numerical results show significant advantages of the proposed algorithms over existing reconstruction algorithms in terms of reconstruction accuracies and runtimes. Compared with the benchmark channel estimation approaches, the proposed algorithms can achieve smaller channel reconstruction error and higher achievable spectral efficiency. [ABSTRACT FROM AUTHOR]

In-memory error correction code (ECC) is a promising technique to improve the yield and reliability of high density memory design. However, the use of in-memory ECC poses a new problem to memory repair analysis algorithm, which has not been explored before. This article first makes a quantitative evaluation and demonstrates that the straightforward algorithms for memory with redundancy and in-memory ECC have serious deficiency on either repair rate or repair analysis speed. Accordingly, an optimal repair analysis algorithm that leverages preprocessing/filter algorithms, hybrid search tree, and depth-first search strategy is proposed to achieve low computational complexity and optimal repair rate in the meantime. In addition, a heuristic repair analysis algorithm that uses a greedy strategy is proposed to efficiently find repair solutions. Experimental results demonstrate that the proposed optimal repair analysis algorithm can achieve optimal repair rate and increase the repair analysis speed by up to 105 × compared with the straightforward exhaustive search algorithm. The proposed heuristic repair analysis algorithm is approximately 28 percent faster than the proposed optimal algorithm, at the expense of 5.8 percent repair rate loss. [ABSTRACT FROM AUTHOR]

Sequential attack detection in a distributed sensor network is considered, where each sensor successively produces one-bit quantized samples of a desired deterministic scalar parameter corrupted by additive noise. The unknown parameters in the pre-attack and post-attack models, namely the desired parameter to be estimated and the injected malicious data at the attacked sensors pose a significant challenge for designing a computationally efficient scheme for each sensor to detect the occurrence of attacks by only using local communication with neighboring sensors. The generalized Cumulative Sum (GCUSUM) algorithm is considered, which replaces the unknown parameters with their maximum likelihood estimates in the CUSUM test statistic. For the problem under consideration, a sufficient condition is provided under which the expected false alarm period of the GCUSUM can be guaranteed to be larger than any given value. Next, we consider the distributed implementation of the GCUSUM. We first propose an alternative test statistic which is asymptotically equivalent to that of GCUSUM. Then based on the proposed alternative test statistic and running consensus algorithms, we propose a distributed approximate GCUSUM algorithm which significantly reduce the prohibitively high computational complexity of the centralized GCUSUM. Numerical results show that the proposed distributed approximate GCUSUM algorithm can provide a performance that is comparable to the centralized GCUSUM. [ABSTRACT FROM AUTHOR]

Optimization theory assisted algorithms have received great attention for precoding design in multiuser multiple-input multiple-output (MU-MIMO) systems. Although the resultant optimization algorithms are able to provide excellent performance, they generally require considerable computational complexity, which gets in the way of their practical application in real-time systems. In this work, in order to address this issue, we first propose a framework for deep-unfolding, where a general form of iterative algorithm induced deep-unfolding neural network (IAIDNN) is developed in matrix form to better solve the problems in communication systems. Then, we implement the proposed deep-unfolding framework to solve the sum-rate maximization problem for precoding design in MU-MIMO systems. An efficient IAIDNN based on the structure of the classic weighted minimum mean-square error (WMMSE) iterative algorithm is developed. Specifically, the iterative WMMSE algorithm is unfolded into a layer-wise structure, where a number of trainable parameters are introduced to replace the high-complexity operations in the forward propagation. To train the network, a generalized chain rule of the IAIDNN is proposed to depict the recurrence relation of gradients between two adjacent layers in the back propagation. Moreover, we discuss the computational complexity and generalization ability of the proposed scheme. Simulation results show that the proposed IAIDNN efficiently achieves the performance of the iterative WMMSE algorithm with reduced computational complexity. [ABSTRACT FROM AUTHOR]

The first moment and second central moments of the portfolio return, a.k.a. mean and variance, have been widely employed to assess the expected profit and risk of the portfolio. Investors pursue higher mean and lower variance when designing the portfolios. The two moments can well describe the distribution of the portfolio return when it follows the Gaussian distribution. However, the real world distribution of assets return is usually asymmetric and heavy-tailed, which is far from being a Gaussian distribution. The asymmetry and the heavy-tailedness are characterized by the third and fourth central moments, i.e., skewness and kurtosis, respectively. Higher skewness and lower kurtosis are preferred to reduce the probability of extreme losses. However, incorporating high-order moments in the portfolio design is very difficult due to their non-convexity and rapidly increasing computational cost with the dimension. In this paper, we propose a very efficient and convergence-provable algorithm framework based on the successive convex approximation (SCA) algorithm to solve high-order portfolios. The efficiency of the proposed algorithm framework is demonstrated by the numerical experiments. [ABSTRACT FROM AUTHOR]

We consider a transmission scheduling problem in which multiple agents receive update information through a shared Time Division Multiple Access (TDMA) channel. To provide timely delivery of update information, the problem asks for a schedule that minimizes the overall Age of Information (AoI). We call this problem the Min-AoI problem. Several special cases of the problem are known to be solvable in polynomial time. Our contribution is threefold. First, we introduce a new job scheduling problem called the Min-WCS problem, and we prove that, for any constant ${r} \geq 1$ , every r-approximation algorithm for the Min-WCS problem can be transformed into an r-approximation algorithm for the Min-AoI problem. Second, we give a randomized 2.619-approximation algorithm, a randomized 3-approximation algorithm, which outperforms the previous one in certain scenarios, and a dynamic-programming-based exact algorithm for the Min-WCS problem. Finally, we prove that the Min-AoI problem is NP-hard. [ABSTRACT FROM AUTHOR]

When dealing with complex nonlinear signals in intelligent system, by defining the inner product of two data vectors in the feature space, the kernel function can reflect the nonlinear mapping relationship between reproducing kernel Hilbert space (RKHS) and original data space. Therefore, by implementing classical linear adaptive filtering in RKHS space, the filtering operation can be expressed as a special relation of inner product with kernel function, which is referred to as “kernel trick.” As long as these algorithms can be expressed in the form of inner product, not only the convex least squares problem can be solved iteratively, but also the nonlinear adaptive filtering algorithms can be obtained, which have both general approximation characteristics and convexity. Therefore, the combination of kernel method and adaptive filtering algorithm is realized. On the other hand, since the Gram matrix is used, the dimension of kernel adaptive algorithm is determined by the number of data samples. When the number of observation sample point is increasing, the size of the state space increases exponentially with the growth of the dimension. Thereby, the kernel adaptive algorithm should solve the problem of online sparsification to avoid “curse of dimensionality.” As part II, based on online sparse kernel learning and the classical adaptive filtering algorithm, the kernel adaptive algorithms and online sparse algorithms are investigated in this paper. The main works of this paper have two aspects. First, combined with classical adaptive algorithm and kernel feature mapping, this paper investigates the basic concept of kernel adaptive algorithm and the realization mechanism of four kernel adaptive algorithm intensively: 1) kernel least mean squares; 2) kernel recursive least squares; 3) kernel affine projection algorithm; and 4) kernel principal component analysis. Second, in order to reduce the computational complexity, this paper studies some online sparse algorithms which include novel criterion, approximate linear dependency, sliding window, coherence criterion, surprise criterion, and so on. Finally, this paper summarizes the essence of existing conclusions of above algorithms and perspectives the future research direction. [ABSTRACT FROM AUTHOR]

Adaptive exponential functional link network (AEFLN) is a recently introduced linear-in-the-parameters nonlinear filter. In an attempt to improve the performance of AEFLN, an improved AEFLN (IAEFLN) which employs independent decay rates for each exponentially varying sinusoidal basis function, has been proposed in this brief. The update rules for the filter weights as well as the decay parameter vector has been derived. To further reduce the computational complexity of the proposed network, without sacrificing performance, two approximate versions of IAEFLN, namely approximate 1 IAEFLN (Apx1-IAEFLN) and approximate 2 IAEFLN (Apx2-IAEFLN) has been developed and their corresponding update rules have been derived. Bounds on learning rates have also been derived and simulation study shows improved convergence behaviour of the proposed IAEFLN over AEFLN. The approximate versions achieve similar convergence performance as that of IAEFLN, at a lower computational load. [ABSTRACT FROM AUTHOR]

Block sparse Bayesian learning (BSBL) has been widely used in inverse synthetic aperture radar (ISAR) imaging, which significantly improves the imaging performance by exploiting the sparse pattern information of ISAR images. However, the conventional Bayesian learning algorithm has high computational complexity, which hinders its applications to real-time processing of radar imaging. The approximate message passing (AMP) can be used to obtain a low complexity implementation of sparse Bayesian learning (SBL). However, AMP suffers from performance losses and even diverges in the case of high-Doppler resolution ISAR imaging where the measurement matrix can be highly correlated. To solve this problem, we propose a fast pattern coupled SBL ISAR imaging algorithm based on approximate message passing with unitary transformation (UTAMP). First, the estimates of the hyperparameters of sparse vector are obtained through UTAMP based SBL, and then nearest neighbor hyperparameters are coupled and updated for next iteration. With low complexity, the proposed algorithm can effectively exploit the sparse pattern information of ISAR images, and exhibits excellent convergence and imaging performance. Both simulation and real data experiments are carried out to verify the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose transmission point selection algorithms to provide lower service time between an application server to end users by selecting the transmission point used by a newly identified metric, i.e., service latency. In particular, the proposed ordered service latency-based transmission point selection algorithm is beneficial in a sense that it does not increase average service time but decrease the maximum service time although it brings additional computational complexity slightly. We also provide the performance bounds with proven approximation ratios and verify that the proposed algorithm achieves lower maximum service time without degrading the average service time as well as waiting time through simulations in practical environments. [ABSTRACT FROM AUTHOR]

Device-to-Device (D2D) communications incorporated with content caching have been regarded as a promising way to offload the cellular traffic data. In this paper, the caching strategy is investigated to maximize the D2D offloading gain with the comprehensive consideration of user collaborative characteristics as well as the physical transmission conditions. Specifically, for a given content, the number of interested users in different groups is different, and users always ask the most trustworthy user in proximity for D2D transmissions. An analytical expression of the D2D success probability is first derived, which represents the probability that the received signal to interference ratio is no less than a given threshold. As the formulated problem is nonconvex, the optimal caching strategy for the special unbiased case is derived in a closed form, and a numerical searching algorithm is proposed to obtain the globally optimal solution for the general case. To reduce the computational complexity, an iterative algorithm based on the asymptotic approximation of the D2D success probability is proposed to obtain the solution that satisfies the Karush-Kuhn-Tucker conditions. The simulation results verify the effectiveness of the analytical results and show that the proposed algorithm outperforms the existing schemes in terms of offloading gain. [ABSTRACT FROM AUTHOR]

A method to find the minimized state machine cover of live and safe Petri nets (PNs) is proposed in this paper. It is required that a cover be obtained in some implementation methods of PN-based control algorithms and other applications such as data mining. Most of the known methods of its computation have at least exponential time and space complexity; this is true not only for the methods which guarantee a minimal cover is obtained but also for some methods of finding approximate solutions. The proposed algorithm is an approximation algorithm and has polynomial computational complexity. The experimental verification shows a very high efficiency of the presented technique. The proposed method is especially valuable in the case of large systems where a solution is obtained hundreds of times quicker than by other methods. [ABSTRACT FROM AUTHOR]

Recently, the gradient based constrained maximum correntropy criterion (GCMCC) algorithm has received considerable attention since it provides superior performance to the traditional methods and is robust to the non-Gaussian noise. However, the convergence of GCMCC algorithm depends on the learning rate. With a large learning rate, GCMCC converges fast but achieves a high steady state mean square deviation (MSD), and vice versa. To balance the convergence rate and the MSD, we propose a novel recursive CMCC (RCMCC) algorithm in this brief by utilizing the matrix inversion lemma. Furthermore, we provide a computationally efficient version of RCMCC (ERCMCC) algorithm by using some approximations. More importantly, we provide the convergence analysis of the RCMCC algorithm, and derive the stability condition and theoretical MSD. The theoretical analysis and superiorities of RCMCC and ERCMCC are validated by simulations. [ABSTRACT FROM AUTHOR]

Synthesis of unequally spaced arrays with uniform excitation is considered in this article. An iterative method based on second-order cone programming is developed to search the geometry with local optimum peak sidelobe level (PSLL), which is valid for arrays of different scale regardless of geometry constraints like centrosymmetry and minimum separation. By statistical analysis and comparison with other methods, it is verified that the computational complexity of the proposed method is only related to the dimension of optimization variables, and it can further exploit the potential of unequally spaced arrays with uniform excitation under acceptable complexity. [ABSTRACT FROM AUTHOR]

This paper investigates UAV-to-UAV (unmanned aerial vehicle) communications with a turning angle constraint, in which the information transmission time is minimized by joint UAV flight path planning and transmit power control. Considering the communication throughput requirement, peak transmit power, energy consumption, UAV flight speed, collision avoidance, and turning angle constraints, the joint UAV flight path planning and transmit power control problem is formulated as a non-convex optimization. Different from majority of prior studies that separately optimize the UAV flight path and transmit power, we develop a successive convex approximation based time minimization algorithm that simultaneously updates the UAV path and transmit power. We further prove that the proposed algorithm is guaranteed to converge. In addition, an initialization scheme is designed to start the proposed time minimization algorithm by solving an energy minimization problem. Simulation results verify that the proposed time minimization algorithm can shorten the completion time length and reduce the computational complexity compared with state of the art methods. [ABSTRACT FROM AUTHOR]

The problem of quickest detection of dynamic events in networks is studied. At some unknown time, an event occurs, and a number of nodes in the network are affected by the event, in that they undergo a change in the statistics of their observations. It is assumed that the event is dynamic, in that it can propagate along the edges in the network, and affect more and more nodes with time. The event propagation dynamics is assumed to be unknown. The goal is to design a sequential algorithm that can detect a “significant” event, i.e., when the event has affected no fewer than $\eta $ nodes, as quickly as possible, while controlling the false alarm rate. Fully connected networks are studied first, and the results are then extended to arbitrarily connected networks. The designed algorithms are shown to be adaptive to the unknown propagation dynamics, and their first-order asymptotic optimality is demonstrated as the false alarm rate goes to zero. The algorithms can be implemented with linear computational complexity in the network size at each time step, which is critical for online implementation. Numerical simulations are provided to validate the theoretical results. [ABSTRACT FROM AUTHOR]

Motivated by various delay sensitive applications, we address the problem of coordinating the offloading decisions of wireless devices that periodically generate computationally intensive tasks. We consider autonomous devices that aim at minimizing their own cost by choosing when to perform their tasks and whether or not to offload their tasks to an edge cloud through one of the multiple wireless links. We develop a game theoretical model of the problem, prove the existence of pure strategy Nash equilibria and propose a polynomial complexity algorithm for computing an equilibrium. Furthermore, we characterize the structure of the equilibria, and by providing an upper bound on the price of anarchy of the game we establish an asymptotically tight bound on the approximation ratio of the proposed algorithm. Our simulation results show that the proposed algorithm achieves significant performance gain compared to uncoordinated computation offloading at a computational complexity that is on average linear in the number of devices. [ABSTRACT FROM AUTHOR]

In an offload-capable Long Term Evolution (LTE)- Wireless Fidelity (WiFi) Heterogeneous Network (HetNet), we consider the problem of maximization of the total system throughput under voice user blocking probability constraint. The optimal policy is threshold in nature. However, computation of optimal policy requires the knowledge of the statistics of system dynamics, viz., arrival processes of voice and data users, which may be difficult to obtain in reality. Motivated by the Post-Decision State (PDS) framework to learn the optimal policy under unknown statistics of system dynamics, we propose, in this paper, an online Radio Access Technology (RAT) selection algorithm using Relative Value Iteration Algorithm (RVIA). However, the convergence speed of this algorithm can be further improved if the underlying threshold structure of the optimal policy can be exploited. To this end, we propose a novel structure-aware online RAT selection algorithm which reduces the feasible policy space, thereby offering lesser storage and computational complexity and faster convergence. This algorithm provides a novel framework for designing online learning algorithms for other problems and hence is of independent interest. We prove that both the algorithms converge to the optimal policy. Simulation results demonstrate that the proposed algorithms converge faster than a traditional scheme. Also, the proposed schemes perform better than other benchmark algorithms under realistic network scenarios. [ABSTRACT FROM AUTHOR]

In recent years the t-distributed Stochastic Neighbor Embedding (t-SNE) algorithm has become one of the most used and insightful techniques for exploratory data analysis of high-dimensional data. It reveals clusters of high-dimensional data points at different scales while only requiring minimal tuning of its parameters. However, the computational complexity of the algorithm limits its application to relatively small datasets. To address this problem, several evolutions of t-SNE have been developed in recent years, mainly focusing on the scalability of the similarity computations between data points. However, these contributions are insufficient to achieve interactive rates when visualizing the evolution of the t-SNE embedding for large datasets. In this work, we present a novel approach to the minimization of the t-SNE objective function that heavily relies on graphics hardware and has linear computational complexity. Our technique decreases the computational cost of running t-SNE on datasets by orders of magnitude and retains or improves on the accuracy of past approximated techniques. We propose to approximate the repulsive forces between data points by splatting kernel textures for each data point. This approximation allows us to reformulate the t-SNE minimization problem as a series of tensor operations that can be efficiently executed on the graphics card. An efficient implementation of our technique is integrated and available for use in the widely used Google TensorFlow.js, and an open-source C++ library. [ABSTRACT FROM AUTHOR]

Min-Hash is a popular technique for efficiently estimating the Jaccard similarity of binary sets. Consistent Weighted Sampling (CWS) generalizes the Min-Hash scheme to sketch weighted sets and has drawn increasing interest from the community. Due to its constant-time complexity independent of the values of the weights, Improved CWS (ICWS) is considered as the state-of-the-art CWS algorithm. In this paper, we revisit ICWS and analyze its underlying mechanism to show that there actually exists dependence between the two components of the hash-code produced by ICWS, which violates the condition of independence. To remedy the problem, we propose an Improved ICWS (I $^2$ 2 CWS) algorithm which not only shares the same theoretical computational complexity as ICWS but also abides by the required conditions of the CWS scheme. The experimental results on a number of synthetic data sets and real-world text data sets demonstrate that our I $^2$ 2 CWS algorithm can estimate the Jaccard similarity more accurately, and also competes with or outperforms the compared methods, including ICWS, in classification and top- $K$ K retrieval, after relieving the underlying dependence. [ABSTRACT FROM AUTHOR]

Orthogonal greedy algorithms are popular sparse signal reconstruction algorithms. Their principle is to select atoms one by one. A series of unconstrained least-square subproblems of gradually increasing size is solved to compute the approximation coefficients, which is efficiently performed using a fast recursive update scheme. When dealing with non-negative sparse signal reconstruction, a series of non-negative least-squares subproblems have to be solved. Fast implementation becomes tricky since each subproblem does not have a closed-form solution anymore. Recently, non-negative extensions of the classical orthogonal matching pursuit and orthogonal least squares algorithms were proposed, using slow (i.e., non-recursive) or recursive but inexact implementations. In this paper, we revisit these algorithms in a unified way. We define a class of non-negative orthogonal greedy algorithms and exhibit their structural properties. We propose a fast and exact implementation based on the active-set resolution of non-negative least-squares and exploiting warm start initializations. The algorithms are assessed in terms of accuracy and computational complexity for a sparse spike deconvolution problem. We also present an application to near-infrared spectra decomposition. [ABSTRACT FROM AUTHOR]

Many resource allocation tasks are challenging global (i.e., non-convex) optimization problems. The main issue is that the computational complexity of these problems grows exponentially in the number of variables instead of polynomially as for many convex optimization problems. However, often the non-convexity stems only from a subset of variables. Conventional global optimization frameworks like monotonic optimization or DC programming treat all variables as global variables and require complicated, problem specific decomposition approaches to exploit the convexity in some variables. To overcome this challenge, we develop an easy-to-use algorithm that inherently differentiates between convex and non-convex variables, preserving the low computational complexity in the number of convex variables. Another issue with these widely used frameworks is that they may suffer from severe numerical problems. We discuss this issue in detail and provide a clear motivating example. The solution to this problem is to replace the traditional approach of finding an $\varepsilon $ -approximate solution by the novel concept of $\varepsilon $ -essential feasibility. The underlying algorithmic approach is called successive incumbent transcending (SIT) algorithm and builds the foundation of our developed algorithm. A further highlight of this algorithm is that it inherently treats fractional objectives making the use of Dinkelbach's iterative algorithm obsolete. Numerical experiments show a speed-up of four orders of magnitude over state-of-the-art algorithms and almost three orders of magnitude of additional speed-up over Dinkelbach's algorithm for fractional programs. [ABSTRACT FROM AUTHOR]

In data centers, up to dozens of tasks are colocated on a single physical machine. Machines are used more efficiently, but the performance of the tasks deteriorates, as the colocated tasks compete for shared resources. Since the tasks are heterogeneous, the resulting performance dependencies are complex. In our previous work [1] , [2] we proposed a new combinatorial optimization model that uses two parameters of a task — its size and its type — to characterize how a task influences the performance of other tasks allocated to the same machine. In this paper, we study the egalitarian optimization goal: the aim is to optimize the performance of the worst-off task. This problem generalizes the classic makespan minimization on multiple processors ($P||C_{\max }$P||Cmax). We prove that polynomially-solvable variants of $P||C_{\max }$P||Cmax are NP-hard for this generalization, and that the problem is hard to approximate when the number of types is not constant. For a constant number of types, we propose a PTAS, a fast approximation algorithm, and a series of heuristics. We simulate the algorithms on instances derived from a trace of one of Google clusters. Compared with baseline algorithms solving $P||C_{\max }$P||Cmax, our proposed algorithms aware of the types of the jobs lead to significantly better tasks' performance. The notion of type enables us to extend standard combinatorial optimization methods to handle degradation of performance caused by colocation. Types add a layer of additional complexity. However, our results — approximation algorithms and good average-case performance — show that types can be handled efficiently. [ABSTRACT FROM AUTHOR]

Ordered statistics-based decoding (OSD), which exhibits a near maximum likelihood decoding performance, suffers from huge computational complexity as the order increases. In this letter, we propose a fast and scalable OSD by considering the OSD as a fast searching problem. In the searching process, if the up-to-date minimum cost value is less than a predicted threshold value, then we can safely skip the search for remaining higher orders. The computational complexity of the proposed algorithm converges quickly to that of order one, regardless of the maximum order. Compared with the probabilistic necessary conditions-based OSD, the proposed algorithm exhibits speed-up gains of a factor of approximately 2,740 (at 3.0dB) for (127,64) BCH codes, with an indistinguishable decoding performance. [ABSTRACT FROM AUTHOR]

In sketched clustering, a dataset of $T$ samples is first sketched down to a vector of modest size, from which the centroids are subsequently extracted. Its advantages include 1) reduced storage complexity and 2) centroid extraction complexity independent of $T$. For the sketching methodology recently proposed by Keriven et al., which can be interpreted as a random sampling of the empirical characteristic function, we propose a sketched clustering algorithm based on approximate message passing. Numerical experiments suggest that our approach is more efficient than the state-of-the-art sketched clustering algorithm “CL-OMPR” (in both computational and sample complexity) and more efficient than k-means++ when $T$ is large. [ABSTRACT FROM AUTHOR]

In this letter, we consider the problem of detecting finite-alphabet sparse signals from noisy and coarsely quantized measurements. To solve this problem, we propose a greedy sparse signal detection algorithm referred to as Bayesian matching pursuit (BMP). The key idea of BMP is to identify the non-zero elements of a sparse signal that produce the largest a posteriori probabilities in an iterative fashion. Our simulation results show that the BMP algorithm outperforms the existing sparse signal reconstruction algorithms in terms of frame error rates even with a significantly reduced computational complexity. [ABSTRACT FROM AUTHOR]

The problem of phase-noise compensation for correlated phase noise in coded multichannel optical transmission is investigated. To that end, a simple multichannel phase-noise model is considered and the maximum a posteriori detector for this model is approximated using two frameworks, namely factor graphs (FGs) combined with the sum–product algorithm (SPA) and a variational Bayesian (VB) inference method. The resulting pilot-aided algorithms perform iterative phase-noise compensation in cooperation with a decoder, using extended Kalman smoothing to estimate the a posteriori phase-noise distribution jointly for all channels. The system model and the proposed algorithms are verified using experimental data obtained from space-division multiplexed multicore-fiber transmission. Through Monte Carlo simulations, the algorithms are further evaluated in terms of phase-noise tolerance for coded transmission. It is observed that they significantly outperform the conventional approach to phase-noise compensation in the optical literature. Moreover, the FG/SPA framework performs similarly or better than the VB framework in terms of phase-noise tolerance of the resulting algorithms, for a slightly higher computational complexity. [ABSTRACT FROM AUTHOR]

This paper investigates the hybrid precoding design for millimeter wave (mmWave) multiple-input-multiple-output (MIMO) systems with finite-alphabet inputs. The mmWave MIMO system employs partially-connected hybrid precoding architecture with dynamic subarrays, where each radio frequency (RF) chain is connected to a dynamic subset of antennas. We consider the design of analog and digital precoders utilizing statistical and/or mixed channel state information (CSI), which involve solving an extremely difficult problem in theory: First, designing the optimal partition of antennas over RF chains is a combinatorial optimization problem, whose optimal solution requires an exhaustive search over all antenna partitioning solutions; Second, the average mutual information under mmWave MIMO channels lacks closed-form expression and involves prohibitive computational burden; and Third, the hybrid precoding problem with given partition of antennas is nonconvex with respect to the analog and digital precoders. To address these issues, this paper first presents a simple criterion and the corresponding low complexity algorithm to design the optimal partition of antennas using statistical CSI. Then, it derives the lower bound and its approximation for the average mutual information, in which the computational complexity is greatly reduced compared to calculating the average mutual information directly. In addition, it also shows that the lower bound with a constant shift offers a very accurate approximation to the average mutual information. This paper further proposes utilizing the lower bound approximation as a low-complexity and accurate alternative for developing a manifold-based gradient ascent algorithm to find near-optimal analog and digital precoders. Several numerical results are provided to show that our proposed algorithm outperforms the existing hybrid precoding algorithms. [ABSTRACT FROM AUTHOR]