Search

There is growing interest in applying distributed machine learning to edge computing, forming federated edge learning. Federated edge learning faces non-i.i.d. and heterogeneous data, and the communication between edge workers, possibly through distant locations and with unstable wireless networks, is more costly than their local computational overhead. In this work, we propose ${{\sf DONE}}$ DONE , a distributed approximate Newton-type algorithm with fast convergence rate for communication-efficient federated edge learning. First, with strongly convex and smooth loss functions, ${{\sf DONE}}$ DONE approximates the Newton direction in a distributed manner using the classical Richardson iteration on each edge worker. Second, we prove that ${{\sf DONE}}$ DONE has linear-quadratic convergence and analyze its communication complexities. Finally, the experimental results with non-i.i.d. and heterogeneous data show that ${{\sf DONE}}$ DONE attains a comparable performance to Newton's method. Notably, ${{\sf DONE}}$ DONE requires fewer communication iterations compared to distributed gradient descent and outperforms DANE, FEDL, and GIANT, state-of-the-art approaches, in the case of non-quadratic loss functions. [ABSTRACT FROM AUTHOR]

Reinforcement learning (RL) has demonstrated its ability to solve high dimensional tasks by leveraging non-linear function approximators. However, these successes are mostly achieved by ’black-box’ policies in simulated domains. When deploying RL to the real world, several concerns regarding the use of a ’black-box’ policy might be raised. In order to make the learned policies more transparent, we propose in this paper a policy iteration scheme that retains a complex function approximator for its internal value predictions but constrains the policy to have a concise, hierarchical, and human-readable structure, based on a mixture of interpretable experts. Each expert selects a primitive action according to a distance to a prototypical state. A key design decision to keep such experts interpretable is to select the prototypical states from trajectory data. The main technical contribution of the paper is to address the challenges introduced by this non-differentiable prototypical state selection procedure. Experimentally, we show that our proposed algorithm can learn compelling policies on continuous action deep RL benchmarks, matching the performance of neural network based policies, but returning policies that are more amenable to human inspection than neural network or linear-in-feature policies. [ABSTRACT FROM AUTHOR]

By employing time-varying proximal functions, adaptive subgradient methods (ADAGRAD) have improved the regret bound and been widely used in online learning and optimization. However, ADAGRAD with full matrix proximal functions (ADA-FULL) cannot handle large-scale problems due to the impractical $O(d^3)$ O (d 3) time and $O(d^2)$ O (d 2) space complexities, though it has better performance when gradients are correlated. In this paper, we propose two efficient variants of ADA-FULL via a matrix sketching technique called frequent directions (FD). The first variant named as ADA-FD directly utilizes FD to maintain and manipulate low-rank matrices, which reduces the space and time complexities to $O(\tau d)$ O (τ d) and $O(\tau ^2d)$ O (τ 2 d) respectively, where $d$ d is the dimensionality and $\tau \ll d$ τ ≪ d is the sketching size. The second variant named as ADA-FFD further adopts a doubling trick to accelerate FD used in ADA-FD, which reduces the average time complexity to $O(\tau d)$ O (τ d) while only doubles the space complexity of ADA-FD. Theoretical analysis reveals that the regret of ADA-FD and ADA-FFD is close to that of ADA-FULL as long as the outer product matrix of gradients is approximately low-rank. Experimental results demonstrate the efficiency and effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

This paper explores the non-convex composition optimization consisting of inner and outer finite-sum functions with a large number of component functions. This problem arises in important applications such as nonlinear embedding and reinforcement learning. Although existing approaches such as stochastic gradient descent (SGD) and stochastic variance reduced gradient (SVRG) descent can be applied to solve this problem, their query complexities tend to be high, especially when the number of inner component functions is large. Therefore, to significantly improve the query complexity of current approaches, we have devised the stochastic composition via variance reduction (SCVR). What's more, we analyze the query complexity under different numbers of inner function and outer function. Based on different kinds of estimation of inner component function, we also present the SCVRII algorithm, though the order of query complexities are the same with SCVR. Additionally, we propose an extension to handle the mini-batch cases, which improve the query complexity under the optimal mini-batch size. The experimental results validate our proposed algorithms and theoretical analyses. [ABSTRACT FROM AUTHOR]

The ever increasing technological demand for the DFT computation poses several challenges both to theory and hardware realization. The design of usual fast Fourier transform (FFT) algorithms seems to have reached a stage of diminishing returns in terms of performance. Alternatively, approximate transform methods have been demonstrated to provide substantial gains in terms of energy-efficiency and performance by tolerating small inaccuracies in the results. In this letter, we present a transform scaling method variant of the Cooley-Tukey algorithm to obtain DFT approximations of large blocksize. The proposed method scales up a given $N$ -point transformation to an $N^{2}$ -point transformation. Such scaling can be successively applied leading to $N^{2^{n}}$ -point transformations. We have fully presented the $32^{4}$ -point DFT approximation which stems from a multiplierless 32-point DFT approximation. The proposed approximation is equipped with a fast algorithm; we also supply the arithmetic complexity assessment and an error analysis. [ABSTRACT FROM AUTHOR]

The design of a fuzzy neural network (FNN) has long been a challenging problem since most methods rely on approximation error to train an FNN, which may easily result in overfitting phenomenon to degrade the generalization performance. To improve the generalization performance, an FNN with a multiobjective optimization algorithm (MOO-FNN) is proposed in this article. First, the multilevel learning objectives are designed around the generalization performance to guide the training process of an FNN. Then, the method utilizes the approximation error, the structure complexity, and the output smoothness indicators instead of a single indicator to improve the evaluation accuracy of generalization performance. Second, an MOO algorithm with continuous–discrete variables is developed to optimize the FNN. Then, MOO is able to use a novel particle update method to adjust both the structure and parameters rather than adjusting them separately, thereby achieving suitable generalization performance of the FNN. Third, the convergence of MOO-FNN is analyzed in detail to guarantee its successful applications. Finally, the experimental studies of MOO-FNN have been performed on model identification of nonlinear systems to verify the effectiveness. The results illustrate that MOO-FNN has a significant improvement over some state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

There is an increasing need for charging station recommendation to minimize the overall charging time for electric vehicles and balance load for the charging stations. To grant this need, we model the recommendation problem as a Markov Decision Process (MDP) problem. However, the traditional MDP model has the issue of ‘curse of dimensionality’. To address this issue, we propose an extension of MDP: multiple-phase MDP, in which the state transition of MDP is decomposing into several phases, so as to reduce the state space and state transition complexities. This is done by introducing two states other than the normal state defined in MDP: post decision state and intermediate decision state. Then, we propose an online learning based algorithm to solve the formulated multiple-phase MDP model. Thanks to the reduced complexities of the state space and state transition, the proposed online algorithm can converge fast. By comparing to other recommendation mechanisms, such as game theory based recommendation and Q-learning based recommendation, our simulation evaluation demonstrates that our proposition can bring good performance. [ABSTRACT FROM AUTHOR]

In this paper, we propose one joint interference alignment and subchannel allocation (JIARA) interference management scheme, aiming at maximizing the number of satisfactory users with different degrees of freedom (DoF) demand in ultra-dense wireless networks, while the existing works only consider the same DoF demands. The original JIARA scheme is equivalent to the maximum $K$ -colorable subgraph (MKCS) problem in graph theory for a given $K$ -colors and the multicoloring demand at each vertex, hence NP-hard. Therefore, we propose one graph theory based low complexity sub-optimal JIARA scheme. Firstly, we propose one virtual allocation of subchannel based scheme to construct transformed the conflict graph, which is applicable for the different DoF demands and different size of the feasible IA group. Furthermore, we propose one greedy multi-coloring based algorithm to determine the maximum number of satisfactory users. Simulation results show that the proposed JIARA scheme outperforms the subchannel resource allocation only scheme. [ABSTRACT FROM AUTHOR]

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacities of the servers determine the partition by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power consuming and are often also required for other tasks such as classification and routing. Previous work showed how to compute the smallest prefix-matching TCAM necessary to implement a given partition exactly. In this paper we solve the more practical case, where at most $n$ prefix-matching TCAM rules are available, restricting the ability to implement exactly the desired partition. We give simple and efficient algorithms to find $n$ rules that generate a partition closest in $L_\infty $ to the desired one. We do the same for a one-sided version of $L_\infty $ which equals to the maximum overload on a server and for a relative version of it. We use our algorithms to evaluate how the expected error changes as a function of the number of rules, the number of servers, and the width of the TCAM. [ABSTRACT FROM AUTHOR]

Many successful methods have been proposed for learning low-dimensional representations on large-scale networks, while almost all existing methods are designed in inseparable processes, learning embeddings for entire networks even when only a small proportion of nodes are of interest. This leads to great inconvenience, especially on large-scale or dynamic networks, where these methods become almost impossible to implement. In this paper, we formalize the problem of separated matrix factorization, based on which we elaborate a novel objective function that preserves both local and global information. We compare our SMF framework with approximate SVD algorithms and demonstrate SMF can capture more information when factorizing a given matrix. We further propose SepNE, a simple and flexible network embedding algorithm which independently learns representations for different subsets of nodes in separated processes. By implementing separability, our algorithm reduces the redundant efforts to embed irrelevant nodes, yielding scalability to large networks. To further incorporate complex information into SepNE, we discuss several methods that can be used to leverage high-order proximities in large networks. We demonstrate the effectiveness of SepNE on several real-world networks with different scales and subjects. With comparable accuracy, our approach significantly outperforms state-of-the-art baselines in running times on large networks. [ABSTRACT FROM AUTHOR]

Source localization has been a crucial fundamental service in wireless sensor networks (WSNs). Existing algorithms assume a regular region or controlled deployment. In practice, however, irregular network topologies often occurs, which greatly downgrade the localization performance. In this paper, we propose a new distributed localization approach based on Anchor Segmentation and Projection for Irregular networks (ASPI). The new framework is composed of three phases: anchor segmentation boarder construction, convex hull identification and projection-based localization. An anchor based network approximate convex segmentation method is proposed to reduce the consumption of network resources in the first two phases and an improved giftwrapping based convex hull identification method is provided to reduce the complexity. In the localization phase, we formulate the localization as a convex feasibility problem to avoid the multimodality in Maximum likelihood techniques and an alternative procedure is provided for inconsistent situation in the projection-based scheme. Experiments are conducted and the results demonstrate that our algorithm outperforms other existing solutions in irregular-shaped networks in higher accuracy with low complexity. [ABSTRACT FROM AUTHOR]

In this paper, two widely used spectrum sensing algorithms, sphericity test and energy detection are considered. The statistics of sphericity test and energy detector with estimated noise power are weighted and fused to propose a mixture detector. The proposed mixture detector based on the fusion test statistics can simultaneously utilize the power information and correlation feature of the received signals. Specifically, the theoretical optimal weight is derived by maximizing the deflection coefficient of the mixture detector. Besides, the analytical expressions for the decision threshold, false alarm probability and detection probability of this algorithm are derived by moment-matching Beta approximation. Numerical examples are provided to illustrate the validity of theoretical analysis. And simulations show that the proposed mixture detector with optimal weight can improve the spectrum sensing performance compared with existing algorithms. [ABSTRACT FROM AUTHOR]

Multi-carrier faster-than-Nyquist (MFTN) signaling constitutes a promising spectrally efficient non-orthogonal physical layer waveform. In this correspondence, we propose a pair of low-complexity generalized approximate message passing (GAMP)-based frequency-domain equalization (FDE) algorithms for MFTN systems operating in multipath channels. To mitigate the ill-condition of the resultant equivalent channel matrix, we construct block circulant interference matrices by inserting a few cyclic postfixes, followed by truncating the duration of the inherent two-dimensional interferences. Based on the decomposition of the block circulant matrices, we develop a novel frequency-domain received signal model using the two-dimensional fast Fourier transform for mitigating the colored noise imposed by the non-orthogonal matched filter. Moreover, we derive a GAMP-based FDE algorithm and its refined version, where the latter relies on approximations for circumventing the emergence of the ill-conditioned matrices. Our simulation results demonstrate that, for a fixed spectral efficiency, MFTN signaling can significantly improve the bit error rate (BER) performance by jointly optimizing the time- and frequency-domain packing factors. Compared to its Nyquist-signaling counterpart, our proposed MFTN systems employing the refined GAMP equalizer can achieve about 39% higher transmission rates at a negligible BER performance degradation. [ABSTRACT FROM AUTHOR]

Low-density parity-check (LDPC) codes are widely used as error correction codes in new generation digital TV standards, such as the second generation of terrestrial digital video broadcasting standard (DVB-T2), Advanced Television Systems Committee (ATSC) 3.0, etc. The nonlinear belief propagation (BP) algorithm has excellent decoding performance for LDPC codes, but is often simplified in hardware implementations by linear min-sum (MS) algorithm due to its high complexity. This simplification also leads to over-estimation problems, which can be corrected by adding factors in conventional algorithms (e.g., normalized min-sum (NMS), offset min-sum (OMS), and variable scaling normalized min-sum (VMS) algorithms). However, the correction factors of these modified MS algorithms cannot adapt to different channels and modulations, and the performance needs further improvement. In this paper, the concepts of over-estimation value (OEV) and over-estimation rate (OER) are introduced to describe the over-estimation problem of the MS algorithm. Then, under the guidance of OEV and OER, a polygonal line min-sum (PMS) algorithm with correction factors adapted to different channels and modulations is proposed according to LLR distribution. Following the properties of OEV and OER, PMS algorithm is further simplified into Simplified PMS (SPMS) algorithm. LDPC codes from ATSC 3.0 are adopted in this paper to evaluate SPMS algorithm in comparison with the conventional algorithms. Extensive simulation results show that the SPMS algorithm for ATSC 3.0 LDPC decoder has at most 1.61dB, 0.24dB and 0.36dB gain over NMS, OMS and VMS algorithms respectively when frame error rate (FER) is at 10−4 level over additive white Gaussian noise (AWGN) channel with QPSK modulation. More importantly, the simulation results show that the SPMS algorithm can achieve much better performance than these modified MS algorithms over AWGN and Rayleigh channel with higher-order modulations or under limited maximum iteration number. [ABSTRACT FROM AUTHOR]

Given a binary sequence with length $n$ , determining its minimal rational fraction representation (MRFR) has important applications in the design and cryptanalysis of stream ciphers. There are many studies of this problem since Klapper and Goresky first introduced an adaptive rational approximation algorithm with a time complexity of $O(n^{2}\log n\log \log n)$. In this paper, we revisit this problem by considering both adaptive and non-adaptive efficient algorithms. Compared with the state-of-art methods, we make several contributions to the problem of finding MRFR. Firstly, we find a general and precise recursive relationship between the minimal bases for two adjacent lattices generated by successive truncation sequences. This enables us to improve the currently fastest adaptive algorithm proposed by Li et al.. Secondly, by optimizing a time-consuming step of the well-known Lagrange reduction algorithm for 2-dimensional lattices, we obtain a non-adaptive, and yet practically faster MRFR-solving algorithm named global Euclidean algorithm. Thirdly, we identify theoretical flaws on some non-adaptive methods in the literature by counter-examples and correct the problems by designing modified Euclidean algorithm named partial Euclidean algorithm. Meanwhile, we further reduce the time complexity of existing algorithm from $O(n^{2})$ to $O(n\log ^{2}n\log \log n)$ by invoking the half-gcd algorithm. We also conduct a comprehensive experimental comparative analysis on the above algorithms to validate our theoretical analysis. [ABSTRACT FROM AUTHOR]

We consider stochastic optimization of a smooth non-convex loss function with a convex non-smooth regularizer. In the online setting, where a single sample of the stochastic gradient of the loss is available at every iteration, the problem can be solved using the proximal stochastic gradient descent (SGD) algorithm and its variants. However in many problems, especially those arising in communications and signal processing, information beyond the stochastic gradient may be available thanks to the structure of the loss function. By constructing a strongly convex surrogate of the loss function at every iteration, the stochastic SCA algorithms can exploit the structural properties of the loss function. In this work, we take a closer look at the stochastic SCA algorithm and develop its asynchronous variant which can be used for resource allocation in wireless networks. While the stochastic SCA algorithm is known to converge asymptotically, its iteration complexity has not been well-studied, and is the focus of the current work. The insights obtained from the non-asymptotic analysis allow us to develop a more practical asynchronous variant of the stochastic SCA algorithm which allows the use of surrogate calculated in earlier iterations. We characterize precise bound on the maximum delay the algorithm can tolerate, while still achieving the same convergence rate. We apply the algorithm to the problem of linear precoding in wireless sensor networks, where it can be implemented at low complexity but is shown to perform well in practice. [ABSTRACT FROM AUTHOR]

Algorithms determine which calculations computers use to solve problems and are one of the central pillars of computer science. As algorithms improve, they enable scientists to tackle larger problems and explore new domains and new scientific techniques ,. Bold claims have been made about the pace of algorithmic progress. For example, the President’s Council of Advisors on Science and Technology (PCAST), a body of senior scientists that advise the U.S. President, wrote in 2010 that “in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed”. However, this conclusion was supported based on data from progress in linear solvers , which is just a single example. With no guarantee that linear solvers are representative of algorithms in general, it is unclear how broadly conclusions, such as PCAST’s, should be interpreted. Is progress faster in most algorithms? Just some? How much on average? [ABSTRACT FROM AUTHOR]

Expectation Propagation (EP)-based Multiple-Input Multiple-Output (MIMO) detector achieves exceptional performance in high-dimensional systems with high-order modulations and flexible antenna configurations. However, based on our studies, the EP MIMO detector cannot achieve superior performance due to the empirical parameter selection, including initial variance and damping factors. According to the influence of the moment matching and parameter selection on the performance of the EP MIMO detector, we propose a modified EP MIMO detector (MEPD). To obtain the initial variance and damping factors which lead to better performance, we adopt a deep learning scheme, the iterative process of MEPD is unfolded to establish MEPNet for parameters training. The simulation results show that MEPD with off-line trained parameters outperforms the original one in various MIMO scenarios. Besides, the proposed MEPD with deep learning parameters selection is more robust than EPD in practical scenarios. [ABSTRACT FROM AUTHOR]

With the advent of big data and data lakes, data are often integrated from multiple sources. Such integrated data are often of poor quality, due to inconsistencies, errors, and so forth. One way to check the quality of data is to infer functional dependencies (fds). However, in many modern applications it might be necessary to extract properties and relationships that are not captured through fds, due to the necessity to admit exceptions, or to consider similarity rather than equality of data values. Relaxed fds (rfds) have been introduced to meet these needs, but their discovery from data adds further complexity to an already complex problem, also due to the necessity of specifying similarity and validity thresholds. We propose Domino, a new discovery algorithm for rfds that exploits the concept of dominance in order to derive similarity thresholds of attribute values while inferring rfds. An experimental evaluation on real datasets demonstrates the discovery performance and the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Since the late 1980s, temporal difference (TD) learning has dominated the research area of policy evaluation algorithms. However, the demand for the avoidance of TD defects, such as low data-efficiency and divergence in off-policy learning, has inspired the studies of a large number of novel TD-based approaches. Gradient-based and least-squares-based algorithms comprise the major part of these new approaches. This paper aims to combine advantages of these two categories to derive an efficient policy evaluation algorithm with ${O}$ (${n} ^{ {2}}$) per-time-step runtime complexity. The least-squares-based framework is adopted, and the gradient correction is used to improve convergence performance. This paper begins with the revision of a previous ${O}$ (${n} ^{ {3}}$) batch algorithm, least-squares TD with a gradient correction (LS-TDC) to regularize the parameter vector. Based on the recursive least-squares technique, an ${O}$ (${n} ^{ {2}}$) counterpart of LS-TDC called RC is proposed. To increase data efficiency, we generalize RC with eligibility traces. An off-policy extension is also proposed based on importance sampling. In addition, the convergence analysis for RC as well as LS-TDC is given. The empirical results in both on-policy and off-policy benchmarks show that RC has a higher estimation accuracy than that of RLSTD and a significantly lower runtime complexity than that of LSTDC. [ABSTRACT FROM AUTHOR]

A decoding algorithm for polar (sub)codes with binary 2t × 2t polarization kernels is presented. It is based on the window processing (WP) method, which exploits the linear relationship of the polarization kernels and the Arikan matrix. This relationship enables one to compute the kernel input symbols probabilities by computing the probabilities of several paths in Arikan successive cancellation (SC) decoder. In this paper we propose an improved version of WP, which has significantly lower arithmetic complexity and operates in log-likelihood ratios (LLRs) domain. The algorithm identifies and reuses common subexpressions arising in computation of Arikan SC path scores. The proposed algorithm is applied to kernels of size 16 and 32 with improved polarization properties. It enables polar (sub)codes with the considered kernels to simultaneously provide better performance and lower decoding complexity compared with polar (sub)codes with Arikan kernel. [ABSTRACT FROM AUTHOR]

Orthogonal time frequency space (OTFS) modulation has attracted substantial attention recently due to its great potential of providing reliable communications in high-mobility scenarios. In this article, we propose a novel hybrid signal detection algorithm for OTFS modulation. Based on the system model, we first derive the near-optimal symbol-wise maximum a posteriori (MAP) detection algorithm for OTFS modulation. Then, in order to reduce the detection complexity, we propose a partitioning rule that separates the related received symbols into two subsets for detecting each transmitted symbol, according to the corresponding path gains. According to the partitioning rule, we design the hybrid detection algorithm to exploit the power discrepancy of each subset, where the MAP detection is applied to the subset with larger channel gains, while the parallel interference cancellation (PIC) detection is applied to the subset with smaller channel gains. We also provide the error performance analysis of the proposed hybrid detection algorithm. Simulation results show that the proposed hybrid detection algorithm can not only approach the performance of the near-optimal symbol-wise MAP algorithms, but also offer a substantial performance gain compared with existing algorithms. [ABSTRACT FROM AUTHOR]

Massive multiple-input-multiple-output (M-MIMO) features a capability for spatial multiplexing of large number of users. This number becomes even more extreme in extra-large (XL-MIMO), a variant of M-MIMO where the antenna array is of very large size. Yet, the problem of signal processing complexity in M-MIMO is further exacerbated by the XL size of the array. The basic processing problem boils down to a sparse system of linear equations that can be addressed by the randomized Kaczmarz (RK) algorithm. This algorithm has recently been applied to devise low-complexity M-MIMO receivers; however, it is limited by the fact that certain configurations of the linear equations may significantly deteriorate the performance of the RK algorithm. In this article, we embrace the interest in accelerated RK algorithms and introduce three new RK-based low-complexity receiver designs. In our experiments, our methods are not only able to overcome the previous scheme, but they are more robust against inter-user interference (IUI) and sparse channel matrices arising in the XL-MIMO regime. In addition, we show that the RK-based schemes use a mechanism similar to that used by successive interference cancellation (SIC) receivers to approximate the regularized zero-forcing (RZF) scheme. [ABSTRACT FROM AUTHOR]

This paper studies a large random matrix system (LRMS) model involving an arbitrary signal distribution and forward error control (FEC) coding. We establish an area property based on the approximate message passing (AMP) algorithm. Under the assumption that the state evolution for AMP is correct for the coded system, the achievable rate of AMP is analyzed. We prove that AMP achieves the constrained capacity of the LRMS with an arbitrary signal distribution provided that a matching condition is satisfied. As a byproduct, we provide an alternative derivation for the constraint capacity of an LRMS using a proved property of AMP. We discuss realization techniques for the matching principle of binary signaling using irregular low-density parity-check (LDPC) codes and provide related numerical results. We show that the optimized codes demonstrate significantly better performance over un-matched ones under AMP. For quadrature phase shift keying (QPSK) modulation, bit error rate (BER) performance within 1 dB from the constrained capacity limit is observed. [ABSTRACT FROM AUTHOR]

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems. [ABSTRACT FROM AUTHOR]

Large-scale data clustering is an essential key for big data problem. However, no current existing approach is “optimal” for big data due to high complexity, which remains it a great challenge. In this article, a simple but fast approximate DBSCAN, namely, KNN-BLOCK DBSCAN, is proposed based on two findings: 1) the problem of identifying whether a point is a core point or not is, in fact, a kNN problem and 2) a point has a similar density distribution to its neighbors, and neighbor points are highly possible to be the same type (core point, border point, or noise). KNN-BLOCK DBSCAN uses a fast approximate kNN algorithm, namely, FLANN, to detect core-blocks (CBs), noncore-blocks, and noise-blocks within which all points have the same type, then a fast algorithm for merging CBs and assigning noncore points to proper clusters is also invented to speedup the clustering process. The experimental results show that KNN-BLOCK DBSCAN is an effective approximate DBSCAN algorithm with high accuracy, and outperforms other current variants of DBSCAN, including ρ-approximate DBSCAN and AnyDBC. [ABSTRACT FROM AUTHOR]

Only when we understand how hackers think, can we defend against their attacks. Towards this end, this paper studies the cyber-attacks that aim to remove nodes or links from network topologies. We particularly focus on one type of such attacks called Maximum Vertex Coverage Attacks under Knapsack constraint (MVCAK), in which a hacker has a fixed budget to remove nodes from a network with the nodes involving different costs for removal, and the hacker’s goal is to maximize the number of links incident to the nodes removed. Since the MVCAK problem is NP-hard, we firstly propose an optimal solution by Integer Linear Program formulation. Secondly, we give an approximate solution by Linear Programming relaxation that achieves an approximation ratio of 3/4, outperforming the existing 1 - 1√(e) (about 0.39). Thirdly, since the straightforward implementation of our approximate solution has a high time complexity, we propose two heuristics to significantly reduce its complexity while preserving the approximation ratio. We formally prove the correctness and the effectiveness of these two heuristics. Finally, we conduct extensive experiments on both artificial and real-world networks, showing that our approximate solution produces almost the same results as the optimal solution in practice and has an acceptable running time. [ABSTRACT FROM AUTHOR]

Eigenvalue decomposition is widely used in dimensionality reduction for knowledge engineering, in particular principal component analysis and other similar spectral methods. Traditional eigenvalue decomposition algorithms for decomposing a matrix of size n × n are usually of complexity O(n3), due to a bottleneck in using Householder/Givens transforms to convert a general matrix to a tri-diagonal one. It is proposed in this article a new algorithm that takes only O(n2.584963 log 1/ɛ) computational complexity to achieve accuracy ɛ of eigenvalue decomposition for any ɛ > 0 . The basic idea of our algorithm is to convert a matrix into a diagonal form in multi-scale divide and conquer scheme, and the conversion is to iteratively and recursively apply two phases of operations called diagonal attractions and diagonal absorptions respectively. In a diagonal attraction, it attracts the off-diagonal entries to make the entries nearer to the diagonal larger in magnitude than those farther away from the diagonal. In a diagonal absorption, it absorbs the near-to-diagonal nonzero entries into the diagonal. In such a scheme, no Householder or Givens transforms are involved. Moreover, diagonal attractions and diagonal absorptions can be implemented with fast matrix multiplications. The scheme’s divide and conquer pattern also allows our algorithm to be easily mapped to modern computer hardware. Our algorithm also complements well the family of randomized eigenvalue/SVD algorithms using sampling techinques, which are of complexity O(nα polylog (1/ɛ)) with small α but very large overheads in the polylog. Their strength in the small exponent α of n in complexity was easily cancelled by the exploding overheads in the polylog. Now, with their low-accuracy estimate refined by our algorithm for high accuracy, their strength can be boosted significantly. [ABSTRACT FROM AUTHOR]

This paper proposes fast convergent distributed algorithms for weighted average consensus of input data. For acyclic graphs, we give an algorithm that converges to the exact weighted average consensus in a finite number of iterations, equal to the graph diameter. For loopy (cyclic) graphs, we offer two remedies. In the first one, we give another distributed algorithm to enable our average consensus algorithm applicable to a loopy graph by converting it into a spanning tree. In the second one, we consider a slightly modified average consensus problem whose optimal solution approximates the consensus solution with arbitrary precision, and give a modified average consensus algorithm with guaranteed exponential convergence to the optimal solution. The proposed average consensus algorithms enjoy low complexities, robustness to transmission adversaries, and asynchronous implementation. Our algorithms are conceptually different from the popular graph Laplacian approach, and converge much faster than the latter approach. [ABSTRACT FROM AUTHOR]

Multiple-input Multiple-output (MIMO) technologies play an important role in modern and future wireless communication systems as they can improve the capacity without increasing the bandwidth. MIMO detection is one of the key technologies for MIMO system designs. MIMO detection schemes based on Message Passing (MP) algorithms have attracted extensive attention in recent years. The MIMO detection scheme based on Expectation Propagation (EP), which is also a kind of MP algorithms, has been proved to achieve the Bayes-optimal performance under the conditions of large system limit and compression rate threshold. However, there is improvement space for the detection performance of the EP algorithm when the conditions are not satisfied, which are the common cases in the practical applications. In this paper, when the conditions of the large system limit and compression rate threshold are not satisfied, we analyze the influences of two factors, the initial parameters selection and the moment matching strategy, on the performance of EP based detection scheme. As a result, we propose an improved EP detection scheme based on optimizing the two factors. Simulation results show that the proposed scheme outperforms the original EP detection scheme in different MIMO scenarios. [ABSTRACT FROM AUTHOR]

FIR filters have boosted the development of digital signal processing, beamformers, and so on, due to their stability and low coefficient sensitivity. Generally, the design of FIR filters follows two main principles, i.e., the specification on the response error and the low implementation complexity. In this brief, we describe the sparsity of the filter coefficients using the k-maximum function, which equals to ℓ0-norm under mild conditions and has no restriction on the magnitude of nonzero coefficients. In order to avoid possible violation of specifications on response errors caused by frequency discretization, we estimate the frequencies at which the magnitude of the response error is maximized when constructing linear problems in the proposed algorithm. To address the nonlinearity and nonconvexity of the resulted optimization problem, we transform it into a piecewise linear concave optimization (PLCO) problem. Considering the fact that a PLCO problems is reduced to a linear programming (LP) problem locally, we outline an iterative algorithm by solving a series of LP problems and provide a brief complexity analysis. Numerical experiments on the propose method and some state-of-the-art methods are performed, the result of which shows the excellent performance of the propose method on balancing the sparsity and computational efficiency. [ABSTRACT FROM AUTHOR]

We provide a differentially private algorithm for hypothesis selection. Given samples from an unknown probability distribution P and a set of m probability distributions $\mathcal {H}$ , the goal is to output, in a $\varepsilon $ -differentially private manner, a distribution from $\mathcal {H}$ whose total variation distance to P is comparable to that of the best such distribution (which we denote by $\alpha $). The sample complexity of our basic algorithm is $\text {O}\left ({\frac {\log \text {m}}{\alpha ^{2}} + \frac {\log \text {m}}{\alpha \varepsilon }}\right)$ , representing a minimal cost for privacy when compared to the non-private algorithm. We also can handle infinite hypothesis classes $\mathcal {H}$ by relaxing to $(\varepsilon,\delta)$ -differential privacy. We apply our hypothesis selection algorithm to give learning algorithms for a number of natural distribution classes, including Gaussians, product distributions, sums of independent random variables, piecewise polynomials, and mixture classes. Our hypothesis selection procedure allows us to generically convert a cover for a class to a learning algorithm, complementing known learning lower bounds which are in terms of the size of the packing number of the class. As the covering and packing numbers are often closely related, for constant $\alpha $ , our algorithms achieve the optimal sample complexity for many classes of interest. Finally, we describe an application to private distribution-free PAC learning. [ABSTRACT FROM AUTHOR]

Non-uniform constellation (NUC) is an advanced technology in digital terrestrial television broadcasting (DTTB) systems to reduce the shapping gap of BICM capacity to Shannon theoretical limit and provide performance gain. Two-dimensional NUC (2D-NUC) is a kind of NUC providing more gain but bringing higher demapping complexity at the receiver, which hinders its application prospects, especially in power limited systems. This paper proposes three novel demapping algorithms with reduced complexity for low to medium code rate 2D-NUCs in Advanced Television Systems Committee 3rd Generation (ATSC 3.0) standard. The proposed algorithms are based on the introduction of virtual points, the strategy of condensed symbols reduction and some reasonable approximations. There is a trade-off between the demapping complexity and performance. These three algorithms have different degrees of reduction in complexity and performance degradation, so they accommodate for different practical requirements. Theoretical analysis and simulation results are also given in this paper to prove the efficiency of the proposed demapping algorithms with reduced complexity. [ABSTRACT FROM AUTHOR]

In this article, we investigate effective sketching schemes via sparsification for high dimensional multilinear arrays or tensors. More specifically, we propose a novel tensor sparsification algorithm that retains a subset of the entries of a tensor in a judicious way, and prove that it can attain a given level of approximation accuracy in terms of tensor spectral norm with a much smaller sample complexity when compared with existing approaches. In particular, we show that for a kth order $ {d}\times \cdots \times {d}$ cubic tensor of stable rank $ {r}_{ {s}}$ , the sample size requirement for achieving a relative error $\varepsilon $ is, up to a logarithmic factor, of the order $ {r}_{ {s}}^{1/2} {d}^{ {k}/2} /\varepsilon $ when $\varepsilon $ is relatively large, and $ {r}_{ {s}} {d} /\varepsilon ^{2}$ and essentially optimal when $\varepsilon $ is sufficiently small. It is especially noteworthy that the sample size requirement for achieving a high accuracy is of an order independent of k. To further demonstrate the utility of our techniques, we also study how higher order singular value decomposition (HOSVD) of large tensors can be efficiently approximated via sparsification. [ABSTRACT FROM AUTHOR]

Standard Principal-Component Analysis (PCA) is known to be sensitive to outliers among the processed data. On the other hand, L1-norm-based PCA (L1-PCA) exhibits sturdy resistance against outliers, while it performs similar to standard PCA when applied to nominal or smoothly corrupted data. Exact calculation of the K L1-norm Principal Components (L1-PCs) of a rank-r data matrix X ∈ RD × N costs O(N(r −1)K + 1). In this work, we present reduced-rank L1-PCA (RR L1-PCA): a hybrid approach that approximates the K L1-PCs of X by the L1-PCs of its L2-norm-based rank-d approximation (d ≤ r), calculable exactly with reduced complexity O(N(d − 1)K + 1). The proposed method combines the denoising capabilities and low computation cost of standard PCA with the outlier-resistance of L1-PCA. RR L1-PCA is accompanied by formal performance guarantees as well as thorough numerical studies that corroborate its computational and corruption resistance merits. [ABSTRACT FROM AUTHOR]

The problem of distributed representation learning is one in which multiple sources of information $X_1,\ldots, X_K$ X 1 ,... , X K are processed separately so as to learn as much information as possible about some ground truth $Y$ Y . We investigate this problem from information-theoretic grounds, through a generalization of Tishby's centralized Information Bottleneck (IB) method to the distributed setting. Specifically, $K$ K encoders, $K \geq 2$ K ≥ 2 , compress their observations $X_1,\ldots, X_K$ X 1 ,... , X K separately in a manner such that, collectively, the produced representations preserve as much information as possible about $Y$ Y . We study both discrete memoryless (DM) and memoryless vector Gaussian data models. For the discrete model, we establish a single-letter characterization of the optimal tradeoff between complexity (or rate) and relevance (or information) for a class of memoryless sources (the observations $X_1,\ldots, X_K$ X 1 ,... , X K being conditionally independent given $Y$ Y ). For the vector Gaussian model, we provide an explicit characterization of the optimal complexity-relevance tradeoff. Furthermore, we develop a variational bound on the complexity-relevance tradeoff which generalizes the evidence lower bound (ELBO) to the distributed setting. We also provide two algorithms that allow to compute this bound: i) a Blahut-Arimoto type iterative algorithm which enables to compute optimal complexity-relevance encoding mappings by iterating over a set of self-consistent equations, and ii) a variational inference type algorithm in which the encoding mappings are parametrized by neural networks and the bound approximated by Markov sampling and optimized with stochastic gradient descent. Numerical results on synthetic and real datasets are provided to support the efficiency of the approaches and algorithms developed in this paper. [ABSTRACT FROM AUTHOR]

Many robotics applications require alignment and fusion of observations obtained at multiple views to form a global model of the environment. Multiway data association methods provide a mechanism to improve alignment accuracy of pairwise associations and ensure their consistency. However, existing methods that solve this computationally challenging problem are often too slow for real-time applications. Furthermore, some of the existing techniques can violate the cycle consistency principle, thus drastically reducing the fusion accuracy. This article presents the consistent lifting, embedding, and alignment rectification (CLEAR) algorithm to address these issues. By leveraging insights from the multiway matching and spectral graph clustering literature, CLEAR provides cycle-consistent and accurate solutions in a computationally efficient manner. Numerical experiments on both synthetic and real datasets are carried out to demonstrate the scalability and superior performance of our algorithm in real-world problems. This algorithmic framework can provide significant improvement in the accuracy and efficiency of existing discrete assignment problems, which traditionally use pairwise (but potentially inconsistent) correspondences. An implementation of CLEAR is made publicly available online. [ABSTRACT FROM AUTHOR]

Ever-increasing research efforts have been dedicated to radio frequency identification (RFID) systems, such as finding top-k, elephant groups, and missing-tag detection. While group labeling, which is how to tell tags their associated group data, is the common prerequisite in many RFID applications, its efficiency is not well optimized due to the transmission of useless data with only one seed used. In this paper, we introduce a unified protocol called GLMS which employs multiple seeds to construct a composite indicator vector (CIV), reducing the useless transmission. Technically, to address Seed Assignment Problem (SAP) arising during building CIV, we develop an approximation algorithm (AA) with a competitive ratio 0.632 by globally searching for the seed contributing to the most useful slot. We then further design two simplified algorithms through local searching, namely $c$ c -search-I and its enhanced version $c$ c -search-II, reducing the complexity by one order of magnitude while achieving comparable performance. We conduct extensive simulations to demonstrate the superiority of our approaches. [ABSTRACT FROM AUTHOR]

Recently, various iterative methods are investigated to achieve linear minimum mean square error (MMSE) detection accuracy for uplink massive multiple-input multiple-output (MIMO) systems. This letter introduces the non-stationary Richardson (NSR) iteration to achieve fast convergence rate, and reduces its complexity with approximate eigenvalues in massive MIMO system. However, when the system scale grows and channel correlation is considered, the performance of NSR method decays obviously. To improve the robustness, this letter further proposes a deeply fused SDNSR algorithm, which effectively overcomes the weakness of NSR method by fully utilizing the information obtained through the steepest descent (SD) method and NSR method. Moreover, the complexity is significantly reduced by adopting matrix-vector multiplication and reusing intermediate results. Simulation results and complexity analysis exhibit that the SDNSR method achieves superior performance with lower complexity compared to the recently reported works. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a powerful technique based on Leave-One-Out analysis to the study of low-rank matrix completion problems. Using this technique, we develop a general approach for obtaining fine-grained, entrywise bounds for iterative stochastic procedures in the presence of probabilistic dependency. We demonstrate the power of this approach in analyzing two of the most important algorithms for matrix completion: (i) the non-convex approach based on Projected Gradient Descent (PGD) for a rank-constrained formulation, also known as the Singular Value Projection algorithm, and (ii) the convex relaxation approach based on nuclear norm minimization (NNM). Using this approach, we establish the first convergence guarantee for the original form of PGD without regularization or sample splitting, and in particular shows that it converges linearly in the infinity norm. For NNM, we use this approach to study a fictitious iterative procedure that arises in the dual analysis. Our results show that NNM recovers an $d$ -by- $d$ rank- $r$ matrix with $\mathcal {O}(\mu r \log (\mu r) d\log d)$ observed entries. This bound has optimal dependence on the matrix dimension and is independent of the condition number. To the best of our knowledge, none of previous sample complexity results for tractable matrix completion algorithms satisfies these two properties simultaneously. [ABSTRACT FROM AUTHOR]

We consider the tasks of feature selection and policy evaluation based on linear value function approximation in reinforcement learning problems. High-dimension feature vectors and limited number of samples can easily cause over-fitting and computation expensive. To prevent this problem, ${\ell _{1}}$ -regularized method obtains sparse solutions and thus improves generalization performance. We propose an efficient ${\ell _{1}}$ -regularized recursive least squares-based online algorithm with ${O}$ (${n} ^{{2}}$) complexity per time-step, termed ${\ell _{1}}$ -RC. With the help of nested optimization decomposition, ${\ell _{1}}$ -RC solves a series of standard optimization problems and avoids minimizing mean squares projected Bellman error with ${\ell _{1}}$ -regularization directly. In ${\ell _{1}}$ -RC, we propose RC with iterative refinement to minimize the operator error, and we propose an alternating direction method of multipliers with proximal operator to minimize the fixed-point error. The convergence of ${\ell _{1}}$ -RC is established based on ordinary differential equation method and some extensions are also given. In empirical computations, some state-of-the-art ${\ell _{1}}$ -regularized methods are chosen as the baselines, and ${\ell _{1}}$ -RC are tested in both policy evaluation and learning control benchmarks. The empirical results show the effectiveness and advantages of ${\ell _{1}}$ -RC. [ABSTRACT FROM AUTHOR]

Numerical optimization serves as one of the pillars of machine learning. To meet the demands of big data applications, lots of efforts have been put on designing theoretically and practically fast algorithms. This article provides a comprehensive survey on accelerated first-order algorithms with a focus on stochastic algorithms. Specifically, this article starts with reviewing the basic accelerated algorithms on deterministic convex optimization, then concentrates on their extensions to stochastic convex optimization, and at last introduces some recent developments on acceleration for nonconvex optimization. [ABSTRACT FROM AUTHOR]

A low-complexity approximation for the 16-point DFT and its respective multiplierless fast algorithm is proposed. A receive mode multibeam phased-array experiment was realized at 2.4 GHz employing a 16-element IQ receiver array that uses the proposed approximate spatial DFT in real-time in order to achieve multibeam digital beamforming. The 16-beam digital receiver experiment uses a ROACH-2 based Xilinx Virtex-6 FPGA platform for both digital beam computation as well as to perform the multireceiver analog-to-digital conversion. Receive mode RF beams were measured and compared to the exact DFT (realized with fixed-point multipliers with 8-bit twiddle factors). The measured approximate DFT closely followed the measured beams resulting from the fixed-point conventional DFT implementation. The approximate DFT achieves RF beam performance (mainlobe gain, sidelobes) similar to the DFT at the cost of a small error which would be tolerable for the majority of multibeam phased-array receivers. The 16-point approximate DFT provides a hardware reduction of $\sim$70% with respect to FFTs, setting up a low size, weight and power (SWaP) system.The maximum magnitude error of the filter bank response is 0.106 ($\approx -20$ dB). [ABSTRACT FROM AUTHOR]

Expectation propagation (EP) attains near-optimal performance for massive multiple-input multiple-output (MIMO) detection. However, the inevitable matrix inversions and exponentiations at each EP iteration bring great challenges to realistic hardware implementation. To address these issues, a low-complexity EP with iterative Neumann-series Approximation (EP-INSA) detector is proposed by employing INSA to estimate the inverse matrices. Further approximations are applied to avoid the exponentiations, which makes EP-INSA an efficient, feasible, and hardware-friendly detector for massive MIMO with various modulations. Simulation results show that EP-INSA attains similar performance as exact EP with only a few INSA terms, which assures enhanced performance and complexity trade-off. The associated hardware architectures of EP-INSA detector are also presented. The implementation results on 65 nm CMOS technology show that our design yields a throughput of 0.62 Gb/s with 2.63 × area efficiency of existing EP detector. [ABSTRACT FROM AUTHOR]

Recent years have witnessed increasingly more uses of Unmanned Aerial Vehicle (UAV) swarms for rapidly providing wireless coverage to ground users. Each UAV is constrained in its energy storage and wireless coverage, and it consumes most energy on flying to the top of the target area, thus leaving limited leftover energy for hovering at its deployed position and keeping wireless coverage. The literature largely overlooks the sustainability issues of deploying UAV swarm and the UAV-to-UAV cooperation, and we aim to maximize the minimum leftover energy storage among all the UAVs after their deployment. Our new energy-saving deployment problem captures that each UAV's wireless coverage is adjustable by its service altitude, and also takes the no-fly-zone (NFZ) constraint into account. We show that a UAV with larger initial energy storage in the UAV swarm should be deployed further away from the UAV station, and we propose an optimal energy-saving deployment algorithm by jointly balancing heterogeneous UAVs’ flying distances on the ground and final service altitudes in the sky. When n UAVs with different initial energy storages are dispatched from different initial locations, we prove this problem is NP-hard in general by reduction from partition problem. Despite of this, we propose to preserve the UAVs’ location order and successfully design an approximation algorithm of complexity n log 1/ε to arbitrarily approach the optimum with error ε. Inspiring by this proposed (1−ε)-approximation algorithm, we present a heuristic algorithm to solve the general case by balancing the efficiency and computation complexity well. [ABSTRACT FROM AUTHOR]